New trie data structures which support very fast search operations
From MaRDI portal
Publication:794438
DOI10.1016/0022-0000(84)90020-5zbMath0541.68037OpenAlexW2046569047MaRDI QIDQ794438
Publication date: 1984
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(84)90020-5
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items (18)
An old sub-quadratic algorithm for finding extremal sets ⋮ Scanline algorithms on a grid ⋮ Approximate covering detection among content-based subscriptions using space filling curves ⋮ Ranking intervals under visibility constraints∗ ⋮ An improved scheme for set equality testing and updating ⋮ Palindrome pattern matching ⋮ Bounded ordered dictionaries in O(log log N) time and O(n) space ⋮ A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Improved behaviour of tries by adaptive branching ⋮ Range-restricted mergeable priority queues ⋮ Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Parallel processing can be harmful: The unusual behavior of interpolation search ⋮ Log-logarithmic worst-case range queries are possible in space theta(N) ⋮ Finding extremal sets in less than quadratic time ⋮ Surpassing the information theoretic bound with fusion trees ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space
Cites Work
- Unnamed Item
- Unnamed Item
- Preserving order in a forest in less than logarithmic time and linear space
- Understanding the complexity of interpolation search
- An algorithmic and complexity analysis of interpolation search
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Storing a sparse table
- A priority queue in which initialization and queue operations takeO(loglogD) time
- New Data Structures for Orthogonal Range Queries
- Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
- Polygon Retrieval
- Design and implementation of an efficient priority queue
- Interpolation search—a log log N search
- Binary Search Trees of Bounded Balance
This page was built for publication: New trie data structures which support very fast search operations
