Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
From MaRDI portal
Publication:4828937
zbMath1093.68582arXiv0705.0552MaRDI QIDQ4828937
Venkatesh Raman, S. Srinivasa Rao, Rajeev Raman
Publication date: 29 November 2004
Full work available at URL: https://arxiv.org/abs/0705.0552
68P05: Data structures
Related Items
Spaces, Trees, and Colors, A Space-Optimal Grammar Compression., Rainbowfish: A Succinct Colored de Bruijn Graph Representation, Succinct Color Searching in One Dimension, Compressed indexes for approximate string matching, Sorting and ranking of self-delimiting numbers with applications to tree isomorphism, Succinct dynamic cardinal trees, Optimal encodings for range majority queries, Fast construction of wavelet trees, Less space: indexing for queries with wildcards, Random access to Fibonacci encoded files, Succinct posets, Compact binary relation representations with rich functionality, Compressed indexes for text with wildcards, Colored range queries and document retrieval, On compressing and indexing repetitive sequences, Ultra-succinct representation of ordered trees with applications, New algorithms on wavelet trees and applications to information retrieval, Succinct representations of permutations and functions, Succinct indexes for reporting discriminating and generic words, Efficient dynamic range minimum query, Combined data structure for previous- and next-smaller-values, Space-efficient construction of Lempel-Ziv compressed text indexes, Implicit \(B\)-trees: A new data structure for the dictionary problem, Finding range minima in the middle: approximations and applications, Succinct data structures for searchable partial sums with optimal worst-case performance, Dynamic rank/select structures with applications to run-length encoded texts, Rank/select on dynamic compressed sequences and applications, A simple optimal representation for balanced parentheses, A simple storage scheme for strings achieving entropy bounds, Encoding 2D range maximum queries, Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees, Succinct data structures for flexible text retrieval systems, Improved approximate string matching using compressed suffix data structures, On compact representations of all-pairs-shortest-path-distance matrices, Faster entropy-bounded compressed suffix trees, Approximate string matching with compressed indexes, Practical compressed suffix trees, High-order entropy compressed bit vectors with rank/select, siEDM: an efficient string index and search algorithm for edit distance with moves, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, Indexing and querying character sets in one- and two-dimensional words, Dynamic path queries in linear space, New space/time tradeoffs for top-\(k\) document retrieval on sequences, Compact structure for sparse undirected graphs based on a clique graph partition, Rank and select operations on a word, Accelerated partial decoding in wavelet trees, Improved and extended locating functionality on compressed suffix arrays, Bottom-\(k\) document retrieval, The myriad virtues of wavelet trees, A space efficient direct access data structure, Grammar compressed sequences with rank/select support, Stronger Lempel-Ziv based compressed text indexing, Compressed text indexing with wildcards, A uniform paradigm to succinctly encode various families of trees, Wavelet trees for all, A simpler analysis of Burrows-Wheeler-based compression, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Compressed data structures: Dictionaries and data-aware measures, Rank and select revisited and extended, Optimal lower bounds for rank and select indexes, GLOUDS: representing tree-like graphs, Fully Functional Static and Dynamic Succinct Trees, Succinct Representations of Ordinal Trees, Compact Indexes for Flexible Top-$$k$$ Retrieval, Faster Lightweight Lempel-Ziv Parsing, A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs, Succincter Text Indexing with Wildcards, Self-indexing Based on LZ77, LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations, Self-indexed Text Compression Using Straight-Line Programs, Space-Efficient Frameworks for Top- k String Retrieval, Access, Rank, and Select in Grammar-compressed Strings, A Uniform Approach Towards Succinct Representation of Trees, Succinct Representations of Arbitrary Graphs
