Quasi-Valid range querying and its implications for nearest neighbor problems

ABSTRACT

We define a new formalism called the quasi-valid range aggregation. This formalism leads to a new and quite simple method for reducing non-range query-like problems to range queries and often to orthogonal range queries, with immediate applications to the ATTRACTED NEIGHBOR and the planar ALL-PAIRS NEAREST NEIGHBORS problems (the latter being solved optimally on both parallel and sequential machines). A point of special interest is that our new formalism permits operators “+” that are neither associative nor abelian (unlike traditional range query theory). The technique described in this paper should therefore have significant other applications besides those we consider, especially in the context of parallel computational geometry.

REFERENCES

• AC88: R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73414]
• ACG87a: M.J. Atallah, R. Cole, and M.T. Goodrich, Divideand-Conquer: A technique for Designing Parallel Algorithms, Tech. Rep. 665, Dept. of Comp. Sci., Purdue Univ., 1987.
• ACG87b: M.J. Atallah, R. Cole, and M.T. Goodrich, Divideand-Conquer: A Technique for Designing Parallel Algorithms, 28-th IEEE Syrup. on Foundations o/ Computer Science, (1987), pp. 151-160.
• AG86: Mikhail J. Atallah , Michael T. Goodrich, Efficient parallel solutions to some geometric problems, Journal of Parallel and Distributed Computing, v.3 n.4, p.492-507, December 1, 1986 [doi>10.1016/0743-7315(86)90011-0]
• AKS83: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• Be75: 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]
• Be80: 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]
• BM80: J.L. Bentley and H.A. Mauer, Efficient worst-case data structures for range searching, Acts lnformatica 13 (1980), pp. 155-168.
• BS77: J.L. Bentley and M.I. Shamos, A problem in multivariate statistics: algorithm, data structure and applications, 15-th Allerton Conf. on Comm., Contr., and Comp. (1977), pp. 193-201.
• BS80: J.L. Bentley and J.B. Saxe, Decomposable searching problems #1: static to dynamic transformations, J. Alg. (1980), pp. 301-358.
• Ch85: B. Chazelle, Slimming Down Data Structures a Functional Approach to Algorithm Design, 25-th IEEE Syrup. on Foundations of Computer Science, pp i65- 174.
• Ch86a: 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]
• Ch86b: Lower bounds on the complexity of multidimensional searching, Proc. ~7-th Ann. IEEE Syrup. on Foundation8 of Computer Science, Oct. 1986, Toronto, pp. 87-96.
• Ch87: Polytope Range Searching and Integral Geometry, Proc. gS-th Ann. IEEE Syrup. on Foundations of Computer Science, (1987), pp. 1-10.
• Co86: R. Cole, Parallel Merge Sort, eT-th Foundation8 of Computer Science, (1986), pp. 511-516.
• DK87: N. Dadoun , D. G. Kirkpatrick, Parallel processing for efficient subdivision search, Proceedings of the third annual symposium on Computational geometry, p.205-214, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41980]
• Ed87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EO85: H.Edelsbrunner and M. Overmars, Batehed dynamic solutions to decomposable searching problems, J. Algorithms 6 (1985), pp. 515-542.
• EW86: H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
• Fr80: M.L. Fredman, The Inherent Compl. of Dynamic Data Structures Which Accommodate Range Queries, 21st FOCS, (1980), pp 191-199.
• Fr81a: 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]
• Fr81b: The Spanning Bound as a Measure of Range Query Complexity, Journal of Algorithm8 1 (1981), pp 77-87. pp. 282-286.
• HW87: D. Haussler and E. Welzl, e-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), pp. 127- 151.
• KMR85: Rolf G. Karlsson , J. Ian Munro , Edward L. Robertson, The Nearest Neighbor Problem on Bounded Domains, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.318-327, July 15-19, 1985
• LP84: D.T. Lee and F. Preparata, Computational Geometry A Survey, IEEE Trans. Comp. 33 (1984), pp. 1072- 1101.
• LW77: D.T. Lee and C.K. Wont, Worst-case analysis of region and partial region searches in multidimensional binary search trees and balance quad trees, Acta lnformatica 9 (1977), pp. 23-29.
• LW82: G.S. Lueker and D.E. Willard, A data structure for dynamic range queries, Inf. Proc. Letters 15 (1982), pp. 209-213.
• Me84: K. Mehlhorn, Data Structure8 and Algorithm8 (Volume 8}, a 12-page summary of {FrSla}'s formalism appears here; Springer-Verlag, 1984; pp. 60-72. Computing 26 (1981), pp. 155-166.
• OL81: M. Overmars and j.V. Leeuvwen, Two General Methods for Dynamizing Decomposable Searching Problems, Computing 20 (1981), pp. 155-166.
• Ov83: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Va85: 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]
• Va86: ~ An optimal algorithm for the all-nearestneighbors problem, Proc. 27-th Ann. IEEE Syrup. Foundations of Computer Science, 1986, pp. 117-122.
• Wi82: D.E. Willard, Polygon Retrieval, SlAM J. on Comp. 11(1982), pp. 149-165.
• Wi85: 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]
• Wi86: 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]
• Wi87: 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
• WL85: 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]
• Ya85: A.C. Yao, On the complexity of maintaining partial sums, SIAM Journal on Computing, 14(1985), pp. 277-289.
• YY85: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Graphs and networks

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Performance, Theory