scientific article; zbMATH DE number 2079421
From MaRDI portal
Publication:4471381
zbMath1092.68584MaRDI QIDQ4471381
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
Publication date: 28 July 2004
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Faster average case low memory semi-external construction of the Burrows-Wheeler transform ⋮ Compressed matching for feature vectors ⋮ Fast construction of wavelet trees ⋮ Lyndon array construction during Burrows-Wheeler inversion ⋮ Space-efficient indexes for forbidden extension queries ⋮ The cell probe complexity of succinct data structures ⋮ Succinct representations of weighted trees supporting path queries ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Random access to Fibonacci encoded files ⋮ GLOUDS: representing tree-like graphs ⋮ Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ Succinct posets ⋮ The myriad virtues of wavelet trees ⋮ Succinct 2D dictionary matching ⋮ Parallel lightweight wavelet tree, suffix array and FM-index construction ⋮ Range selection and predecessor queries in data aware space and time ⋮ A space efficient direct access data structure ⋮ Grammar compressed sequences with rank/select support ⋮ Approximate string matching with compressed indexes ⋮ A simple storage scheme for strings achieving entropy bounds ⋮ Computing longest (common) Lyndon subsequences ⋮ Practical space-efficient index for structural pattern matching ⋮ Compressed directed acyclic word graph with application in local alignment ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Parallel construction of succinct trees ⋮ Compact binary relation representations with rich functionality ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Entropy-bounded representation of point grids ⋮ Compressed indexes for text with wildcards ⋮ Colored range queries and document retrieval ⋮ On compressing and indexing repetitive sequences ⋮ Space-efficient data-analysis queries on grids ⋮ Edge minimization in de Bruijn graphs ⋮ On compressing permutations and adaptive sorting ⋮ Cross-document pattern matching ⋮ Improved data structures for the orthogonal range successor problem ⋮ Algorithms to compute the Burrows-Wheeler similarity distribution ⋮ Two-dimensional range successor in optimal time and almost linear space ⋮ Ultra-succinct representation of ordered trees with applications ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Bidirectional search in a string with wavelet trees and bidirectional matching statistics ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ Using compressed suffix-arrays for a compact representation of temporal-graphs ⋮ Improved algorithms for the range next value problem and applications ⋮ On optimally partitioning a text to improve its compression ⋮ Wavelet trees for all ⋮ Computing the Burrows-Wheeler transform of a string and its reverse in parallel ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Succinct data structures for flexible text retrieval systems ⋮ Optimal skeleton and reduced Huffman trees ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ Block trees ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ Simpler FM-index for parameterized string matching ⋮ Fixed block compression boosting in FM-indexes: theory and practice ⋮ Path queries on functions ⋮ 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 ⋮ On the string matching with \(k\) mismatches ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ On approximate jumbled pattern matching in strings ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ A simple algorithm for computing the document array ⋮ Distribution-aware compressed full-text indexes ⋮ Move-to-front, distance coding, and inversion frequencies revisited ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Wee LCP ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Speeding up dynamic programming in the line-constrained \(k\)-median ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Dynamic rank/select structures with applications to run-length encoded texts ⋮ Rank/select on dynamic compressed sequences and applications ⋮ The exact multiple pattern matching problem solved by a reference tree approach ⋮ Accelerated partial decoding in wavelet trees ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Selection from read-only memory with limited workspace ⋮ Speeding up Dynamic Programming in the Line-Constrained k-median ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Locally Compressed Suffix Arrays ⋮ General Document Retrieval in Compact Space ⋮ Faster entropy-bounded compressed suffix trees ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Orthogonal Range Searching for Text Indexing ⋮ Array Range Queries ⋮ Sliding suffix tree ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Geometric BWT: compressed text indexing via sparse suffixes and range searching ⋮ Adaptive succinctness ⋮ Optimal Skeleton Huffman Trees Revisited ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Compressed Data Structures for Dynamic Sequences ⋮ Unnamed Item ⋮ Bidirectional Variable-Order de Bruijn Graphs ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Efficient Data Structures for the Orthogonal Range Successor Problem ⋮ Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis ⋮ Compact Indexes for Flexible Top-$$k$$ Retrieval ⋮ Practical Wavelet Tree Construction ⋮ String Indexing with Compressed Patterns ⋮ Algorithms and complexity on indexing founder graphs ⋮ Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Random access in persistent strings and segment selection ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ Optimal Skeleton Huffman Trees ⋮ A Self-index on Block Trees ⋮ Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression ⋮ Lempel-Ziv Factorization Revisited ⋮ Succincter Text Indexing with Wildcards ⋮ Self-indexing Based on LZ77 ⋮ Counting Colours in Compressed Strings ⋮ On Wavelet Tree Construction ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ Range Majority in Constant Time and Linear Space ⋮ Compact Navigation and Distance Oracles for Graphs with Small Treewidth ⋮ Priority Queues and Sorting for Read-Only Data ⋮ Spaces, Trees, and Colors ⋮ Forty Years of Text Indexing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Unnamed Item ⋮ Structural Pattern Matching - Succinctly. ⋮ On Undetected Redundancy in the Burrows-Wheeler Transform ⋮ Practical Compact Indexes for Top-kDocument Retrieval