Storing a Sparse Table

Robert Endre Tarjan, Andrew Chi Chih Yao

Research output: Contribution to journalArticlepeer-review

152 Scopus citations


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(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.

Original languageEnglish (US)
Pages (from-to)606-611
Number of pages6
JournalCommunications of the ACM
Issue number11
StatePublished - Nov 1 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science


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


Dive into the research topics of 'Storing a Sparse Table'. Together they form a unique fingerprint.

Cite this