The string B-tree

DOI10.1145/301970.301973zbMath1065.68518OpenAlexW2087721273MaRDI QIDQ3158537

Paolo Ferragina, Roberto Grossi

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301970.301973

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Extended suffix array construction using Lyndon factors ⋮ Top-\(k\) term-proximity in succinct space ⋮ A FAST TECHNIQUE FOR DERIVING FREQUENT STRUCTURED PATTERNS FROM BIOLOGICAL DATA SETS ⋮ Space-efficient B trees via load-balancing ⋮ On the weak prefix-search problem ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ ISB-tree: A new indexing scheme with efficient expected behaviour ⋮ Ranked Document Retrieval in External Memory ⋮ Compressed string dictionaries via data-aware subtrie compaction ⋮ On the Longest Common Parameterized Subsequence ⋮ I/O efficient dynamic data structures for longest prefix queries ⋮ Two-dimensional substring indexing. ⋮ Online parameterized dictionary matching with one gap ⋮ Worst-case efficient single and multiple string matching on packed texts in the word-RAM model ⋮ I/O-efficient data structures for non-overlapping indexing ⋮ Parameterized dictionary matching and recognition with one gap ⋮ Worst Case Efficient Single and Multiple String Matching in the RAM Model ⋮ On the Weak Prefix-Search Problem ⋮ Efficient processing of substring match queries with inverted variable-length gram indexes ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Faster query algorithms for the text fingerprinting problem ⋮ Cache-oblivious index for approximate string matching ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS ⋮ Minimal indices for predecessor search ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Permuted Longest-Common-Prefix Array ⋮ Fast Compressed Tries through Path Decompositions ⋮ On the longest common parameterized subsequence ⋮ Distributed suffix trees ⋮ Geometric BWT: compressed text indexing via sparse suffixes and range searching ⋮ Faster Compressed Suffix Trees for Repetitive Collections ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space ⋮ Worst-case optimal tree layout in external memory ⋮ Compressing dictionary matching index via sparsification technique ⋮ Space-efficient substring occurrence estimation ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges