A Lower Bound on the Complexity of Orthogonal Range Queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Lower Bound on the Complexity of Orthogonal Range Queries

Full text

Pdf (629 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 4 (October 1981) table of contents

Pages: 696 - 705

Year of Publication: 1981

ISSN:0004-5411

Author

Michael L. Fredman

Department of Electrical Engineering and Computer Sciences, University of California at San Diego, La Jolla, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 51, Citation Count: 23

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/322276.322281 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	BENTLEY, J., FRIEDMAN, J., AND MAUER, H. Two papers on range searching. Tech Rep. CMU-CS- 78-136, Dep. of Computer Science, Carneg,e-Mellon Umv, Pittsburgh, Pa., 1978.
	2	BENTLEY, J, AND SHAMOS, M A problem m mult~-vanate staustlcs: Algorithm, data structure, and applications. Proc 15th Ann AUerton Conf. on Communications, Control, and Computing, 1977, pp 193-201
	3	BURKHARD, W, FREDMAN, M, AND KLEITMAN, D. Inherent complex,ty trade-offs for range query problems To appear m Theoret. Comput Sct
	4	FREDMAN, M Lower bounds on the complexity of some optimal data structures. SICOMP 10, 1 (1981), 1-10.
	5	Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
	6	HARDY, G., LITTLEWOOD, J., AND POLYA, G lnequahtles. Cambndge University Press, Cambridge, 1967
	7	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	8	LUEKER, G A data structure for orthogonal range queries. 19th Ann. Symp. on Foundations of Computer Science, Ann Arbor, Mich., 1978, pp 28-34
	9	LUEKER, G. A transformation for addmg range restriction capability to dynamic data structures for decomposable searching problems Tech. Rep. 129, Univ. of Cahfornia at Irvine, Irvine, Cahf, Feb. 1979
	10	WILLARD, D Predicate-oriented database search algorithms Res. Rep TR-20-78, Aiken Computation Laboratory, Harvard Umv, Cambridge, Mass., 1978.
	11	WILLARD, D New data structures for orthogonal queries. Res. Rep. TR-22-78, Alken Computation Laboratory, Harvard Umv, Cambridge, Mass., 1978.

CITED BY 23

	Paul Dietz , Kurt Mehlhorn , Rajeev Raman , Christian Uhrig, Lower bounds for set intersection queries, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.194-201, January 25-27, 1993, Austin, Texas, 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
	Hervé Brönnimann , Bernard Chazelle, How hard is halfspace range searching?, Proceedings of the eighth annual symposium on Computational geometry, p.271-275, June 10-12, 1992, Berlin, Germany
	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
	Pankaj K. Agarwal , Noga Alon , Boris Aronov , Subhash Suri, Can visibility graphs be represented compactly?, Proceedings of the ninth annual symposium on Computational geometry, p.338-347, May 18-21, 1993, San Diego, California, United States
	P M Vaidya, Space-time tradeoffs for orthogonal range queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.169-174, May 06-08, 1985, Providence, Rhode Island, United States
	Chung Keung Poon, Dynamic orthogonal range queries in OLAP, Theoretical Computer Science, v.296 n.3, p.487-510, 14 March 2003
	Thomas Dubé, Dominance range-query: the one-reporting case, Proceedings of the ninth annual symposium on Computational geometry, p.208-217, May 18-21, 1993, San Diego, California, United States
	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985
	Dan E. Willard, Quasilinear algorithms for processing relational calculus expressions (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-257, April 02-04, 1990, Nashville, Tennessee, United States
	Bernard Chazelle, Lower bounds for off-line range searching, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.733-740, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Managing and analyzing massive data sets with data cubes, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	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
	Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Dynamic multidimensional data cubes, Multidimensional databases: problems and solutions, Idea Group Publishing, Hershey, PA, 2003
	Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982
	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
	Dan E. Willard, Multidimensional search trees that provide new types of memory reductions, Journal of the ACM (JACM), v.34 n.4, p.846-858, Oct. 1987
	Xian Liu , Wilsun Xu, A Stochastic Programming Approach for Range Query Retrieval Problems, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.867-880, July 2002
	Mihai Păatraşcu , Erik D. Demaine, Tight bounds for the partial-sums problem, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
	Mihai Patrascu, Lower bounds for 2-dimensional range counting, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Vida Dujmović , John Howat , Pat Morin, Biased range trees, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.486-495, January 04-06, 2009, New York, New York

INDEX TERMS

Primary Classification:
E. Data

Additional Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:

Michael L. Fredman: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player