Adding range restriction capability to dynamic data structures

ABSTRACT

A database is said to allow range restrictions if one may request that only records with some specified field in a specified range be considered when answering a given query. A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of O(log n) in the worst-case time for an operation and in the space used. This is a generalization of a known transformation that works for static structures. This transformation is then used to produce a data structure for range queries in k dimensions with worst-case times of O(logk n) for each insertion, deletion, or query operation.

REFERENCES

• 1: 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]
• 2: BENTLEY, J.L. Decomposable searching problems. Inf. Proc. Lett. 8, 5 (June 1979), 244-251.
• 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, 2 (Feb. 1980), 155-168.
• 5: BENTLEY, J. L., AND SAXE, J.B. Decomposable searching problems 1: Static to, dynamic transformations, j. Algorithms 1, 4 (1980), 301-358.
• 6: BENTLEY, J. L., AND SHAMOS, M.I. A problem in multivariate statistics: Algorithm, data structure, and applications. In Proceedings of the 15th Allerton Conference on Communication, Control and Computing(Sept. 1977), pp. 193-201.
• 7: BENTLEY, J. L., AND SHAW, M. An Alphard specification of a correct and efficient transformation on data structures. In IEEE Conference on Specifications of Reliable Software (Apr.). IEEE, New York, 1979.
• 8: BENTLEY, J.L., AND STANAT, F. Analysis of range searches in quad trees. Inf. Proc. Lett. 3, 6 (1975), I70-173.
• 9: BLUM, N., AND MEHLHORN, K. On the average number of rebalancing operations in weightbalanced trees. Theor. Comput. Sci. 11 (1980), 303-320.
• 10: BOLOUR, A. Optimal retrieval algorithms for small region queries. SlAM J. Comput. 10, 4 (Nov. 1981), 721-741.
• 11: EDELSBRUNNER, H. A note on dynamic range searching. Bull. EATCS 15 (Oct. 1981), 34-40.
• 12: EDELSBRUNNER, H., AND WELZL, E. Half-planar range search in linear space and O(n0"695) query time. Tech. Rep. F-111, Univ. of Graz, Graz, Austria, Mar. 1983.
• 13: CHAZELLE, B. Filtering search: A new approach to query answering. In 24th IEEE Symposium on Foundations of Computer Science (Nov.). IEEE, New York, 1984, pp. 122-132.
• 14: FINKEL, R.A., AND BENTLEY, J.L. Quad trees: A data structure for retrieval on composite keys. Acta Inf. 4 (1974), 1-9.
• 15: FISCHER, M.J., AND ROSENBERG, A.L. Real-time solutions of the origin-crossing problem, Math. Syst. Theor. 2, 3 (1968), 257-263.
• 16: FREDMAN, M.F. The inherent complexity of dynamic data structures which accomodate range queries. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York, 1980, pp. 696-706.
• 17: 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]
• 18: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• 19: 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
• 20: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 21: LEE, D.T., AND WONG, C.K. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Inf. 9 (1977), 23-29.
• 22: 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]
• 23: LUEKER, G.S. A data structure for orthogonal range queries. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., Oct.). IEEE, New York, 1978, pp. 28-34.
• 24: 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, lrvine, Irvine, Calif., Feb. 1979.
• 25: LUEKER, G.S., AND WILLARD, D.E. A data structure for dynamic range queries. Inf. Proc. Lett. 15, 5 (Dec. 1982), 209-213.
• 26: MCCREIGHT, E. M, Efficient algorithms for enumerating intersecting intervals and rectangles. Tech. Rep. CSL-80-9, Xerox Corp., Palo Alto, Calif., June 1980.
• 27: NIEVERGELT, J., AND REINGOLD, E. M. Binary search trees of bounded balance. SIAM J. Comput. 2, 1 (1973), 33-43.
• 28: OVERMARS, M.H., AND VAN LEEUWEN, J.Two general methods for dynamizing decomposable searching problems. Computing 26 ( 1981), 155-166.
• 29: WILLARD, D. E.Predicate-oriented database search algorithms. Ph.d. Dissertation, Harvard Univ., Sept. 1978; available as Tech. Rep. TR-20-78, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass., 1978.
• 30: 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]
• 31: WILLARD, D.E.Balanced forests of k-d* trees as a dynamic data structure. Tech. Rep. TR-23-78, Cent. for Research in Computing Technology, Harvard Univ., Cambridge, Mass., Nov. 1978.
• 32: WILLARD, D.E.The super-B-tree algorithm. Tech. Rep. TR-03-79, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass., Jan. 1979.
• 33: WILLARD, D. E. k-d trees in a dynamic environment. Tech. Rep. 80-1, Dept. of Computer Science, Univ. of Iowa, Ames, Iowa, May 1980.
• 34: WILLARD, D.E.Polygon retrieval. SIAM J. Comput. 11, 1 (Feb. 1982), 149-165.
• 35: 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
• 36: 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

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Composite structures**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Performance, Theory, Verification