Should Tables Be Sorted?
From MaRDI portal
Publication:3912073
DOI10.1145/322261.322274zbMath0462.68079OpenAlexW1993022201MaRDI QIDQ3912073
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322261.322274
Related Items
A strong lower bound for approximate nearest neighbor searching, Improved bounds for dictionary look-up with one error, A logarithmic lower bound for oblivious RAM (for all Parameters), Lower bounds for dynamic transitive closure, planar point location, and parentheses matching, Approximate distributed top-\(k\) queries, Lower bounds for dynamic algorithms, Tables should be sorted (on random access machines), An algorithm for finding predecessors in integer sets, Integer representation and counting in the bit probe model, Searching among intervals and compact routing tables, The problem of space invariance for sequential machines, A tradeoff between search and update time for the implicit dictionary problem, A lower bound for finding predecessors in Yao's cell probe model, Searching among intervals and compact routing tables, Nearly Optimal Static Las Vegas Succinct Dictionary, Construction of universal enumerators and formulas for threshold functions, The function-inversion problem: barriers and opportunities, New amortized cell-probe lower bounds for dynamic problems, Limits of breach-resistant and snapshot-oblivious RAMs, Low-contention data structures, Forward secret encrypted RAM: lower bounds and applications, On the time-space complexity of reachability queries for preprocessed graphs, Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds, Integer representations towards efficient counting in the bit probe model, Increasing the Output Length of Zero-Error Dispersers, Integer Representation and Counting in the Bit Probe Model, Maintaining bridge-connected and biconnected components on-line, On the cell probe complexity of polynomial evaluation, Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity, Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model, Lower Bounds for External Memory Integer Sorting via Network Coding, HYPERGRAPH RAMSEY NUMBERS AND ADIABATIC QUANTUM ALGORITHM, Lower bounds for predecessor searching in the cell probe model, Determining membership with 2 simultaneous queries, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Shortest-path queries in static networks, On the Size of Separating Systems and Families of Perfect Hash Functions, Recursive bounds for perfect hashing, Applications of Ramsey theory, Dispersing hash functions, Cell-probe lower bounds for the partial match problem, Polynomial hash functions are reliable, Orthogonal range searching in linear and almost-linear space, Unnamed Item, Upper and Lower Bounds on the Power of Advice, Optimal rank and select queries on dictionary-compressed text, On data structures and asymmetric communication complexity, Unnamed Item, A Survey of Data Structures in the Bitprobe Model, Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model, Storing information with extractors., Some nonstandard Ramsey like applications, Partial match retrieval in implicit data structures, Two results on tables, Optimal bounds for the predecessor problem and related problems
