Efficient passage ranking for document databases

ABSTRACT

Queries to text collections are resolved by ranking the documents in the collection and returning the highest-scoring documents to the user. An alternative retrieval method is to rank passages, that is, short fragments of documents, a strategy that can improve effectiveness and identify relevant material in documents that are too large for users to consider as a whole. However, ranking of passages can considerably increase retrieval costs. In this article we explore alternative query evaluation techniques, and develop new tecnhiques for evaluating queries on passages. We show experimentally that, appropriately implemented, effective passage retrieval is practical in limited memory on a desktop machine. Compared to passage ranking with adaptations of current document ranking algorithms, our new “DO-TOS” passage-ranking algorithm requires only a fraction of the resources, at the cost of a small loss of effectiveness.

REFERENCES

• 1: James Allan, Relevance feedback with too much data, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.337-343, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215380]
• 2: 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]
• 3: Timothy C. Bell , Alistair Moffat , Ian H. Witten , Justin Zobel, The MG retrieval system: compressing for space and speed, Communications of the ACM, v.38 n.4, p.41-42, April 1995 [doi>10.1145/205323.205327]
• 4: BERTINO, E., OOI, B., SACKS-DAVIS, R., TAN, K.-L., AND ZOBEL, J. 1997. Text databases. In Indexing Techniques for Advanced Database Systems Kluwer Academic Publishers, Hing-ham, MA.
• 5: 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]
• 6: 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]
• 7: James P. Callan, Passage-level evidence in document retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.302-310, July 03-06, 1994, Dublin, Ireland
• 8: CLARKE,C.L.A.,CORMACK,G.V.,AND BURKOWSKI, F. J. 1995. Shortest substring ranking MultiText experiments for TREC-4. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 295-304.
• 9: CLARKE, C., CORMACK, G., AND TUDHOPE, E. 1997. Relevance ranking for one to three term queries. In Proceedings of the 5th RIAO Conference 388-412.
• 10: CORMACK, G., PALMER, C., BIESBROUCK, M., AND CLARKE, C. 1998. Deriving very short queries for high precision and recall. In Proceedings of the 7th Text Retreival Conference (TREC-7)
• 11: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 12: FULLER, M., KASZKIEL, M., KIM, D., NG, C., ROBERTSON, J., WILKINSON, R., WU, M., AND ZOBEL, J. 1998. TREC 7 ad hoc, speech, and interactive tracks at MDS/CSIRO. In Proceedings of the 7th Text Retreival Conference (TREC-7)
• 13: FULLER, M., KASZKIEL, M., NG, C., VINES, P., WILKINSON, R., AND ZOBEL, J. 1997. MDS TREC 6 report. In Proceedings of the 6th Text Retreival Conference (TREC-6, Nov.), E. Voorhees and D. Harman, Eds. 241-258.
• 14: 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
• 15: HARMAN,D.AND CANDELA, G. 1990. Retrieving records from a gigabyte of text on a minicomputer using statistical ranking. J. Am. Soc. Inf. Sci. 41, 8, 581-589.
• 16: Marti A. Hearst , Christian Plaunt, Subtopic structuring for full-length document access, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.59-68, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160695]
• 17: Marcin Kaszkiel , Justin Zobel, Passage retrieval revisited, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.178-185, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 18: Mandar Mitra , Amit Singhal , Chris Buckley, Improving automatic query expansion, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290995]
• 19: Elke Mittendorf , Peter Schäuble, Document and passage retrieval based on hidden Markov models, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-327, July 03-06, 1994, Dublin, Ireland
• 20: 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]
• 21: MOFFAT, A., ZOBEL, J., AND KLEIN, S. 1995. Improved inverted file processing for large text databases. In Proceedings of the 6th Australasian Database Conference (Adelaide, Jan.), R. Sacks-Davis and J. Zobel, Eds. 162-171.
• 22: PERSIN, M. 1996. Efficient implementation of text retrieval techniques. RMIT, Melbourne, Australia.
• 23: 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]
• 24: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 25: Gerard Salton , Chris Buckley, Automatic text structuring and retrieval-experiments in automatic encyclopedia searching, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-30, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122863]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Performance

Keywords:
inverted files, passage retrieval, query evaluation, text databases, text retrieval