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