Fast phrase querying with combined indexes

ABSTRACT

Search engines need to evaluate queries extremely fast, a challenging task given the quantities of data being indexed. A significant proportion of the queries posed to search engines involve phrases. In this article we consider how phrase queries can be efficiently supported with low disk overheads. Our previous research has shown that phrase queries can be rapidly evaluated using nextword indexes, but these indexes are twice as large as conventional inverted files. Alternatively, special-purpose phrase indexes can be used, but it is not feasible to index all phrases. We propose combinations of nextword indexes and phrase indexes with inverted files as a solution to this problem. Our experiments show that combined use of a partial nextword, partial phrase, and conventional inverted index allows evaluation of phrase queries in a quarter the time required to evaluate such queries with an inverted file alone; the additional space overhead is only 26% of the size of the inverted file.

REFERENCES

• 1: Vo Ngoc Anh , Owen de Kretser , Alistair Moffat, Vector-space ranking with effective early termination, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.35-42, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383957]
• 2: Bahle, D. 2003. Efficient phrase querying. Ph.D. dissertation. School of Computer Science and Information Technology, RMIT, Melbourne, Australia.
• 3: Bahle, D., Williams, H. E., and Zobel, J. 2001a. Compaction techniques for nextword indexes. In Proceedings of the String Processing and Information Retrieval Symposium (San Rafael, Chile). IEEE Computer Society Press, Los Alamitos, CA, 33--45.
• 4: Dirk Bahle , Hugh E. Williams , Justin Zobel, Optimised phrase querying and browsing of large text databases, Proceedings of the 24th Australasian conference on Computer science, p.11-19, January 29-February 02, 2001, Gold Coast, Queensland, Australia
• 5: Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
• 6: Clarke, C. L., Cormack, G. V., and Tudhope, E. A. 1997. Relevance ranking for one- to three-term queries. In Proceedings of the Fifth RIAO International Conference "Recherche d'Information Assistee par Ordinateur" (Montreal P.Q., Canada). 388--400.
• 7: W. Bruce Croft , Howard R. Turtle , David D. Lewis, The use of phrases and structured queries in information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.32-45, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122864]
• 8: Erika F. de Lima , Jan O. Pedersen, Phrase recognition and expansion for short, precision-biased queries based on a query log, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.145-152, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312669]
• 9: Carl Gutwin , Gordon Paynter , Ian Witten , Craig Nevill-Manning , Eibe Frank, Improving browsing in digital libraries with keyphrase indexes, Decision Support Systems, v.27 n.1-2, p.81-104, Nov. 1999 [doi>10.1016/S0167-9236(99)00038-X]
• 10: 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
• 11: Bernard J. Jansen , Udo Pooch, A review of web searching studies and a framework for future research, Journal of the American Society for Information Science and Technology, v.52 n.3, p.235-246, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1607>3.3.CO;2-6]
• 12: D. D. Lewis , W. B. Croft, Term clustering of syntactic phrases, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.385-404, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98244]
• 13: 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]
• 14: Gordon W. Paynter , Ian H. Witten , Sally Jo Cunningham , George Buchanan, Scalable browsing for large collections: a case study, Proceedings of the fifth ACM conference on Digital libraries, p.215-223, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336666]
• 15: 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]
• 16: Paricia Correia Saraiva , Edleno Silva de Moura , Novio Ziviani , Wagner Meira , Rodrigo Fonseca , Berthier Riberio-Neto, Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.51-58, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383959]
• 17: Ian Soboroff, Does WT10g look like the web?, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564475]
• 18: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 19: Spink, A. and Xu, J. 2000. Selected results from a large study of Web searching: The Excite study. Informat. Res. 6, 1. Available online at: http://InformationR.net/ir/6-1/paper90.html.
• 20: Voorhees, E. M. and Harman, D. K. 2001. Overview of TREC 2001. In The Tenth Text REtrieval Conference (TREC 2001), E. M. Voorhees and D. K. Harman, Eds. NIST Spec. pub. 500-250. National Institute of Standards and Technology, Gaithersburg, MD, 1--15.
• 21: Williams, H. E. and Zobel, J. 1999. Compressing integers for fast file access. Comput. J. 42, 3, 193--201.
• 22: Williams, H. E., Zobel, J., and Anderson, P. 1999. What's next? Index structures for efficient phrase querying. In Proceedings of the Australasian Database Conference (Auckland, New Zealand), M. Orlowska, Ed. Springer-Verlag, Berlin, Germany, 141--152.
• 23: 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
• 24: 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]
• 25: Justin Zobel , Steffen Heinz , Hugh E. Williams, In-memory hash tables for accumulating text vocabularies, Information Processing Letters, v.80 n.6, p.271-277, December 2001 [doi>10.1016/S0020-0190(01)00239-3]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Performance

Keywords:
Nextword indexes, Web search, phrase queries, query evaluation