Inverted index compression and query processing with optimized document ordering Export

@inproceedings{citeulike:5183019, 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.}, address = {New York, NY, USA}, author = {Yan, Hao and Ding, Shuai and Suel, Torsten}, booktitle = {WWW '09: Proceedings of the 18th international conference on World wide web}, citeulike-article-id = {5183019}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1526764}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1526709.1526764}, doi = {10.1145/1526709.1526764}, isbn = {978-1-60558-487-4}, keywords = {2009, compression, inverted\_index, pfor, trec, www}, location = {Madrid, Spain}, pages = {401--410}, posted-at = {2009-10-06 11:26:54}, priority = {2}, publisher = {ACM}, title = {Inverted index compression and query processing with optimized document ordering}, url = {http://dx.doi.org/10.1145/1526709.1526764}, year = {2009} }

TY - CONF ID - citeulike:5183019 L3 - citeulike-article-id:5183019 N2 - 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. CY - Madrid, Spain SN - 978-1-60558-487-4 AD - New York, NY, USA EP - 410 TI - Inverted index compression and query processing with optimized document ordering PB - ACM T2 - WWW '09: Proceedings of the 18th international conference on World wide web SP - 401 KW - 2009 KW - compression KW - inverted_index KW - pfor KW - trec KW - www AU - Yan, Hao AU - Ding, Shuai AU - Suel, Torsten PY - 2009/// UR - http://dx.doi.org/10.1145/1526709.1526764 ER -