Fast evaluation of structured queries for information retrieval

ABSTRACT

Information retrieval systems are being challenged to manage larger and larger document collections. In an effort to provide better retrieval performance on large collections, more sophisticated retrieval techniques have been developed that support rich, structured queries. Structured queries are not amenable to previously proposed optimization techniques. Optimizing execution, however, is even more important in the context of large document collections. We present a new structured query optimization technique which we have implemented in an inference network-based information retrieval system. Experimental results show that query evaluation time can be reduced by more than half with little impact on retrieval effectiveness.

REFERENCES

• 1: Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
• 2: Eric W. Brown , James P. Callan , W. Bruce Croft , J. Eliot B. Moss, Supporting full-text information retrieval with a persistent object store, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.365-378, May 1994, Cambridge, United Kingdom
• 3: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 4: J. E Callan, W. B. Croft, and S. M. Harding. The INQUERY retrieval system. In Proc. of the 3rd Inter. Conf. on Database and Expert Systems Applications, Sept. 1992.
• 5: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 6: Donna Harman, Overview of the second text retrieval conference (TREC-2), Proceedings of the second conference on Text retrieval conference, p.271-289, May 1995, Washington, D.C., United States
• 7: D. Harman and G. Candela. Retrieving records from a gigabyte of text on a minicomputer using statistical ranking. J. Amer. Soc. Inf. Sci., 41 (8):581-589, Dec. 1990.
• 8: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 9: Y. Jing and W. B. Croft. An association thesaurus for information retrieval. In Proc. of RIAO 94 Conf., pages 146-I 60, New York, Oct. 1994.
• 10: D. Knaus and E Sch~iuble. Effective and efficient retrieval from large and dynamic document collections. In Harman {6}, pages 163-170.
• 11: Dario Lucarella, A document retrieval system based on nearest neighbour searching, Journal of Information Science, v.14 n.1, p.25-33, January 1988 [doi>10.1177/016555158801400104]
• 12: Alistair Moffat , Justin Zobel, Fast Ranking in Limited Space, Proceedings of the Tenth International Conference on Data Engineering, p.428-437, February 14-18, 1994
• 13: A. Moffat and J. Zobel. Self-indexing inverted files for fast text retrieval. Technical Report 94/2, Collaborative Information Technology Research institute, Department of Computer Science, Royal Melbourne Institute of Technology, Australia, Feb. 1994.
• 14: J. Eliot B. Moss, Design of the Mneme persistent object store, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.103-139, Apr. 1990 [doi>10.1145/96105.96109]
• 15: S. A. Perry and P. Willett. A review of the use of inverted files for best match searching in information retrieval systems. J. Inf. Sci., 6(2-3):59--66, 1983.
• 16: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• 17: Peter Schäuble, SPIDER: a multiuser information retrieval system for semistructured and dynamic data, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-327, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160756]
• 18: A. F. Smeaton , C. J. van Rijsbergen, The nearest neighbour problem in information retrieval: an algorithm using upperbounds, Proceedings of the 4th annual international ACM SIGIR conference on Information storage and retrieval: theoretical issues in information retrieval, p.83-87, May 31-June 02, 1981, Oakland, California
• 19: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 20: Wai Yee Peter Wong , Dik Lun Lee, Implementations of partial document ranking using inverted files, Information Processing and Management: an International Journal, v.29 n.5, p.647-669, Sept.-Oct. 1993 [doi>10.1016/0306-4573(93)90085-R]
• 21: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley Press, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Measurement, Performance, Theory