Vector-space ranking with effective early termination

ABSTRACT

Considerable research effort has been invested in improving the effectiveness of information retrieval systems. Techniques such as relevance feedback, thesaural expansion, and pivoting all provide better quality responses to queries when tested in standard evaluation frameworks. But such enhancements can add to the cost of evaluating queries. In this paper we consider the pragmatic issue of how to improve the cost-effectiveness of searching. We describe a new inverted file structure using quantized weights that provides superior retrieval effectiveness compared to conventional inverted file structures when early termination heuristics are employed. That is, we are able to reach similar effectiveness levels with less computational cost, and so provide a better cost/performance compromise than previous inverted file organisations.

REFERENCES

• 1: Anh Ngoc Vo , Alistair Moffat, Compressed inverted files with reduced decoding overheads, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.290-297, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291011]
• 2: Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215329]
• 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: Gordon V. Cormack , Christopher R. Palmer , Charles L. A. Clarke, Efficient construction of large test collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.282-289, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291009]
• 5: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, August 1998
• 6: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 7: D.K.Harman and G.andela.Retrieving records from a gigabyte of text on a minicomputer using statistical ranking. Journal of the American Society for Information Science 41 (8):581 -589,Aug.1990.
• 8: D.Hawking,E.Voorhees,N.raswell,and P.Bailey.Overview of theTRE -8webtrack.InE.M.VoorheesandD.K.Harman, editors,Proc. Eighth Text REtrieval Conference (TREC-8), Gaithersburg,MD,Nov.1999.National Institute of Standards and Technology Special Publication 500-246.
• 9: 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]
• 10: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 11: Alistair Moffat , Justin Zobel , Ron Sacks-Davis, Memory efficient ranking, Information Processing and Management: an International Journal, v.30 n.6, p.733-744, 1994 [doi>10.1016/0306-4573(94)90002-7]
• 12: 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
• 13: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• 14: S. E. Robertson , S. Walker , M. M. Hancock-Beaulieu, Large test collection experiments on an operational, interactive system: Okapi at TREC, Information Processing and Management: an International Journal, v.31 n.3, p.345-360, May-June 1995
• 15: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 16: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]
• 17: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 18: 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]
• 19: Justin Zobel, How reliable are the results of large-scale information retrieval experiments?, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.307-314, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291014]
• 20: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Experimentation, Languages, Performance