Multidimensional search trees that provide new types of memory reductions

ABSTRACT

An orthogonal query that asks to aggregate the set of records in k-dimensional box regions is studied, and it is shown that space O(N((log N)/(log log N))k-1) makes possible a combined time complexity O(logkN ) for retrievals, insertions, and deletions.

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	AVID, Z., AND SHAMIR, E. A direct solution to range search and related problems for product regions. In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science. IEEE, New York, 1981, pp. 123-126.
	2	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	3	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]
	4	BENTLEY, J. L., AND MAURER, H.A. Efficient worst-case data structures for range searching. Acta Inf. 13 (1980), 155-168.
	5	BENTLEY, J. L., AND SAXE, J. B. Decomposable searching problems #1: Static to dynamic transformations. J. Algorithm I (1980), 301-358.
	6	BENTLEY, J. L., AND SHAMOS, M.I. A problem in multi-variate statistics: Algorithm, data structure and applications. In Proceedings of the 15th Allerton Conference on Communications, Control and Computers. Univ. of lUinois Press, Urbana, IU., 1977, pp. 193-201.
	7	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]
	8	CHAZELLE, B. Slimming down data structures: A functional approach to algorithm design. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 165-174. See also Tech. Rep. CS-85-16, Brown Univ., Providence, R.I., 1985.
	9	B Chazelle , H Edelsbrunner, Linear data structures for two types of range search, Proceedings of the second annual symposium on Computational geometry, p.293-302, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10547]
	10	Bernard Chazelle , Leonidas J. Guibas, Fractional Cascading: A Data Structuring Technique with Geometric Applications, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.90-100, July 15-19, 1985
	11	DOaKIN, D., AND EDELSBRUNNER, H. Space searching for intersection objects. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 387-392.
	12	DOBKIN, D., AND MUNRO, J. I. Efficient use of the past. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science. IEEE, New York, 1980, pp. 200-206.
	13	EDELSBRUNNER, H. A note on dynamic range searching. Bull. EATCS 15 (1981), 34-40.
	14	EDELSBRUNNER, H., AND OVERMARS, M.H. On the equivalence of some rectangle search problems. Inf. Proc. Lett. 14 (1982), 124-127.
	15	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]
	16	O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
	17	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]
	18	IMAI, H., AND ASANO, T. Dynamic segment intersection with application. In Proceedings of the 25th Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 393-402.
	19	LEE, D. T., AND PREPARATA, F. Computational geometry: A survey. IEEE Trans. Comput. 33 (1984), 1072-1101.
	20	LEE, D. T., AND WONG, S.K. Worst-case analysis of region and partial region searches in multidimensional binary search and balanced quad trees. Acta Inf. 9 (1977), 23-24.
	21	D. T. Lee , C. K. Wong, Quintary trees: a file structure for multidimensional datbase sytems, ACM Transactions on Database Systems (TODS), v.5 n.3, p.339-353, Sept. 1980 [doi>10.1145/320613.320618]
	22	LUEKER, G.S. A data structure for orthogonal range queries. In Proceedings of the 19th Symposium on Foundations of Computer Science. IEEE, New York, 1978, pp. 28-34.
	23	LUEKER, G.S. A transformation for adding range restriction capability to dynamic data structures for decomposable searching problems. Tech. Rep. 129, Dept. of Information and Computer Science, Univ. of California, Irvine, Calif., 1979.
	24	LUEKER, G. S., AND WILLARD, D.E. A data structure for dynamic range queries. Inf. Proc. Lett. 15 (1982), 209-213.
	25	MCCREIGHT, E.M. Priority search trees. Xerox Rep. CSL-8 I-5, Xerox, Palo Alto Research Center, Palo Alto, Calif., 1981.
	26	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	27	NIEVERGELT, J., AND REINGOLD, E.M. Binary search trees of bounded balance. SIAM J. Comput. 2 (1973), 33-43.
	28	OVERMARS, M. Range searching on a grid. Rep. R00-CS-85-179, Univ. of Utrecht, Utrecht, Holland, 1985.
	29	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	30	WILLARD, D. E. Predicate-oriented database search algorithms. In Outstanding Dissertations in Computer Science. Garland, New York, 1979.
	31	Dan E Willard, Efficient processing of relational calculus expressions using range query theory, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	32	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]
	33	D E Willard, Reduced memory space for multi-dimensional search trees, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.363-374, December 1985, Saarbru:9Aicken, Germany
	34	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
	35	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 [doi>10.1145/10515.10524]
	36	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]
	37	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]
	38	YAO, A. C. On the complexity of maintaining partial sums. SIAM J. Comput. 14 (1985), 277-289.