Efficient algorithms for document retrieval problems

ABSTRACT

We are given a collection D of text documents d1,…,dk, with ∑i = n, which may be preprocessed. In the document listing problem, we are given an online query comprising of a pattern string p of length m and our goal is to return the set of all documents that contain one or more copies of p. In the closely related occurrence listing problem, we output the set of all positions within the documents where pattern p occurs. In 1973, Weiner [24] presented an algorithm with O(n) time and space preprocessing following which the occurrence listing problem can be solved in time O(m + output) where output is the number of positions where p occurs; this algorithm is clearly optimal. In contrast, no optimal algorithm is known for the closely related document listing problem, which is perhaps more natural and certainly well-motivated.We provide the first known optimal algorithm for the document listing problem. More generally, we initiate the study of pattern matching problems that require retrieving documents matched by the patterns; this contrasts with pattern matching problems that have been studied more frequently, namely, those that involve retrieving all occurrences of patterns. We consider document retrieval problems that are motivated by online query processing in databases, Information Retrieval systems and Computational Biology. We present very efficient (optimal) algorithms for our document retrieval problems. Our approach for solving such problems involve performing "local" encodings whereby they are reduced to range query problems on geometric objects --- points and lines --- that have color. We present improved algorithms for these colored range query problems that arise in our reductions using the structural properties of strings. This approach is quite general and yields simple, efficient, implementable algorithms for all the document retrieval problems in this paper.

REFERENCES

• 1: P. Agarwal and M. van Kreveld. Polygon and connected component intersection searching Algorithmica, 1996, 15, 626-660.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Amir M. Ben-Amram , Omer Berkman , Costas S. Iliopoulos , Kunsoo Park, The subtree max gap problem with application to parallel string covering, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 23-25, 1994, Arlington, Virginia, United States
• 4: G. Benson and M. Waterman A Method for Fast Database Search for All k-nucleotide Repeats. Nucleic Acids Research, Vol 22, No. 22, 1994.
• 5: Gerth Stølting Brodal , Rune B. Lyngsø , Christian N. S. Pedersen , Jens Stoye, Finding Maximal Pairs with Bounded Gap, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.134-149, July 22-24, 1999
• 6: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
• 7: P. Ferragina. Personal Communication, 1999.
• 8: Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375610]
• 9: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 10: Prosenjit Gupta , Ravi Janardan , Michiel Smid, Further results on generalized intersection searching problems: counting, reporting, and dynamization, Journal of Algorithms, v.19 n.2, p.282-317, Sept. 1995 [doi>10.1006/jagm.1995.1038]
• 11: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 12: Torben Hagerup , Peter Bro Miltersen , Rasmus Pagh, Deterministic dictionaries, Journal of Algorithms, v.41 n.1, p.69-85, October 2001 [doi>10.1006/jagm.2001.1171]
• 13: Jiawei Han , Laks V. S. Lakshmanan , Jian Pei, Scalable frequent-pattern mining methods: an overview, Tutorial notes of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, August 26-29, 2001, San Francisco, California [doi>10.1145/502786.502792]
• 14: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 15: Lucas Chi Kwong Hui, Color Set Size Problem with Application to String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.230-243, April 29-May 01, 1992
• 16: R. Janardan and M. Lopez. Generalized intersection searching problems. Intl J Comput. Geom. Applications, 3(1993), 39-69.
• 17: R. Kolpakov and G. Kucherov. Finding repeats with fixed gap. Technical Report RR-3901, INRIA, March 2000.
• 18: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 19: Udi Manber , Ricardio Baeza-Yates, An algorithm for string matching with a sequence of don't cares, Information Processing Letters, v.37 n.3, p.133-136, Feb. 18, 1991 [doi>10.1016/0020-0190(91)90032-D]
• 20: Yossi Matias , S. Muthukrishnan , Süleyman Cenk Sahinalp , Jacob Ziv, Augmenting Suffix Trees, with Applications, Proceedings of the 6th Annual European Symposium on Algorithms, p.67-78, August 24-26, 1998
• 21: R. Hariharan. Personal communication, 1999.
• 22: SQL full text indexing. http://larr.unm.edu/owen/SQLBOL70/html/ca --- co15.htm.
• 23: Jaak Vilo. Discovering Frequent Patterns from Strings Technical Report, Department of Computer Science P.O.Box 26 FIN-00014. Check at http://citeseer.nj.nec.com/103438.html.
• 24: P. Weiner. Linear Pattern Matching Algorithms. Proc. 14th IEEE Symp on Switching and Automata Theory, 1973, 1-11.