Approximate substring selectivity estimation

ABSTRACT

We study the problem of estimating selectivity of approximate substring queries. Its importance in databases is ever increasing as more and more data are input by users and are integrated with many typographical errors and different spelling conventions. To begin with, we consider edit distance for the similarity between a pair of strings. Based on information stored in an extended N-gram table, we propose two estimation algorithms, MOF and LBS for the task. The latter extends the former with ideas from set hashing signatures. The experimental results show that MOF is a light-weight algorithm that gives fairly accurate estimations. However, if more space is available, LBS can give better accuracy than MOF and other baseline methods. Next, we extend the proposed solution to other similarity predicates, SQL LIKE operator and Jaccard similarity.

REFERENCES

• 1: 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
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 4: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 5: Surajit Chaudhuri , Venkatesh Ganti , Luis Gravano, Selectivity Estimation for String Predicates: Overcoming the Underestimation Problem, Proceedings of the 20th International Conference on Data Engineering, p.227, March 30-April 02, 2004
• 6: Arturas Mazeika , Michael H. Böhlen , Nick Koudas , Divesh Srivastava, Estimating the selectivity of approximate string queries, ACM Transactions on Database Systems (TODS), v.32 n.2, p.12-es, June 2007 [doi>10.1145/1242524.1242529]
• 7: 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]
• 8: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 9: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 10: W. Cohen, P. Ravikmar and and S. Fienberg. A Comparison of String Metrics for Matching Names and Records. Proc. of KDD Workshop on Data Cleaning, pp. 73--78, 2003.
• 11: Flamingo Project, http://www.ics.uci.edu/flamingo/.
• 12: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 13: H. V. Jagadish , Raymond T. Ng , Divesh Srivastava, Substring selectivity estimation, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.249-260, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304001]
• 14: Liang Jin , Chen Li , Nick Koudas , Anthony K. H. Tung, Indexing mixed types for approximate retrieval, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Liang Jin , Chen Li, Selectivity estimation for fuzzy string predicates in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: Nick Koudas , Amit Marathe , Divesh Srivastava, Flexible string matching against large databases in practice, Proceedings of the Thirtieth international conference on Very large data bases, p.1078-1086, August 31-September 03, 2004, Toronto, Canada
• 17: P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.282-293, June 04-06, 1996, Montreal, Quebec, Canada
• 18: Hongrae Lee , Raymond T. Ng , Kyuseok Shim, Extending q-grams to estimate selectivity of string matching with low edit distance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 19: Chen Li , Bin Wang , Xiaochun Yang, VGRAM: improving performance of approximate queries on string collections using variable-length grams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: Nikos Mamoulis, Efficient processing of joins on set-valued attributes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872778]
• 21: Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000 [doi>10.1145/351827.384246]
• 22: 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]
• 23: Winkler, W. E. The State of Record Linkage and Current Research Problems. Statistics of Income Division, U.S. Bureau of the Census, 1999.