Cost-based variable-length-gram selection for string collections to support approximate queries efficiently

ABSTRACT

Approximate queries on a collection of strings are important in many applications such as record linkage, spell checking, and Web search, where inconsistencies and errors exist in data as well as queries. Several existing algorithms use the concept of "grams," which are substrings of strings used as signatures for the strings to build index structures. A recently proposed technique, called VGRAM, improves the performance of these algorithms by using a carefully chosen dictionary of variable-length grams based on their requencies in the string collection. Since an index structure using fixed-length grams can be viewed as a special case of VGRAM, a fundamental problem arises naturally: what is the relationship between the gram dictionary and the performance of queries? We study this problem in this paper. We propose a dynamic programming algorithm for computing a tight lower bound on the number of common grams shared by two similar strings in order to improve query performance. We analyze how a gram dictionary affects the index structure of the string collection and ultimately the performance of queries. We also propose an algorithm for automatically computing a dictionary of high-quality grams for a workload of queries. Our experiments on real data sets show the improvement on query performance achieved by these techniques. To our best knowledge, this study is the first cost-based quantitative approach to deciding good grams for approximate string queries.

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: Roberto J. Bayardo , Yiming Ma , Ramakrishnan Srikant, Scaling up all pairs similarity search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242591]
• 3: V. R. Carvalho and W. W. Cohen. Improving "email speech acts" analysis via n-gram selection. In Analyzing Conversations in Text and Speech (ACTS) Workshop at HLT-NAACL, pages 35--41, 2006.
• 4: 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]
• 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: Surajit Chaudhuri , Venkatesh Ganti , Raghav Kaushik, A Primitive Operator for Similarity Joins in Data Cleaning, Proceedings of the 22nd International Conference on Data Engineering, p.5, April 03-07, 2006 [doi>10.1109/ICDE.2006.9]
• 7: Prahlad Fogla , Wenke Lee, q-Gram Matching Using Tree Models, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.433-447, April 2006 [doi>10.1109/TKDE.2006.66]
• 8: 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
• 9: M. Hadjieleftheriou, A. Chandel, N. Koudas, and D. Srivastava. Set similarity selection queries at interactive speeds. In ICDE, 2008.
• 10: Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031212]
• 11: 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]
• 12: 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
• 13: Min-Soo Kim , Kyu-Young Whang , Jae-Gil Lee , Min-Jae Lee, n-gram/2L: a space and time efficient two-level n-gram inverted index structure, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Nick Koudas , Sunita Sarawagi , Divesh Srivastava, Record linkage: similarity measures and algorithms, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142599]
• 15: 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
• 16: 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
• 17: C. Li, J. Lu, and Y. Lu. Efficient merging and filtering algorithms for approximate string searches. In ICDE, 2008.
• 18: 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
• 19: 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]
• 20: 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]
• 21: S. C. Sahinalp, M. Tasan, J. Macker, and Z. M. Özsoyoglu. Distance based indexing for string proximity search. In ICDE, 2003.
• 22: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Performance

Keywords:
approximate string query, gram selection, vgram