Re-Pair Compression of Inverted Lists

Details Re-Pair Compression of Inverted Lists Re-Pair Compression of Inverted Lists

2009-11-17

arxiv.org/abs/0911.3318v1

Computer Science

Information Retrieval

Scientific paper

Compression of inverted lists with methods that support fast intersection operations is an active research topic. Most compression schemes rely on encoding differences between consecutive positions with techniques that favor small numbers. In this paper we explore a completely different alternative: We use Re-Pair compression of those differences. While Re-Pair by itself offers fast decompression at arbitrary positions in main and secondary memory, we introduce variants that in addition speed up the operations required for inverted list intersection. We compare the resulting data structures with several recent proposals under various list intersection algorithms, to conclude that our Re-Pair variants offer an interesting time/space tradeoff for this problem, yet further improvements are required for it to improve upon the state of the art.

Affiliated with

Also associated with

No associations

Rating

Re-Pair Compression of Inverted Lists does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Re-Pair Compression of Inverted Lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Re-Pair Compression of Inverted Lists will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650744