The Complexity of Some Simple Retrieval Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Complexity of Some Simple Retrieval Problems

Full text

Pdf (915 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 3 (July 1975) table of contents

Pages: 367 - 379

Year of Publication: 1975

ISSN:0004-5411

Authors

Peter Elias	Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, MA
Richard A. Flower	Coordinated Science Laboratory, University of Illinois, Urbana, IL and Massachusetts Institute of Technology, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 25, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321892.321899 What is a DOI?

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	COVER, T.M. Enumerative source encoding. IEEE Trans. Information Theory 1T-19, (1973), 73-77.
	2	ELIAs, P. 6.891 Course Notes. M.I.T., Cambridge, Mass., Fall 1973.
	3	Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, Journal of the ACM (JACM), v.21 n.2, p.246-260, April 1974 [doi>10.1145/321812.321820]
	4	ELIAS, P. Minimum times and memories needed to compute the values of a function. J. Comput. and Syst. Scis. 9, 2 (Oct. 1974), 196-212.
	5	FLOWER, R.A. Computer updating of a data structure. Quart. Progress Rep. 110, Res. Lab. of Electronics, M.I.T., Cambridge, Mass., July 1973, pp. 147-154.
	6	FLOWER, R. A. An analysis of optimal retrieval systems with updates. Tech. Rep. 488, Res. Lab. of Electronics, M.I.T., Cambridge, Mass. (in press).
	7	Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
	8	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	9	LERMER, D. H. Teaching combinatorial tricks to a computer. Proc. Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis, Amer. Math. Soc., Providence, R. I., 1960.
	10	MINSKY, M., AND PAPERT, S. Perceptrons. M.I.T. Press, Cambridge, Mass., 1969.
	11	T. A. Welch, BOUNDS ON INFORMATION RETRIEVAL EFFICIENCY IN STATIC FILE STRUCTURES., Massachusetts Institute of Technology, Cambridge, MA, 1971

CITED BY 6

	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981
	Donna J. Brown, Kraft storage and access for list implementations(Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.100-107, April 28-30, 1980, Los Angeles, California, United States
	Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada
	H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
	Anna Gál , Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoretical Computer Science, v.379 n.3, p.405-417, June, 2007
	Gianni Franceschini , Roberto Grossi, No sorting? better searching!, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-13, March 2008