Efficient phrase querying with an auxiliary index

ABSTRACT

Search engines need to evaluate queries extremely fast, a challenging task given the vast quantities of data being indexed. A significant proportion of the queries posed to search engines involve phrases. In this paper we consider how phrase queries can be efficiently supported with low disk overheads. 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. We propose a combination of nextword indexes with inverted files as a solution to this problem. Our experiments show that combined use of an auxiliary nextword index and a conventional inverted file allow evaluation of phrase queries in half the time required to evaluate such queries with an inverted file alone, and the space overhead is only 10% of the size of the inverted file. Further time savings are available with only slight increases in disk requirements.

References

1. V. N. Anh, O. Kretser, and A. Moffat. Vector-Space ranking with effective early termination. In W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, editors, Proc. ACM-SIGIR International Conference on Research and Development in Information Retrieval, pages 35--42, New York, Sept. 2001.
2. D. Bahle, H.E. Williams, and J. Zobel. Compaction techniques for nextword indexes. In Proc. 8th International Symposium on String Processing and Information Retrieval (SPIRE2001), pages 33--45, San Rafael, Chile, 2001.
3. D. Bahle, H. E. Williams, and J. Zobel. Optimised phrase querying and browsing in text databases. In M. Oudshoorn, editor, Proc. Australasian Computer Science Conference, pages 11--19, Gold Coast, Australia, Jan. 2001.
4. P. Bruza, R. McArthur, and S. Dennis. Interactive internet search: keyword, directory and query reformulation mechanisms compared. In N. J. Belkin, P. Ingwersen, and M.-K. Leong, editors, Proc. ACM-SIGIR International Conference on Research and Development in Information Retrieval, pages 280--287, Athens, 2000.
5. C. L. Clarke, G. V. Cormack, and E. A. Tudhope. Relevance ranking for one- to three-term queries. In Proc. of RIAO-97, 5th International Conference "Recherche d'Information Assistee par Ordinateur", pages 388--400, Montreal, CA, 1997.
6. W. B. Croft, H. R. Turtle, and D. D. Lewis. The use of phrases and structured queries in information retrieval. In A. Bookstein, Y. Chiaramella, G. Salton, and V. V. Raghavan, editors, Proc. ACM-SIGIR International Conference on Research and Development in Information Retrieval, pages 32--45, Chicago, 1991.
7. E. F. de Lima and J. O. Pedersen. Phrase recognition and expansion for short, precision-biased queries based on a query log. In Proc. ACM-SIGIR International Conference on Research and Development in Information Retrieval, pages 145--152, Berkeley, 1999.
8. C. Gutwin, G. Paynter, I. Witten, C. NevillManning, and E. Frank. Improving browsing in digital libraries with keyphrase indexes. Decision Support Systems, 27(1/2):81--104, 1998.
9. D. Hawking, N. Craswell, P. Thistlewaite, and D. Harman. Results and challenges in web search evaluation. In Proc. of the Eighth International World-Wide Web Conference, volume 31, pages 1321--1330, May 1999.
10. D. D. Lewis and W. B. Croft. Term clustering of syntactic phrases. In J.-L. Vidick, editor, Proc. ACM-SIGIR International Conference on Research and Development in Information Retrieval, pages 385--404, 1990.
11. A. Moffat and J. Zobel. Self-indexing inverted files for fast text retrieval. ACM Transactions on Information Systems, 14(4):349--379, 1996.
12. G. W. Paynter, I. H. Witten, S. J. Cunningham, and G. Buchanan. Scalable browsing for large collections: A case study. In Proc. of the 5th ACM International Conference on Digital Libraries, pages 215--223, San Antonio, 2000.
13. M. Persin, J. Zobel, and R. Sacks-Davis. Filtered document retrieval with frequency-sorted indexes. Journal of the American Society for Information Science, 47(10):749--764, 1996.
14. A. Spink, D. Wolfram, B. J. Jansen, and T. Saracevic. Searching the web: The public and their queries. Journal of the American Society for Information Science, 52(3):226--234, 2001.
15. H. Williams, J. Zobel, and P. Anderson. What's next? index structures for efficient phrase querying. In M. Orlowska, editor, Proc. Australasian Database Conference, pages 141--152, Auckland, New Zealand, 1999.
16. I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, San Francisco, California, second edition, 1999.
17. J. Zobel and A. Moffat. Exploring the similarity space. SIGIR Forum, 32(1):18--34, 1998.

Index Terms

• Information systems

  • Information retrieval

    • Evaluation of retrieval results

  • Information storage systems

    • Record storage systems

      • Record storage alternatives