Peter Elias
Abstract
We consider a set of static files or inventories, each consisting of the same number of entries, each entry a binary word of the same fixed length selected (with replacement) from the set of all binary sequences of that length, and the entries in each file sorted into lexical order. We also consider several retrieval questions of interest for each such file. One is to find the value of the jth entry, another to find the number of entries of value less than k.
When a binary representation of such a file is stored in computer memory and an algorithm or machine which knows only the file parameters (i.e. number of entries, number of possible values per entry) accesses some of the stored bits to answer a retrieval question, the number of bits stored and the number of bits accessed per retrieval question are two cost measures for the storage and retrieval task which have been used by Minsky and Papert. Bits stored depends on the representation chosen: bits accessed also depends on the retrieval question asked and on the algorithm used.
We give firm lower bounds to minimax measures of bits stored and bits accessed for each of four retrieval questions, and construct representations and algorithms for a bit-addressable machine which come within factors of two or three of attaining all four bounds at once for files of any size. All four factors approach one for large enough files.
- 1 CovslL T.M. Enumerative source encoding. IEEE Trans. IT-19 (Jan. 1973), 73-77.Google Scholar
- 2 ELIAs, P. On binary representations of monotone sequences. Proc. Sixth Princeton Conference on Information Sciences and Systems, March 1972, Dep. of Electrical Engineering, Princeton U., Princeton, N. J., 1972, pp. 54-57.Google Scholar
- 3 FANo,R.M. On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., n.d.Google Scholar
- 4 FANO, 1{. M. Transmission of Information, MIT Press, Cambridge, Mass., and Wiley, New York, 1961.Google Scholar
- 5 GALLAaE*~, R.G. Information Theory and Reliable Communication. Wiley, New York, 1968. Google Scholar
- 6 LEH~Sn, D.H. Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis, Amer. Math. Soc., Providence, R.I., 1960, Ch. 1, pp. 5-31.Google Scholar
- 7 MINSKY, M., AND PAeERT, S. Perceptrons. MIT Press, Cambridge, Mass., 1969, pp. 215-225.Google Scholar
- 8 SCnA~KWIJK, J. P.M. An algorithm for source coding. IEEE Trans. IT-18 (May 1972), 395-399.Google Scholar
- 9 WOZENCRAFT, J. M., AND REIFFEN, B. Sequential Decoding. MIT Press, Cambridge, Mass., 1961, pp. 71-73.Google Scholar
- 10 FLOWER, R.A. Computer updating of a data structure. Quart Progress Rep. 110, Res. Lab. of Electronics, MIT, Cambridge, Mass., July 1973.Google Scholar
Index Terms
- Efficient Storage and Retrieval by Content and Address of Static Files
Recommendations
Efficient Management of Complex Striped Files in Active Storage
Euro-Par '08: Proceedings of the 14th international Euro-Par conference on Parallel ProcessingActive Storage provides an opportunity for reducing the bandwidth requirements between the storage and compute elements of current supercomputing systems, and leveraging the processing power of the storage nodes used by some modern file systems. To ...
Comments