Estimating the selectivity of approximate string queries

ABSTRACT

Approximate queries on string data are important due to the prevalence of such data in databases and various conventions and errors in string data. We present the VSol estimator, a novel technique for estimating the selectivity of approximate string queries. The VSol estimator is based on inverse strings and makes the performance of the selectivity estimator independent of the number of strings. To get inverse strings we decompose all database strings into overlapping substrings of length q (q-grams) and then associate each q-gram with its inverse string: the IDs of all strings that contain the q-gram. We use signatures to compress inverse strings, and clustering to group similar signatures.

We study our technique analytically and experimentally. The space complexity of our estimator only depends on the number of neighborhoods in the database and the desired estimation error. The time to estimate the selectivity is independent of the number of database strings and linear with respect to the length of query string. We give a detailed empirical performance evaluation of our solution for synthetic and real-world datasets. We show that VSol is effective for large skewed databases of short strings.

REFERENCES

• 1: Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.239-250, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 3: Andrei Z. Broder, Identifying and Filtering Near-Duplicate Documents, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.1-10, June 21-23, 2000
• 4: 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
• 5: Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003 [doi>10.1016/S0022-0000(02)00031-4]
• 6: Cohen, E. 1994. Estimating the size of the transitive closure in linear time. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS) (Nov.). 190--200.
• 7: Finding Interesting Associations without Support Pruning, Proceedings of the 16th International Conference on Data Engineering, p.489, February 28-March 03, 2000
• 8: Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005 [doi>10.1016/j.jalgor.2003.12.001]
• 9: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 10: 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
• 11: Victoria J. Hodge , Jim Austin, A Comparison of Standard Spell Checking Algorithms and a Novel Binary Neural Approach, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1073-1081, September 2003 [doi>10.1109/TKDE.2003.1232265]
• 12: H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, One-dimensional and multi-dimensional substring selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.214-230, December 2000 [doi>10.1007/s007780000029]
• 13: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 14: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 15: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 16: 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
• 17: 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
• 18: Liang Jin , Chen Li , Sharad Mehrotra, Efficient Record Linkage in Large Data Sets, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.137, March 26-28, 2003
• 19: 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
• 20: Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
• 21: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 22: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
• 23: Mazeika, A. and Böhlen, M. H. 2006. Cleansing databases of misspelled proper nouns. In Proceedings of the CleanDB Workshop (in conjunction with) the International Conference on Very Large Databases (VLDB).
• 24: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 25: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 26: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 27: Sahinalp, C., Tasan, M., Macker, J., and Ozsoyoglu, Z. M. 2003. Distance based indexing for string proximity search. In Proceedings of the International Conference on Data Engineering (ICDE). 125--137.
• 28: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 29: Simon Sheu , Chang-Yeng Cheng , Alan Chang, Fast Pattern Detection in Stream Data, Proceedings of the 19th International Conference on Advanced Information Networking and Applications, p.125-130, March 25-30, 2005 [doi>10.1109/AINA.2005.184]
• 30: Esko Ukkonen, On Approximate String Matching, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.487-495, August 21-27, 1983
• 31: Vernica, R. and Li, C. 2007. Flamingo project. http://www.ics.uci.edu/~flamingo/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Inverse strings, min-wise hash signatures, q-grams