skip to main content
10.1145/1772690.1772850acmotherconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
poster

An efficient random access inverted index for information retrieval

Published: 26 April 2010 Publication History

Abstract

To improve query performance and space efficiency, an efficient random access blocked inverted index (RABI) is proposed. RABI divides an inverted list into blocks and compresses different part of each block with the corresponding encoding method to decrease space consumption. RABI can provide fast addressing and random access functions on the compressed blocked inverted index with the novel hybrid compression method, which can provide both block level and inner block level skipping function and further enhance both space and time efficiencies without inserting any additional auxiliary information. Experimental results show that RABI achieves both high space efficiency and search efficiency, and outperforms the existing approach significantly.

References

[1]
J. Zobel, A. Moffat. Inverted Files for Text Search Engines. ACM Computing Surveys, 38(2): 1--56, 2006.
[2]
A. Moffat, J. Zobel. Self-Indexing Inverted Files for Fast Text Retrieval. ACM Transactions on Information Systems, 14(4): 349--379, 1996.
[3]
A. Moffat, L. Stuiver. Binary interpolative coding for effective index compression. Information Retrieval, 3(1): 25--47, 2000.
[4]
D. K. Blandford, G. E. Blelloch. Compact representations of ordered sets. In Proc. of the 15th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 11--19, 2004.
[5]
S. Buttcher, Charles L. Clarke. A. Index compression is good, especially for random access. In Proc. of the 16th ACM CIKM, pages 761--770, 2007.
[6]
J. Zhang, X. Long, T. Suel. Performance of compressed inverted list caching in search engines. In Proc. of the 17th International Conference on World Wide Web, pages 387--396, 2008.
[7]
X. Liu, Z. Peng. Time and Space Efficiencies Analysis of Full-Text Index Techniques. Journal of Software, 20(7): 1768--1784, 2009.

Cited By

View all
  • (2024)Partitioned Inverted Index Compression Using Hierarchical Dirichlet Process2024 4th International Conference on Neural Networks, Information and Communication (NNICE)10.1109/NNICE61279.2024.10499155(1433-1442)Online publication date: 19-Jan-2024
  • (2020)Pipelined Query Processing Using Non-volatile Memory SSDsWeb and Big Data10.1007/978-3-030-60290-1_35(457-472)Online publication date: 14-Oct-2020
  • (2019)A Hybrid BitFunnel and Partitioned Elias-Fano Inverted IndexThe World Wide Web Conference10.1145/3308558.3313553(1153-1163)Online publication date: 13-May-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
WWW '10: Proceedings of the 19th international conference on World wide web
April 2010
1407 pages
ISBN:9781605587998
DOI:10.1145/1772690

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 April 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. information retrieval
  2. inverted index
  3. random access

Qualifiers

  • Poster

Conference

WWW '10
WWW '10: The 19th International World Wide Web Conference
April 26 - 30, 2010
North Carolina, Raleigh, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Partitioned Inverted Index Compression Using Hierarchical Dirichlet Process2024 4th International Conference on Neural Networks, Information and Communication (NNICE)10.1109/NNICE61279.2024.10499155(1433-1442)Online publication date: 19-Jan-2024
  • (2020)Pipelined Query Processing Using Non-volatile Memory SSDsWeb and Big Data10.1007/978-3-030-60290-1_35(457-472)Online publication date: 14-Oct-2020
  • (2019)A Hybrid BitFunnel and Partitioned Elias-Fano Inverted IndexThe World Wide Web Conference10.1145/3308558.3313553(1153-1163)Online publication date: 13-May-2019
  • (2013)Uniform Storage Model-based Update Scheme of On-line Information Retrieval SystemJournal of Networks10.4304/jnw.8.9.2179-21858:9Online publication date: 10-Sep-2013

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

EPUB

View this article in ePub.

ePub

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media