On the application of sheared retrieval to orthogonal range queries

ABSTRACT

We propose a new search technique, called the Shear-Based Format, which shows that Yao's lower bound on the time-space tradeoff for orthogonal range queries is either optimal or nearly optimal [Ya82, Ya85]. Shearing is also a very pragmatic technique.

REFERENCES

• AMM81: H. Alt, K. Mehlhorn and I. Munro, "On the complexity of partial match retrieval", Mathematical Foundations of Computer Science (1981), Springer-Verlag LNCS 118, pp. 155.161.
• 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 worstcase data structures for range searching, Acta Information 13 (1980), pp. 155-168.
• BS77: J.l,. Bentley and M.I. Shamos, A problem in multi-variate statistics: algorithm, data structure and applications, 15-th Allerton Conf. on Comm., Contr., and Comp. (1977), p. 193-201.
• BS80: J.L. Bentley and J.B. Saxe, Decomposable searching problems #1: static to dynamic transformations, or. Alg. (1980), pp. 301-358.
• BW80: J.L. Bentley and D. Wood, An optimal worstcase algorithm for reporting intersection of rectangles, IEEE Trans. on Comp. 29(1980), pp. 571-577.
• Ch83: B. Chazelle, Filter Search a New Approach to Query Processing, ~4th IEEE Syrup. on Foundations of Computer Science, 1983, pp. 122-132.
• Ch85a: --, Slimming Down Data Structures a Functional Approach to Algorithm Design, ~5-th IEEE Syrup. on Foundations of Computer Sci. ence, pp 165-174.
• Ch85b: 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]
• CG85: 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
• CE86: B. Clla zelle and H. Edelsbrunner, l,inear space data structures for two types of range queries, an article appearing in these Conference Proceedings, 1986.
• Ed81: H. Edelsbrunner, A Note on Dynamic Range Searching, Bulletin of EA TCS 15(1981), pp. 34- 40.
• EO82: H. Edelsbrunner and M. Overmars, On the equivalence of some rectangle search problems, Inf. Proc. Letters 14(1982), pp. 124-127.
• FKS82: M.L. Fredman, J. Komlos and E. Szemeredi, Storing a sparse table with O(1) Worst-case Access Time, 23-rd IEEE Syrup. on Foundations of Computer Science (1982), pp. 165-170.
• Fr80: M.L. Fredman, The Inherent Compl. of Dynamic Data Structures Which Accommodate Range Queries, ~1st FOUS, 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: G.N. Fredickson, Implicit Data Structures for the Weighted Dictionary Problem, ~~nd IEEE Symp. on Found. of Comp. Science, pp. 133- 139.
• FMN85: 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]
• GBT84: 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]
• Jo82: D.B. Johnson, A priority queue in which initialization and queue operations take O(log log D) time, Math. System Theory 15 (1982), pp. 295- 309.
• Ka84: Rolf Gunnar Karlsson, Algorithms in a restricted universe, 1985
• 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. Wong, Worst-case analysis of region and partial region searches in multidimensional binary search trees and balance quad trees, Acta Informatica 9 (1977), pp. 23- 29.
• LW80: 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]
• LW82: G.S. Lueker and D.E. Willard, A data structure for dynamic range queries, Inf. Proc. Letters 15 (1982), pp. 209-213.
• Me84: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• MS80: J.I. Munro and H. Suwanda, Implicit data structure for fast search and update, J. of Comp. and System Sciences 21 (1980), pp. 235- 250.
• NHS84: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• Ov85: M. Overmars, Range Searching on a Grid, Univ. Utrecht, RUU-CS-85-179, 1985.
• OL81: M. Overmars and J v. Leeuvwen, Two General Methods for Dynamizing Decomposable Searching Problems, Computing 26 (1981),pp155-166.
• 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]
• Va77: P. Van Erode Boas, Preserving order in a forest in less than logarithmic time and linear space, Inform. Process. Left. 6 (1977), 80-82.
• VKZ77: P. Van Emde Boas, R. Kaas and E. Zijlstra, Design and implementation of an efficient priority queue, Math. Systems Theory 10 (1977), pp. 99-1~7.
• Wi78: 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]
• Wi83: D.E. Willard, Log-logarithmic worst case range queries are possible in space O(N), Inform. Process. Lett. 17 (1983), pp. 81-89.
• Wi84a: Dan E. Willard, Sampling Algorithms for Differential Batch Retrieval Problems (Extended Abstract), Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.514-526, July 16-20, 1984
• Wi84b: 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
• Wi85a: 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]
• Wi85b: 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
• Wi85c: D.E. Willard, Lower Bounds for the Addition- Subtraction Operations in Orthogonal Range Queries, SUNY Albany, Technical Report 85- 13, to appear in the Proceedings of ICALP- 1986.
• Wi86: D.E. Willard, Applied and Theoretical Algorithms based on the Application of Sheared Retrieval to Orthogonal Range Queries, the full length version of this paper, SUNY Albany Technical Report 86-4, January 1986.
• 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]
• Ya82: 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]
• Ya85: A.C. Yao, On the complexity of maintaining partial sums, SIAM Journal on Computing, 14(1985), pp. 277-289.

INDEX TERMS

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Range data; Time-varying imagery

General Terms:
Algorithms, Theory, Verification