Computing partial sums in multidimensional arrays

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing partial sums in multidimensional arrays

Full text

Pdf (974 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifth annual symposium on Computational geometry table of contents

Saarbruchen, West Germany

Pages: 131 - 139

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

B. Chazelle	Department of Computer Science, Princeton University
B. Rosenberg	Department of Computer Science, Princeton University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/73833.73848 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	Agarwal, P., Sharir, M., Shor, P. Sharp upper and louter bounds on the length of geneml Davenport-Schintel sequences, manuscript, 1988.
	2	Alon, N., Schieber, B. Optimal preprocessing for answering on-line product queries, TR 71/87, The Moise and Frida Eskenasy Institute of Computer Science, Tel Aviv University, 1987.
	3	Bentley, J.L. Decomposable searching problems, Info. Proc. Lett. 8 (1979), 244-251.
	4	Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
	5	Bentley, J.L., Maurer, H.A. Deficient worst-case data structures for range searching, Acta Informatica 13 (1980), 155-168.
	6	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	7	Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
	8	Chazelle, B. Lower bounds on the complexity of multidimensional searching, Tech. Rep. CS-TR-055-86, Dept. Computer Science, Princeton University. Abridged version in Proc. 27th Annu. IEEE Symp. on Foundat. of Comput. Sci. (1986), 87-96.
	9	Chazelle, B., Guibas, L.J. Fractional cascading: IJ. Applications, Algorithmica 1 (1986), 163-191.
	10	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]
	11	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	12	Lueker, G.S. A data structure for orthogonal range queries, Proc. 19th Annu. IEEE Symp. on Foundat. of Comput. Sci. (1978), 28-34.
	13	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	14	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	15	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	16	Tarjan, R.E. Complexity of monotone networks for computing conjunctions, Annals Discrete Math. 2 (1978), 121-133.
	17	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 [doi>10.1145/22145.22164]
	18	Dan E. Willard, New data structures for orthogonal range queries, SIAM Journal on Computing, v.14 n.1, p.232-253, Feb. 1985 [doi>10.1137/0214019]
	19	D E Willard, Lower bounds for dynamic range query problems that permit subtraction, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.444-453, September 1986, Rennes, France
	20	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 [doi>10.1145/3828.3839]
	21	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]
	22	Yao, A.C. On the complexity of maintaining partial sums, SIAM J. Comput. 14 (1985), 277-288.

CITED BY 2

	Chung Keung Poon, Dynamic orthogonal range queries in OLAP, Theoretical Computer Science, v.296 n.3, p.487-510, 14 March 2003
	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