Inverted index compression and query processing with optimized document ordering

ABSTRACT

Web search engines use highly optimized compression schemes to decrease inverted index size and improve query throughput, and many index compression techniques have been studied in the literature. One approach taken by several recent studies first performs a renumbering of the document IDs in the collection that groups similar documents together, and then applies standard compression techniques. It is known that this can significantly improve index compression compared to a random document ordering. We study index compression and query processing techniques for such reordered indexes. Previous work has focused on determining the best possible ordering of documents. In contrast, we assume that such an ordering is already given, and focus on how to optimize compression methods and query processing for this case. We perform an extensive study of compression techniques for document IDs and present new optimizations of existing techniques which can achieve significant improvement in both compression and decompression performances. We also propose and evaluate techniques for compressing frequency values for this case. Finally, we study the effect of this approach on query processing performance. Our experiments show very significant improvements in index size and query processing speed on the TREC GOV2 collection of 25.2 million web pages.

REFERENCES

• 1: 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
• 2: 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]
• 3: 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]
• 4: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 5: Klaus Berberich , Srikanta Bedathur , Thomas Neumann , Gerhard Weikum, A time machine for text search, 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.1277831]
• 6: R. Blanco and A. Barreiro. Document identifier reassignment through dimensionality reduction. In Proc. of the 27th European Conf. on Information Retrieval, pages 375--387, 2005.
• 7: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference, p.342, April 02-04, 2002
• 8: P. Boldi and S. Vigna. Compressed perfect embedded skip lists for quick inverted-index lookups. In Proc. of the 12th Int. Conf. on String Processing and Information Retrieval, 2005.
• 9: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 10: Andrei Z. Broder , David Carmel , Michael Herscovici , Aya Soffer , Jason Zien, Efficient query evaluation using a two-level retrieval process, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956944]
• 11: A. Broder, N. Eiron, M. Fontoura, M. Herscovici, R. Lempel, J. McPherson, R. Qi, and E. Shekita. Indexing shared content in information retrieval systems. In Proc. of the 10th Int. Conf. on Extending Database Technology, pages 313--330, 2006.
• 12: Flavio Chierichetti , Silvio Lattanzi , Federico Mari , Alessandro Panconesi, On placing skips optimally in expectation, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341537]
• 13: Ronald Fagin, Combining fuzzy information: an overview, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565143]
• 14: S. Heman. Super-scalar database compression between RAM and CPU-cache. MS Thesis, Centrum voor Wiskunde en Informatica, Amsterdam, Netherlands, July 2005.
• 15: M. Herscovici, R. Lempel, and S. Yogev. Efficient indexing of versioned document sequences. In Proc. of the 29th European Conf. on Information Retrieval, 2007.
• 16: Xiaohui Long , Torsten Suel, Optimized query execution in large search engines with global page ordering, Proceedings of the 29th international conference on Very large data bases, p.129-140, September 09-12, 2003, Berlin, Germany
• 17: 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]
• 18: 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]
• 19: 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]
• 20: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 21: Knut Magne Risvik , Yngve Aasheim , Mathias Lidal, Multi-Tier Architecture for Web Search Engines, Proceedings of the First Conference on Latin American Web Congress, p.132, November 10-12, 2003
• 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: F. Silvestri. Sorting out the document identifier assignment problem. In Proc. of 29th European Conf. on Information Retrieval, pages 101--112, 2007.
• 25: 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]
• 26: 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
• 27: 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]
• 28: Jiangong Zhang , Torsten Suel, Efficient search in large textual collections with redundancy, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242628]
• 29: 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]
• 30: 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:
IR query processing, document ordering, index compression, inverted index, search engines