Storing a Sparse Table

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 0(n) w
words of storage and allows O(logn 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.

CACM November, 1979

Tarjan, R.
Yao, A.

Gaussian elimination, parsing, searching,
sparse matrix, table compression, table lookup

3.74 4.12 4.34 5.25

CA791104 DB January 23, 1980  11:24 AM

3041	4	3176
3126	4	3176
3176	4	3176
2905	5	3176
3176	5	3176
3176	5	3176
3176	5	3176