Real-time approximate Range Motif discovery & data redundancy removal algorithm
Real-time approximate Range Motif discovery & data redundancy removal algorithm
复制标题
DOI：
10.1145/1951365.1951422
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
A. Narang;Souvik Bhattacherjee
中科院分区：
文献类型：
--
作者：
A. Narang;Souvik Bhattacherjee
去除数据中的冗余是一个重要的问题，因为它有助于提高大规模（1000万到1亿条记录）数据集下游处理的资源和计算效率。在诸如IR、股票市场、电信等应用领域中，强烈需要以1Gb/s或更高速率流动的大量数据的实时数据冗余去除。我们考虑在一个大数据集中的记录上找到范围基序（簇）的问题，使得同一簇内的记录彼此近似接近。这个问题是密切相关的近似最近邻搜索，但更昂贵的计算。在海量数据集上实时可扩展的近似Range Motif发现是一个具有挑战性的问题。我们提出了新的顺序和并行的近似范围模体发现和数据删除算法使用布隆过滤器的设计。我们建立了我们的算法的假阳性和假阴性率的渐近上界。此外，我们的并行算法在多核架构的时间复杂度分析。对于1000万条记录，我们的并行算法可以在16核Intel Xeon 5570架构上，在59秒内对4个集（集群）执行近似范围Motif发现和重复数据删除。这给出了大约170 K记录/s和大约700 Mb/s的吞吐量（使用大小为4K位的记录）。据我们所知，这是在如此大规模的数据集上进行近似Range Motif发现和数据冗余去除的最高实时吞吐量。
Removing redundancy in the data is an important problem as it helps in resource and compute efficiency for downstream processing of massive (10 million to 100 million records) datasets. In application domains such as IR, stock markets, telecom and others there is a strong need for real-time data redundancy removal of enormous amounts of data flowing at the rate of 1Gb/s or higher. We consider the problem of finding Range Motifs (clusters) over records in a large dataset such that records within the same cluster are approximately close to each other. This problem is closely related to the approximate nearest neighbour search but is more computationally expensive. Real-time scalable approximate Range Motif discovery on massive datasets is a challenging problem. We present the design of novel sequential and parallel approximate Range Motif discovery and data de-duplication algorithms using Bloom filters. We establish asymptotic upper bounds on the false positive and false negative rates for our algorithm. Further, time complexity analysis of our parallel algorithm on multi-core architectures has been presented. For 10 million records, our parallel algorithm can perform approximate Range Motif discovery and data de-duplication, on 4 sets (clusters), in 59s, on 16 core Intel Xeon 5570 architecture. This gives a throughput of around 170K records/s and around 700Mb/s (using records of size 4K bits). To the best of our knowledge, this is the highest real-time throughput for approximate Range Motif discovery and data redundancy removal on such massive datasets.