LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations

Details LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations

2010-09-29

arxiv.org/abs/1009.5863v1

Computer Science

Data Structures and Algorithms

13 pages, 1 figure

Scientific paper

LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks, and to express the relative position of the first element of each block within a previous block. They were used to encode ordinal trees and to index integer arrays in order to support range minimum queries on them. We describe how they yield many other convenient results in a variety of areas, from data structures to algorithms: some compressed succinct indices for range minimum queries; a new adaptive sorting algorithm; and a compressed succinct data structure for permutations supporting direct and indirect application in time all the shortest as the permutation is compressible.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523619