Bounded ordered dictionaries in O(log log N) time and O(n) space
From MaRDI portal
Publication:915434
DOI10.1016/0020-0190(90)90022-PzbMath0702.68042OpenAlexW2089439745WikidataQ56018871 ScholiaQ56018871MaRDI QIDQ915434
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90022-p
Related Items
Two- and three- dimensional point location in rectangular subdivisions, Fast and compact regular expression matching, An algorithm for finding predecessors in integer sets, Fingerprints in compressed strings, Incremental hive graph, Using persistent data structures for adding range restrictions to searching problems, On the longest upsequence problem for permutations, Substring range reporting, Four results on randomized incremental constructions, Dynamic relative compression, dynamic partial sums, and substring concatenation, Point location in fat subdivisions, Biased predecessor search, A new metric between polygons, and how to compute it, Four results on randomized incremental constructions, Algorithms for three-dimensional dominance searching in linear space., Optimal Partition of a Bipartite Graph with Prescribed Layout into Non-Crossing b-Matchings, Efficient labelling algorithms for the maximum noncrossing matching problem, Linked dynamic tries with applications to LZ-compression in sublinear time and space
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- New trie data structures which support very fast search operations
- Preserving order in a forest in less than logarithmic time and linear space
- Log-logarithmic worst-case range queries are possible in space theta(N)
- A priority queue in which initialization and queue operations takeO(loglogD) time
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Design and implementation of an efficient priority queue
