Compressing term positions in web indexes

ABSTRACT

Large search engines process thousands of queries per second on billions of pages, making query processing a major factor in their operating costs. This has led to a lot of research on how to improve query throughput, using techniques such as massive parallelism, caching, early termination, and inverted index compression. We focus on techniques for compressing term positions in web search engine indexes. Most previous work has focused on compressing docID and frequency data, or position information in other types of text collections. Compression of term positions in web pages is complicated by the fact that term occurrences tend to cluster within documents but not across document boundaries, making it harder to exploit clustering effects. Also, typical access patterns for position data are different from those for docID and frequency data. We perform a detailed study of a number of existing and new techniques for compressing position data in web indexes. We also study how to efficiently access position data for ranking functions that take proximity features into account.

REFERENCES

• 1: V. Anh. Impact-based document retrieval. PhD Thesis, The University of Melbourne, Amsterdam, Netherlands, April 2004.
• 2: Vo Ngoc Anh , Alistair Moffat, Index compression using fixed binary codewords, Proceedings of the 15th Australasian database conference, p.61-67, January 01, 2004, Dunedin, New Zealand
• 3: Vo Ngoc Anh , Alistair Moffat, Inverted Index Compression Using Word-Aligned Binary Codes, Information Retrieval, v.8 n.1, p.151-166, January 2005 [doi>10.1023/B:INRT.0000048490.99518.5c]
• 4: Vo Ngoc Anh , Alistair Moffat, Improved Word-Aligned Binary Compression for Text Indexing, IEEE Transactions on Knowledge and Data Engineering, v.18 n.6, p.857-861, June 2006 [doi>10.1109/TKDE.2006.99]
• 5: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference, p.342, April 02-04, 2002
• 6: A. Bookstein , S. T. Klein , T. Raita, Modeling word occurrences for the compression of concordances, ACM Transactions on Information Systems (TOIS), v.15 n.3, p.254-290, July 1997 [doi>10.1145/256163.256166]
• 7: A. Bookstein, S. Klein, and T. Raita. Markov models for clusters in concordance compression. In Proc. of the Data Compression Conference, March, 1994.
• 8: Stefan Büttcher , Charles L. A. Clarke , Brad Lushman, Term proximity scoring for ad-hoc retrieval on very large text collections, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148285]
• 9: P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 12(3):194--203, Mar. 1975.
• 10: A. Fraenkel and S. Klein. Novel compression of sparse bit-strings--preliminary report. Combinatorial Algorithms on Words, 12:169--183, 1985.
• 11: J. Gailly. zlib compression library. Available at http://www.gzip.org/zlib/.
• 12: S. Golomb. Run-length encodingds. IEEE Transactions on Information Theory, 12(3):399--401, 1966.
• 13: S. Heman. Super-scalar database compression between ram and cpu-cache. MS Thesis, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, Netherlands, July 2005.
• 14: Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
• 15: Donald Metzler , W. Bruce Croft, A Markov random field model for term dependencies, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076115]
• 16: G. Mishne and M. Rijke. Boosting web retrieval through query operations. In Proc. of the 27th European Conference on IR Research, 2005.
• 17: Alistair Moffat , Vo Ngoc Anh, Binary codes for locally homogeneous sequences, Information Processing Letters, v.99 n.5, p.175-180, 15 September 2006 [doi>10.1016/j.ipl.2006.04.014]
• 18: A. Moffat , L. Stuiver, Exploiting clustering in inverted file Compression, Proceedings of the Conference on Data Compression, p.82, March 31-April 03, 1996
• 19: Alistair Moffat , Lang Stuiver, Binary Interpolative Coding for Effective Index Compression, Information Retrieval, v.3 n.1, p.25-47, July 2000 [doi>10.1023/A:1013002601898]
• 20: Alistair Moffat , Justin Zobel, Parameterised compression for sparse bitmaps, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.274-285, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133210]
• 21: R. Schenkel, A. Broschart, S. Hwang, M. Theobald, and G. Weikum. Efficient text proximity search. In 14th String Processing and Information Retrieval Symposium, 2007.
• 22: Falk Scholer , Hugh E. Williams , John Yiannis , Justin Zobel, Compression of inverted indexes For fast query evaluation, 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.564416]
• 23: Wann-Yun Shieh , Tien-Fu Chen , Jean Jyh-Jiun Shann , Chung-Ping Chung, Inverted file compression through document identifier reassignment, Information Processing and Management: an International Journal, v.39 n.1, p.117-131, January 2003 [doi>10.1016/S0306-4573(02)00020-1]
• 24: Fabrizio Silvestri , Salvatore Orlando , Raffaele Perego, Assigning identifiers to documents to enhance the clustering property of fulltext indexes, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009046]
• 25: Fabrizio Silvestri , Raffaele Perego , Salvatore Orlando, Assigning document identifiers to enhance compressibility of Web Search Engines indexes, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968024]
• 26: Tao Tao , ChengXiang Zhai, An exploration of proximity measures in information retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277794]
• 27: H. Williams and J. Zobel. Compressing integers for fast file access. Computer Journal, 42(3):193--201, 1999.
• 28: 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
• 29: Jiangong Zhang , Xiaohui Long , Torsten Suel, Performance of compressed inverted list caching in search engines, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367550]
• 30: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]
• 31: Marcin Zukowski , Sandor Heman , Niels Nes , Peter Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, p.59, April 03-07, 2006 [doi>10.1109/ICDE.2006.150]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
index compression, inverted index, search engines