Space-time tradeoffs for orthogonal range queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Space-time tradeoffs for orthogonal range queries

Full text

Pdf (600 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 169 - 174

Year of Publication: 1985

ISBN:0-89791-151-2

Author

P M Vaidya

Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/22145.22164 What is a DOI?

ABSTRACT

We investigate the question of (storage) space - (retrieval) time tradeoff for orthogonal range queries on a static database. Lower bounds on the product of retrieval time and storage space are obtained in the arithmetic and tree models.

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	J. L. Bentley and H. A. Maurer, Efficient worst-case data structures for range searching, Acts Information, 13, 1980, pp. 155-1~8.
	2	B. Chazelle, Filtering Search: A new approach to query answering, Proc. 24th Annual IEEE Syrup. Found. Camp. Sci., 1983, pp. 122-132.
	3	R. Cole and C. K. Yap, Geometric Retrieval Problems, Proc. 24tk Annual IEEE Sltmp. Found. Camp. Sci., 1983, pp. 112-121.
	4	Fredman M. L., The inherent complexity of dynamic dat~ structures which accomodate range queries, Proc. 21't Annual IEEE Syrup. Found. Camp. Sci., 1980, pp. 191- 200.
	5	Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
	6	Fredman M. L., Lower bounds on the complexity of some optimal data data structures, SIAM J. Comput., Vo!. 10, No. 1, 1981, pp. 1-10.
	7	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	8	G. S. Lueker. A data structure for orthogonal range queries, Proc. 19t~ Annual IEEE Sltmp. Found. of Camp. Sci.. 1978, pp. 28-34.
	9	D. E. ~A3llard, New data structures for orthogonal range queries, Tech. Report TR-22-78, Aiken Computer Lab., 1978, Harvard University.
	10	D. E. Willard, Polygon Retrieval, SIAM J. Comput., Vol. 11, 1982, pp. 149-165.
	11	Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]

CITED BY 5

	B. Chazelle , B. Rosenberg, Computing partial sums in multidimensional arrays, Proceedings of the fifth annual symposium on Computational geometry, p.131-139, June 05-07, 1989, Saarbruchen, West Germany
	D. E. Willard , Y. C. Wee, Quasi-Valid range querying and its implications for nearest neighbor problems, Proceedings of the fourth annual symposium on Computational geometry, p.34-43, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	D E Willard, On the application of sheared retrieval to orthogonal range queries, Proceedings of the second annual symposium on Computational geometry, p.80-89, June 02-04, 1986, Yorktown Heights, New York, United States
	Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, ACM SIGMOD Record, v.26 n.2, p.73-88, June 1997
	Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990