Indexing text data under space constraints

ABSTRACT

An important class of queries is the LIKE predicate in SQL. In the absence of an index, LIKE queries are subject to performance degradation. The notion of indexing on substrings (or <i>q</i>-grams) has been explored earlier without sufficient consideration of efficiency. <i>q</i>-grams are used to prune away rows that do not qualify for the query. The problem is to identify a finite number of grams subject to storage constraint that gives maximal pruning for a given query workload. Our contributions include: i) a formal problem definition, that produces results within a provable error bound, ii) performance evaluation of the application of the novel method to real data, and iii) parallelization of the algorithm, scaling considerations and a proposal to handle scaling issues.

REFERENCES

• 1: A Fast Regular Expression Indexing Engine, Proceedings of the 18th International Conference on Data Engineering, p.419, February 26-March 01, 2002
• 2: Digital Bibliography & Library Project. http://dblp.uni-trier.de/.
• 3: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 4: E. Ukkonen. Online construction of Suffix-trees. Algorithmica, 1993.
• 5: L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, L. Pietarinen, and D. Srivastava. Using q grams in a dbms for approximate string processing. IEEE Data Engineering Bulletin, 24(4):28--34, 2001.
• 6: 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
• 7: Stefan Burkhardt , Andreas Crauser , Paolo Ferragina , Hans-Peter Lenhof , Eric Rivals , Martin Vingron, q-gram based database searching using a suffix array (QUASAR), Proceedings of the third annual international conference on Computational molecular biology, p.77-83, April 11-14, 1999, Lyon, France [doi>10.1145/299432.299460]
• 8: Hore, B., Hacigumus, H., Iyer, B., Mehrotra, S. Indexing Text Data under Space Constraints TR-DB-04-02, www-db.ics.uci.edu/pages/publications/index.shtml
• 9: Dorit S. Hochbaum, Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: D. S. Hochbaum and A. Pathria. Analysis of the Greedy Approach in Problems of Maximum k-Coverage. Naval Research Quarterly, (45):615--627, 1998.
• 11: 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]
• 12: Surajit Chaudhuri , Ashish Kumar Gupta , Vivek Narasayya, Compressing SQL workloads, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564747]
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 15: Bayer, R., and McCreight, C. Organization and maintenance of large ordered indexes Acta Informatica, 1972, pp173--189.
• 16: Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225287]
• 17: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 18: Ricardo A. Baeza-Yates , Gaston H. Gonnet, Fast text searching for regular expressions or automaton searching on tries, Journal of the ACM (JACM), v.43 n.6, p.915-936, Nov. 1996 [doi>10.1145/235809.235810]
• 19: Maxime Crochemore , Christophe Hancart, Automata for matching patterns, Handbook of formal languages, vol. 2: linear modeling: background and application, Springer-Verlag New York, Inc., New York, NY, 1997
• 20: Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M., T., and Seiferas, J. The smallest automaton recognizing the subwords of a text. Theoretical computer science, 40(1), 1985, pp. 31--55.
• 21: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 22: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 23: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 24: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 25: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 26: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 27: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 28: Kaushik Chakrabarti , Sharad Mehrotra, Efficient concurrency control in multidimensional access methods, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.25-36, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation

Keywords:
B-tree, SQL, index, like queries, q-grams