| Storing a sparse table |
| Full text |
 Pdf
(595 KB)
|
Source
|
Communications of the ACM
archive
Volume 22 , Issue 11 (November 1979)
table of contents
Pages: 606 - 611
Year of Publication: 1979
ISSN:0001-0782
|
|
Authors
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 17, Downloads (12 Months): 112, Citation Count: 39
|
|
|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
|
 |
3
|
|
| |
4
|
Even, S., Lichtenstein, D.I., and Shiloach, Y. Remarks on Ziegler's method for matrix compression. Unpublished manuscript, 1977.
|
| |
5
|
|
| |
6
|
|
| |
7
|
Tarjan, R.E. Graph theory and Gaussian elimination. In Sparse Matrix Computations, J.R. Bunch and D.J. Rose, Eds., Academic Press, New York, 1976, pp. 3-22.
|
| |
8
|
Ziegler, S.F. Smaller faster table driven parser. Unpublished manuscript, Madison Academic Comptg. Ctr., U. of Wisconsin, Madison, Wisconsin, 1977.
|
CITED BY 39
|
|
|
|
|
Robert F. Cohen , Giuseppe Di Battista , Arkady Kanevsky , Roberto Tamassia, Reinventing the wheel: an optimal data structure for connectivity queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.194-200, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
Amos Fiat , Moni Naor , Jeanette Schmidt , Alan Siegel, Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.367-376, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Peter Bro Miltersen, Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.556-563, January 25-27, 1998, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
|
|
|
|
|
|
|
|
|
|
|
|
Y. Kadoya , M. Fuketa , El-Sayed Atlam , K. Morita , T. Sumitomo , J. Aoe, A compression algorithm using integrated record information for translation dictionaries, Information Sciences—Informatics and Computer Science: An International Journal, v.165 n.3-4, p.171-186, 19 October 2004
|
|
|
|
|
|
|
|
|
Praveen Krishnamurthy , Jeremy Buhler , Roger Chamberlain , Mark Franklin , Kwame Gyang , Arpith Jacob , Joseph Lancaster, Biosequence Similarity Search on the Mercury System, Journal of VLSI Signal Processing Systems, v.49 n.1, p.101-121, October 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
