Log-logarithmic worst-case range queries are possible in space theta(N)
From MaRDI portal
Publication:1838333
DOI10.1016/0020-0190(83)90075-3zbMath0509.68106OpenAlexW2090021115WikidataQ61051151 ScholiaQ61051151MaRDI QIDQ1838333
Publication date: 1983
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(83)90075-3
priority queuesdata structurerandom access machineVan Emde Boas treessparse tablesspecial search algorithm of Fredmann, Komolos and Szemeredistratified trees
Related Items
Computing a poset from its realizer, Order-preserving indexing, PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS, Two- and three- dimensional point location in rectangular subdivisions, Lower bounds for dynamic algorithms, Searching among intervals and compact routing tables, The heaviest induced ancestors problem: better data structures and applications, Space-Efficient Frameworks for Top- k String Retrieval, Scanline algorithms on a grid, A lower bound for finding predecessors in Yao's cell probe model, Fingerprints in compressed strings, Searching among intervals and compact routing tables, Ranking intervals under visibility constraints∗, On the succinct representation of equivalence classes, Composite Repetition-Aware Data Structures, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree, Entropy-bounded representation of point grids, On compressing and indexing repetitive sequences, On compressing permutations and adaptive sorting, Cross-document pattern matching, Efficient index for retrieving top-\(k\) most frequent documents, Absent Subsequences in Words, Internal masked prefix sums and its connection to fully internal measurement queries, Incremental hive graph, The complexity of the co-occurrence problem, The nearest colored node in a tree, Faster shortest paths in dense distance graphs, with applications, Compressed text indexing with wildcards, Gapped indexing for consecutive occurrences, Computing Longest Single-arm-gapped Palindromes in a String, Online parameterized dictionary matching with one gap, Succinct representations of permutations and functions, Order-preserving matching, Bounded ordered dictionaries in O(log log N) time and O(n) space, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Online recognition of dictionary with one gap, Fast relative Lempel-Ziv self-index for similar sequences, Faster algorithms for computing longest common increasing subsequences, Improved approximate string matching using compressed suffix data structures, Efficient Computation of 2-Covers of a String., Worst Case Efficient Single and Multiple String Matching in the RAM Model, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Efficient vertex-label distance oracles for planar graphs, Enumerating Range Modes, More efficient bottom-up multi-pattern matching in trees, Improved behaviour of tries by adaptive branching, Lower bounds for predecessor searching in the cell probe model, Range-restricted mergeable priority queues, Fast local searches and updates in bounded universes, Flexible indexing of repetitive collections, Cache-oblivious index for approximate string matching, Two-dimensional packet classification and filter conflict resolution in the internet, Opportunistic data structures for range queries, Finding longest increasing and common subsequences in streaming data, Unnamed Item, Efficient dynamic approximate distance oracles for vertex-labeled planar graphs, Biased predecessor search, A linear-space data structure for range-LCP queries in poly-logarithmic time, Compressed indexes for approximate string matching, Indexing weighted sequences: neat and efficient, Dynamic interpolation search revisited, Minimal indices for predecessor search, Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, Efficient computation of longest single-arm-gapped palindromes in a string, Unnamed Item, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Searching Long Repeats in Streams, On data structures and asymmetric communication complexity, Parallel processing can be harmful: The unusual behavior of interpolation search, Space efficient linear time algorithms for BFS, DFS and applications, Range minimum queries in minimal space, A History of Distribution-Sensitive Data Structures, A Survey on Priority Queues, Orthogonal Range Searching for Text Indexing, New trie data structures which support very fast search operations, Approximate periodicity, Algorithms for three-dimensional dominance searching in linear space., Geometric BWT: compressed text indexing via sparse suffixes and range searching, Surpassing the information theoretic bound with fusion trees, Linked dynamic tries with applications to LZ-compression in sublinear time and space, Maximal Common Subsequence Algorithms, Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms., Compressing dictionary matching index via sparsification technique, The Heaviest Induced Ancestors Problem Revisited, Optimal bounds for the predecessor problem and related problems, A comparative study of dictionary matching with gaps: limitations, techniques and challenges
Cites Work
- 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
- Understanding the complexity of interpolation search
- An algorithmic and complexity analysis of interpolation search
- A priority queue in which initialization and queue operations takeO(loglogD) time
- Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
- Design and implementation of an efficient priority queue
- Interpolation search—a log log N search
