Storing a Sparse Table

Robert Endre Tarjan; Andrew Chi Chih Yao

doi:10.1145/359168.359175

Storing a Sparse Table

Robert Endre Tarjan, Andrew Chi Chih Yao

Research output: Contribution to journal › Article › peer-review

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

Original language	English (US)
Pages (from-to)	606-611
Number of pages	6
Journal	Communications of the ACM
Volume	22
Issue number	11
DOIs	https://doi.org/10.1145/359168.359175
State	Published - Nov 1 1979
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science

Keywords

Gaussian elimination
parsing
searching
sparse matrix
table compression
table lookup

Access to Document

10.1145/359168.359175

Cite this

@article{4ec78fe78b3c4edc83cee8262ce60ee4,

title = "Storing a Sparse Table",

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.",

keywords = "Gaussian elimination, parsing, searching, sparse matrix, table compression, table lookup",

author = "Tarjan, {Robert Endre} and Yao, {Andrew Chi Chih}",

year = "1979",

month = nov,

day = "1",

doi = "10.1145/359168.359175",

language = "English (US)",

volume = "22",

pages = "606--611",

journal = "Communications of the ACM",

issn = "0001-0782",

publisher = "Association for Computing Machinery (ACM)",

number = "11",

}

TY - JOUR

T1 - Storing a Sparse Table

AU - Tarjan, Robert Endre

AU - Yao, Andrew Chi Chih

PY - 1979/11/1

Y1 - 1979/11/1

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

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

KW - Gaussian elimination

KW - parsing

KW - searching

KW - sparse matrix

KW - table compression

KW - table lookup

UR - http://www.scopus.com/inward/record.url?scp=0018543294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0018543294&partnerID=8YFLogxK

U2 - 10.1145/359168.359175

DO - 10.1145/359168.359175

M3 - Article

AN - SCOPUS:0018543294

SN - 0001-0782

VL - 22

SP - 606

EP - 611

JO - Communications of the ACM

JF - Communications of the ACM

IS - 11

ER -

Storing a Sparse Table

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this