Optimization of inverted vector searches

ABSTRACT

A simple algorithm is presented for increasing the efficiency of information retrieval searches which are implemented using inverted files. This optimization algorithm employs knowledge about the methods used for weighting document and query terms in order to examine as few inverted lists as possible. An extension to the basic algorithm allows greatly increased performance optimization at a modest cost in retrieval effectiveness. Experimental runs are made examining several different term weighting models and showing the optimization possible with each.

REFERENCES

• 1: G. Salton, ed., The SMART Retrieval System. Prentice-Hall, Englewood Cliffs, N.J. (1971).
• 2: R.E. Williamson, "Real-time Document Retrieval". Ph.D. Thesis, Cornell University (1971).
• 3: N. Jardine and C.J. van Rijsbergen, "The Use of Hierarchic Clustering in Information Retrieval". Inform. Stor. Retr. 1971, 7, 217- 240.
• 4: Caroline Merriam Eastman, A tree algorithm for nearest neighbor searching in document retrieval systems., 1977
• 5: Caroline M. Eastman , Stephen F. Weiss, A tree algorithm for nearest neighbor searching in document retrieval systems, Proceedings of the 1st annual international ACM SIGIR conference on Information storage and retrieval, p.131-149, May 10-12, 1978
• 6: Stephen F. Weiss, A probabilistic algorithm for nearest neighbour searching, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.325-333, June 23-27, 1980, Cambridge, England
• 7: 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
• 8: F. Murtagh, "A Very Fast Exact Nearest Neighbor Algorithm for Use in Information Retrieval". Information Technology: Research and Development, 1, 1982, 275-283.
• 9: M.J. McGill, T. Noreault, "Syracuse Information Retrieval Experiment (SIRE): Rationale and Basic System Design". Report, School of Information Studies, Syraeue University, May 1977.
• 10: Michael J. McGill , Linda C. Smith , Stuart Davidson , Terry Noreault, Syracuse information retrieval experiment (SIRE): design of an on-line bibliographic retrieval system, ACM SIGIR Forum, v.10 n.4, p.37-44, Spring 1976 [doi>10.1145/1095286.1095300]
• 11: T.E. Doszkocs, B.A. Rapp, "Searching MED- LINE in English: A Prototype User Interface with Natural Language Query, Ranked Output and Relevance Feedback", Proceedings of the ASIS Annual Meeting, 18, 1979, 131-139.
• 12: D.J. Harper, "Relevance Feedback in Document Retrieval Systems: An Evaluation of Probabilistie Strategies". Ph.D. Thesis, The University of Cambridge (1980}.
• 13: W.B. Croft, "Document Representation in Probabilistic Models of Information Retrieval". Journal of the American Society for Information Science, 32, 451-457.
• 14: W.B. Croft, "Experiments with Representation in a Document Retrieval System". Information Technology: Research and Development, 2, 1983, 1-21.
• 15: G. Salton, C.S. Yang, C.T. Yu, "A Theory of Term Importance in Automatic Text Analysis". Journal of the American Society for Information Science, 26, 1975, 33-44.
• 16: E.A. Fox, "Characteristics of Two New Experimental Collections in Computer and Information Science Containing Textual and Bibliographic Concepts". Technical Report 83-561, Cornell University, 1983.
• 17: C.A. Buckley, "An Overview of the Implementation of SMART". Technical Report, Cornell University, 1985.
• 18: H. Wu and G. Salton, "The Estimation of Term Relevance Weights Using Relevance Feedback". Journal of Documentation, 37, 1981, 194-214.