Academic
Publications
Compressed Representations of Permutations, and Applications

Compressed Representations of Permutations, and Applications,10.4230/LIPIcs.STACS.2009.1814,Computing Research Repository,Jérémy Barbay,Gonzalo Navarr

Compressed Representations of Permutations, and Applications   (Citations: 13)
BibTex | RIS | RefWorks Download
We explore various techniques to compress a permutation overn integers, taking advantage of ordered subsequences in , while supporting its application (i) and the application of its inverse 1(i) in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications k(i) of it, of integer functions, and of inverted lists and sux arrays.
Journal: Computing Research Repository - CORR , vol. abs/0902.1, pp. 111-122, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...This improves or gives alternatives to the best previous results [4,17,12]...
    • ...We follow Barbay and Navarro’s notation [4] and improve their space and, especially, their time performance...
    • ...Let π be covered by ρ runs (using any of the previous definitions of runs [13,4,16]) of lengths runs(π )= � n1 ,...,n ρ� .T hen H(runs(π)) = n...
    • ...ni ≤ lg ρ is called the entropy of the runs (and, because ni ≥ 1, it also holds nH(runs(π)) ≥ (ρ − 1) lg n). We first consider permutations which are interleaved sequences of increasing or decreasing values as first defined by Levcopoulos et al. [13] for adaptive sorting, and later on for compression [4], and then give improved results for more specific classes of runs...

    Jérémy Barbayet al. Alphabet Partitioning for Compressed Rank/Select and Applications

    • ...Formally in the literature, the default map is called an ordered set (i.e., dictionary) and maps not satisfying the previous property are called unordered [5]...
    • ...called Wavelet Tree on Runs [5] that compresses the permutation and provides fast computation of �(i) and � 1 (i)...
    • ...J´er´emy and Gonzalo [5] have studied several techniques to compress a permutation and suggested three solutions: Wavelet Tree on Runs (WTR), Stricter Runs and Shuffled Sequences...
    • ...WTR which is based on the reverse of the merge sort algorithm, takes advantage of ordered subsequences in � performs �(i) and � 1 (i) in (1 + log�) time using nd lg�e (1 + o(1)) + (lg(n)) bits, where � represents number of runs in the permutation [5]...

    Humaira Kamalet al. Scalability of communicators and groups in MPI

    • ...Wavelet trees are not only used to represent strings [14], but also grids [7], permutations [5], and many other structures...

    Jérémy Barbayet al. Compact Rich-Functional Binary Relation Representations

    • ...[23,30,26]), binary relations and permutations (see e.g. [11,9]), and many others...

    Paolo Ferragina. Data Structures: Time, I/Os, Entropy, Joules

    • ...In the same way the range [2, 4] of the left child is projected onto its children as [rank1(B1, 2 − 1) + 1 ,r ank1(B1, 4)] = [1, 1] and [rank1(B2, 2 − 1) + 1 ,r ank1(B2, 4)] = [2, 4]. In the next level, the first node accessed is the second one that covers the range [3,4]...
    • ...In the same way the range [2, 4] of the left child is projected onto its children as [rank1(B1, 2 − 1) + 1 ,r ank1(B1, 4)] = [1, 1] and [rank1(B2, 2 − 1) + 1 ,r ank1(B2, 4)] = [2, 4]. In the next level, the first node accessed is the second one that covers the range [3,4]...
    • ...In the parent of this node, there are no local results and the left result ([1]) and right result ([2]) reference the same MBR (select1(B1, 1) = select1(B2, 2) = 2). Finally, in the root node the result comes Compact Data Structure for Indexing Geographic Data 83...
    • ...a permutation Π over {1 ...N } into the minimum number of Shuffled (i.e., not consecutive) UpSequences [1] (the rightmost values of the MBRs correspond to the permutation values)...

    Nieves R. Brisaboaet al. A Fun Application of Compact Data Structures to Indexing Geographic Da...

Sort by: