Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
From MaRDI portal
Publication:4962682
DOI10.1145/1290672.1290680zbMath1446.68046MaRDI QIDQ4962682
Srinivasa Rao Satti, Venkatesh Raman, Rajeev Raman
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1290672.1290680
68P05: Data structures
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Nearly Optimal Static Las Vegas Succinct Dictionary, Faster Practical Block Compression for Rank/Select Dictionaries, Optimal Skeleton Huffman Trees, Compressed Multiple Pattern Matching, Practical Compact Indexes for Top-kDocument Retrieval, m-Bonsai: A Practical Compact Dynamic Trie, Forward looking Huffman coding, Fast and compact planar embeddings, Compact representations of spatial hierarchical structures with support for topological queries, On representing the degree sequences of sublogarithmic-degree Wheeler graphs, Space-efficient data structure for next/previous larger/smaller value queries, Enumerating Range Modes, Document retrieval with one wildcard, Simultaneous encodings for range and next/previous larger/smaller value queries, Compressed property suffix trees, Entropy-bounded representation of point grids, Succinct encoding of arbitrary graphs, On compressing permutations and adaptive sorting, Top-\(k\) document retrieval in optimal space, Various improvements to text fingerprinting, Compact navigation and distance oracles for graphs with small treewidth, Efficient fully-compressed sequence representations, Optimal indexes for sparse bit vectors, Improved space-time tradeoffs for approximate full-text indexing with one edit error, I/O-efficient path traversal in succinct planar graphs, A quick tour on suffix arrays and compressed suffix arrays, Selection from read-only memory with limited workspace, Compact and succinct data structures for multidimensional orthogonal range searching, Tree path majority data structures, Lyndon array construction during Burrows-Wheeler inversion, Fixed block compression boosting in FM-indexes: theory and practice, Approximate query processing over static sets and sliding windows, Top tree compression of tries, Succinct representation for (non)deterministic finite automata, Faster compressed quadtrees, Navigating planar topologies in near-optimal space and time, Space efficient merging of de Bruijn graphs and Wheeler graphs, Adaptive succinctness, Enumeration of maximal common subsequences between two strings, An LMS-based grammar self-index with local consistency properties, Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs, Using compressed suffix-arrays for a compact representation of temporal-graphs, Optimal skeleton and reduced Huffman trees, Block trees, Succinct representations for (non)deterministic finite automata, Lempel-Ziv compressed structures for document retrieval, Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster, Space-efficient fully dynamic DFS in undirected graphs, DenseZDD: a compact and fast index for families of sets, On hardness of several string indexing problems, Top-\(k\) term-proximity in succinct space, Succinct indices for path minimum, with applications, Block graphs in practice, Range selection and predecessor queries in data aware space and time, On the succinct representation of equivalence classes, Succinct data structure for dynamic trees with faster queries, Succinct representation of labeled graphs, Succinct and I/O efficient data structures for traversal in trees, A uniform paradigm to succinctly encode various families of trees, Minimal indices for predecessor search, Space efficient data structures for nearest larger neighbor, Representation of ordered trees with a given degree distribution, Succinct encoding of binary strings representing triangulations, Faster repetition-aware compressed suffix trees based on block trees, Compact representation of graphs with bounded bandwidth or treedepth, Succinct permutation graphs, Locally Compressed Suffix Arrays, General Document Retrieval in Compact Space, From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures, Random Access to High-Order Entropy Compressed Text, Succinct and Implicit Data Structures for Computational Geometry, Space Efficient Data Structures for Nearest Larger Neighbor, Encoding range minima and range top-2 queries, Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet, Compact Navigation and Distance Oracles for Graphs with Small Treewidth, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
