Heavy-tailed distributions and multi-keyword queries

ABSTRACT

Intersecting inverted indexes is a fundamental operation for many applications in information retrieval and databases. Efficient indexing for this operation is known to be a hard problem for arbitrary data distributions. However, text corpora used in Information Retrieval applications often have convenient power-law constraints (also known as Zipf's Law and long tails) that allow us to materialize carefully chosen combinations of multi-keyword indexes, which significantly improve worst-case performance without requiring excessive storage. These multi-keyword indexes limit the number of postings accessed when computing arbitrary index intersections. Our evaluation on an e-commerce collection of 20 million products shows that the indexes of up to four arbitrary keywords can be intersected while accessing less than 20% of the postings in the largest single-keyword index.

REFERENCES

• 1: http://shopping.msn.com/.
• 2: Polarity dataset v2.0. http://www.cs.cornell.edu/people/pabo/movie-review-data/.
• 3: 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]
• 4: H. Baayen. Word Frequency Distributions, volume 18 of Text, Speech and Language Technology. Kulver Academic Publishers, 2001.
• 5: Dirk Bahle , Hugh E. Williams , Justin Zobel, Efficient phrase querying with an auxiliary index, 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.564415]
• 6: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceedings of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 7: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 8: T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780639]
• 9: P. Li, T. Hastie, and K. W. Church. Using Sketches to Estimate Two-Way and Multi-Way Associations. Technical report, Microsoft Research, 2006.
• 10: P. Li, K. W. Church and T. Hastie. Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data. NIPS, 2006.
• 11: 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]
• 12: Hugh E. Williams , Justin Zobel , Dirk Bahle, Fast phrase querying with combined indexes, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.573-594, October 2004 [doi>10.1145/1028099.1028102]
• 13: 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
• 14: Yahoo. Analysts day report. available at http://yhoo.client.shareholder.com/downloads/2006AnalystsDay.pdf, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
heavy-tailed, index, information retrieval, partial match, power law