Efficient top-k count queries over imprecise duplicates

ABSTRACT

We propose efficient techniques for processing various Top-K count queries on data with noisy duplicates. Our method differs from existing work on duplicate elimination in two significant ways: First, we dedup on the fly only the part of the data needed for the answer --- a requirement in massive and evolving sources where batch deduplication is expensive. The non-local nature of the problem of partitioning data into duplicate groups, makes it challenging to filter only those tuples forming the K largest groups. We propose a novel method of successively collapsing and pruning records which yield an order of magnitude reduction in running time compared to deduplicating the entire data first.

Second, we return multiple high scoring answers to handle situations where it is impossible to resolve if two records are indeed duplicates of each other. Since finding even the highest scoring deduplication is NP-hard, the existing approach is to deploy one of many variants of score-based clustering algorithms which do not easily generalize to finding multiple groupings. We model deduplication as a segmentation of a linear embedding of records and present a polynomial time algorithm for finding the R highest scoring answers. This method closely matches the accuracy of an exact exponential time algorithm on several datasets.

REFERENCES

• 1: Rohit Ananthakrishna , Surajit Chaudhuri , Venkatesh Ganti, Eliminating fuzzy duplicates in data warehouses, Proceedings of the 28th international conference on Very Large Data Bases, p.586-597, August 20-23, 2002, Hong Kong, China
• 2: Periklis Andritsos , Ariel Fuxman , Renee J. Miller, Clean Answers over Dirty Databases: A Probabilistic Approach, Proceedings of the 22nd International Conference on Data Engineering, p.30, April 03-07, 2006 [doi>10.1109/ICDE.2006.35]
• 3: Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.238, November 16-19, 2002
• 5: Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007 [doi>10.1145/1217299.1217304]
• 6: M. Bilenko. Learnable similarity functions and their applications to clustering and record linkage. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25--29, 2004, San Jose, California, USA, pages 981--982. AAAI Press / The MIT Press, 2004.
• 7: Mikhail Bilenko , Sugato Basu , Mehran Sahami, Adaptive Product Normalization: Using Online Learning for Record Linkage in Comparison Shopping, Proceedings of the Fifth IEEE International Conference on Data Mining, p.58-65, November 27-30, 2005 [doi>10.1109/ICDM.2005.18]
• 8: Mikhail Bilenko , Beena Kamath , Raymond J. Mooney, Adaptive Blocking: Learning to Scale Up Record Linkage, Proceedings of the Sixth International Conference on Data Mining, p.87-96, December 18-22, 2006 [doi>10.1109/ICDM.2006.13]
• 9: Mikhail Bilenko , Raymond Mooney , William Cohen , Pradeep Ravikumar , Stephen Fienberg, Adaptive Name Matching in Information Integration, IEEE Intelligent Systems, v.18 n.5, p.16-23, September 2003 [doi>10.1109/MIS.2003.1234765]
• 10: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with qualitative information, Journal of Computer and System Sciences, v.71 n.3, p.360-383, October 2005 [doi>10.1016/j.jcss.2004.10.012]
• 11: Surajit Chaudhuri , Bee-Chung Chen , Venkatesh Ganti , Raghav Kaushik, Example-driven design of efficient record matching queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 12: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 13: Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
• 14: David Cheng , Ravi Kannan , Santosh Vempala , Grant Wang, A divide-and-merge methodology for clustering, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1499-1525, December 2006 [doi>10.1145/1189769.1189779]
• 15: W. Cohen and J. Richman. Learning to match and cluster entity names. In ACM SIGIR' 01 Workshop on Mathematical/Formal Methods in Information Retrieval, 2001.
• 16: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 17: Xin Dong , Alon Y. Halevy , Cong Yu, Data integration with uncertainty, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 18: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Society, 64:1183--1210, 1969.
• 19: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 20: Ihab F. Ilyas , George Beskales , Mohamed A. Soliman, A survey of top-k query processing techniques in relational database systems, ACM Computing Surveys (CSUR), v.40 n.4, p.1-58, October 2008 [doi>10.1145/1391729.1391730]
• 21: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 22: J. Ko, T. Mitamura, and E. Nyberg. Language-independent probabilistic answer ranking for question answering. In ACL, 2007.
• 23: D. Koller and N. Friedman. Structured probabilistic models. Under preparation, 2007.
• 24: Yehuda Koren , David Harel, A Multi-scale Algorithm for the Linear Arrangement Problem, Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, p.296-309, June 13-15, 2002
• 25: Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas, Supporting ad-hoc ranking aggregates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142481]
• 26: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 27: A. McCallum and B. Wellner. Toward conditional models of identity uncertainty with application to proper noun coreference. In Proceedings of the IJCAI-2003 Workshop on Information Integration on the Web, pages 79--86, Acapulco, Mexico, Aug. 2003.
• 28: A. E. Monge and C. P. Elkan. The field matching problem: Algorithms and applications. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 1996.
• 29: H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity uncertainty and citation matching. In Advances in Neural Processing Systems 15, Vancouver, British Columbia, 2002. MIT Press.
• 30: S. Sarawagi. The crf project: a java implementation. http://crf.sourceforge.net, 2004.
• 31: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 32: S. Sarawagi and A. Kirpal. Scaling up the alias duplicate elimination system: A demostration. In Proc. of the 19th IEEE Int'l Conference on Data Engineering (ICDE), Bangalore, March 2003.
• 33: Sunita Sarawagi , Alok Kirpal, Efficient set joins on similarity predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007652]
• 34: Anish Das Sarma , Xin Dong , Alon Halevy, Bootstrapping pay-as-you-go data integration systems, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376702]
• 35: Mohamed A. Soliman , Ihab F. Ilyas , Kevin Chen--Chuan Chang, Probabilistic top-k and ranking-aggregate queries, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-54, August 2008 [doi>10.1145/1386118.1386119]
• 36: Michael L. Wick , Khashayar Rohanimanesh , Karl Schultz , Andrew McCallum, A unified approach for schema matching, coreference and canonicalization, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401977]
• 37: Xiaochun Yang , Bin Wang , Chen Li, Cost-based variable-length-gram selection for string collections to support approximate queries efficiently, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376655]