Storing a sparse table
Robert Endre Tarjan, Andrew Chi-Chih Yao · Communications of the ACM · 1979
The problem of storing and searching large sparse tables is ubiquitous in computer science. The standard technique for storing such tables is hashing, but hashing has poor worst-case performance. We propose a good worst-case method for storing a static table of n entries, each an integer between 0 and N - 1. The method requires O ( n ) words of storage and allows O (log n N ) access time. Although our method is a little complicated to use in practice, our analysis shows why a simpler algorithm used for compressing LR parsing tables works so well.
Cited by 207 works. doi:10.1145/359168.359175 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- The Art of Computer Programming: Volume 3: Sorting and Searching
- The art of computer programming. Vol.3: Sorting and searching
- Principles of Compiler Design
- Principles of Compiler Design (Addison-Wesley series in computer science and information processing)
- Perfect hashing functions
- Variations on the Common Subexpression Problem
- GRAPH THEORY AND GAUSSIAN ELIMINATION