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.
- 1 Alto, A.V., Hopcroft, J.E., and Ullman, J.D. The Design and Analysis of Computer d Igorithm. Addison-Wesley, Reading, Mass., 1974, Google ScholarDigital Library
- 2 Aho, A.V., and Ullman, J.D. Principles of Compiler Design. Addison-Wesley, Reading, Mass., 1977. Google ScholarDigital Library
- 3 Downey, P.J., Sethi, R., and Tarjan, R.E. Variations on the common subexpression problem. To appear in J. A CM. Google ScholarDigital Library
- 4 Even, S., Lichtenstein, D.I., and Shiloach, Y. Remarks on Ziegler's method for matrix compression. Unpublished manuscript, 1977.Google Scholar
- 5 Knuth, D.E. The Art of Computer Programming, VoL 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 6 Sprugnoli, R. Perfect hashing functions: A single probe retrieving method for static sets. Comm. ACM 20, 11 (Nov. 1977), 841-850. Google ScholarDigital Library
- 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.Google Scholar
- 8 Ziegler, S.F. Smaller faster table driven parser. Unpublished manuscript, Madison Academic Comptg. Ctr., U. of Wisconsin, Madison, Wisconsin, 1977.Google Scholar
Index Terms
- Storing a sparse table
Recommendations
An optimal storage format for sparse matrices
The irregular nature of sparse matrix-vector multiplication, Ax = y, has led to the development of a variety of compressed storage formats, which are widely used because they do not store any unnecessary elements. One of these methods, the Jagged ...
Improved sparse low-rank matrix estimation
We consider estimating simultaneously sparse and low-rank matrices from their noisy observations.We use non-convex penalty functions that are parameterized to ensure strict convexity of the overall objective function.An ADMM based algorithm is derived ...
Comments