Should Tables Be Sorted?
Andrew Chi-Chih Yao · Journal of the ACM · 1981
Optmaahty questions are examined m the following information retrieval problem.Given a set S of n keys, store them so that queries of the form, "Is x E S?" can be answered quickly It is shown that m a rather general model including all the commonly used schemes, [lg(n + I)] probes to the table are needed m the worst case, prowded the key space is sufficiently large The effects of smaller key space and arbitrary encoding are also explored KEY WORDS AND PHRASES mformaUon retrieval, lower bound, optmaahty, query, Ramsey's theorem, search strategy, sorted table
Cited by 345 works. doi:10.1145/322261.322274 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- The Art of Computer Programming: Volume 3: Sorting and Searching
- Graphs and Hypergraphs
- The art of computer programming. Vol.3: Sorting and searching
- Geometric complexity
- Multidimensional Searching Problems
- Perfect hashing functions
- Design and implementation of an efficient priority queue
- Storing a sparse table