On Compressing Permutations and Adaptive Sorting

Details On Compressing Permutations and Adaptive Sorting On Compressing Permutations and Adaptive Sorting

2011-08-22

arxiv.org/abs/1108.4408v1

Computer Science

Data Structures and Algorithms

Scientific paper

Previous compact representations of permutations have focused on adding a small index on top of the plain data $<\pi(1), \pi(2),...\pi(n)>$, in order to efficiently support the application of the inverse or the iterated permutation. In this paper we initiate the study of techniques that exploit the compressibility of the data itself, while retaining efficient computation of $\pi(i)$ and its inverse. In particular, we focus on exploiting {\em runs}, which are subsets (contiguous or not) of the domain where the permutation is monotonic. Several variants of those types of runs arise in real applications such as inverted indexes and suffix arrays. Furthermore, our improved results on compressed data structures for permutations also yield better adaptive sorting algorithms.

Affiliated with

Also associated with

No associations

Rating

On Compressing Permutations and Adaptive Sorting 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 On Compressing Permutations and Adaptive Sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Compressing Permutations and Adaptive Sorting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176844