Biased range trees

ABSTRACT

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R² and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are O(n log n).

REFERENCES

• 1: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society Press, 1999.
• 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: 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]
• 5: 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]
• 6: B. Chazelle and L. J. Guibas. Fractional cascading: I. a data structuring technique. Algorithmica, 1:133--162, 1986.
• 7: Sébastien Collette , Vida Dujmović , John Iacono , Stefan Langerman , Pat Morin, Distribution-sensitive point location in convex subdivisions, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.912-921, January 20-22, 2008, San Francisco, California
• 8: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 9: 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]
• 10: George S. Lueker, A data structure for orthogonal range queries, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, p.28-34, October 16-18, 1978
• 11: K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5:287--295, 1975.
• 12: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: Raimund Seidel , Udo Adamy, On the exact worst case query complexity of planar point location, Journal of Algorithms, v.37 n.1, p.189-217, Oct. 2000 [doi>10.1006/jagm.2000.1101]
• 14: C. E. Shannon. A mathematical theory of communication. Bell Systems Technical Journal, pages 379--423 and 623--656, 1948.
• 15: A. C. Yao. On the complexity of maintaining partial sums. SIAM Journal on Computing, 14:277--288, 1985.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms