Storing a Sparse Table

Robert Endre Tarjan, Andrew Chi Chih Yao

Research output: Contribution to journalArticle

135 Scopus citations

Abstract

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
Volume22
Issue number11
DOIs
StatePublished - Nov 1 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

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

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

  • Cite this