Storing a Sparse Table with 0 (1) Worst Case Access Time
From MaRDI portal
Publication:3766870
DOI10.1145/828.1884zbMath0629.68068OpenAlexW2165621523WikidataQ56021017 ScholiaQ56021017MaRDI QIDQ3766870
Michael L. Fredman, Endre Szemerédi, János Komlós
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/828.1884
Related Items (only showing first 100 items - show all)
Counting Subgraphs in Degenerate Graphs ⋮ Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions ⋮ Sorting and searching revisted ⋮ Stochastic analysis of dynamic processes ⋮ Two- and three- dimensional point location in rectangular subdivisions ⋮ Tables should be sorted (on random access machines) ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ The log-star revolution ⋮ A perfect parallel dictionary ⋮ Trans-dichotomous algorithms without multiplication — some upper and lower bounds ⋮ Reverse-Safe Text Indexing ⋮ String Indexing with Compressed Patterns ⋮ Secure two-party input-size reduction: challenges, solutions and applications ⋮ Near-optimal search time in \(\delta \)-optimal space, and vice versa ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Graphs, hypergraphs and hashing ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Elastic-degenerate string matching with 1 error ⋮ m-Bonsai: A Practical Compact Dynamic Trie ⋮ FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE ⋮ Dilation-Optimal Edge Deletion in Polygonal Cycles ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Longest Common Factor After One Edit Operation ⋮ Preconditioning for the Geometric Transportation Problem ⋮ Representing graphs implicitly using almost optimal space ⋮ Slightly Superexponential Parameterized Problems ⋮ Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Unnamed Item ⋮ Faster algorithms for 1-mappability of a sequence ⋮ Polynomial hash functions are reliable ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Optimal Higher Order Delaunay Triangulations of Polygons ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Circular pattern matching with \(k\) mismatches ⋮ Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Upper tail analysis of bucket sort and random tries ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Real-Time Streaming Multi-Pattern Search for Constant Alphabet ⋮ Two-way chaining for non-uniform distributions ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces ⋮ Unnamed Item ⋮ ANN for time series under the Fréchet distance ⋮ Improved bounds for dictionary look-up with one error ⋮ The cell probe complexity of succinct data structures ⋮ Information compression and Varshamov-Gilbert bound ⋮ Searching among intervals and compact routing tables ⋮ An Efficient Trie Construction for Natural Language Dictionaries ⋮ The problem of space invariance for sequential machines ⋮ A simple optimal representation for balanced parentheses ⋮ A construction method for optimally universal hash families and its consequences for the existence of RBIBDs ⋮ Certifying equality with limited interaction ⋮ String indexing for top-\(k\) close consecutive occurrences ⋮ Implicit \(B\)-trees: A new data structure for the dictionary problem ⋮ Construct a perfect word hash function in time independent of the size of integers ⋮ Permuted function matching ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Space-time trade-offs for finding shortest unique substrings and maximal unique matches ⋮ Longest Common Extensions in Trees ⋮ Alphabet-Dependent String Searching with Wexponential Search Trees ⋮ On the power of unambiguity in log-space ⋮ Minimal and Monotone Minimal Perfect Hash Functions ⋮ Succinct encoding of arbitrary graphs ⋮ Perfect hashing ⋮ Flash memory efficient LTL model checking ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ An improved version of cuckoo hashing: average case analysis of construction cost and search operations ⋮ Unnamed Item ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ The nearest colored node in a tree ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Representing shared data on distributed-memory parallel computers ⋮ Low-contention data structures ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Gapped indexing for consecutive occurrences ⋮ Minimal perfect hashing in polynomial time ⋮ Smaller representation of finite state automata ⋮ Bounded ordered dictionaries in O(log log N) time and O(n) space ⋮ Dynamic and internal longest common substring ⋮ Worst-case efficient single and multiple string matching on packed texts in the word-RAM model ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ Algorithmic complexity of protein identification: Combinatorics of weighted strings ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Simple fast parallel hashing ⋮ A Constructive Arboricity Approximation Scheme ⋮ Worst Case Efficient Single and Multiple String Matching in the RAM Model ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ A subquadratic algorithm for 3XOR ⋮ On-line weighted pattern matching ⋮ On the cell probe complexity of polynomial evaluation ⋮ Substring Range Reporting ⋮ A practical method for implementing string pattern matching machines ⋮ Index structures for fast similarity search for binary vectors ⋮ On a compaction theorem of Ragde ⋮ Substring range reporting
This page was built for publication: Storing a Sparse Table with 0 (1) Worst Case Access Time
