Path caching (extended abstract): a technique for optimal external searching

ABSTRACT

External 2-dimensional searching is a fundamental problem with many applications in relational, object-oriented, spatial, and temporal databases. For example, interval intersection can be reduced to 2-sided, 2-dimensional searching and indexing class hierarchies of objects to 3-sided, 2-dimensional searching. Path caching is a new technique that can be used to transform a number of time/space efficient data structures for internal 2-dimensional searching (such as segment trees, interval trees, and priority search trees) into I/O efficient external ones. Let n be the size of the database, B the page size, and t the output size of a query. Using path caching, we provide the first data structure with optimal I/O query time O(logBn+t/B) for 2-sided, 2-dimensional searching. Furthermore, we show that path caching requires a small space overhead O(n÷Blog2log2B) and is simple enough to admit dynamic updates in optimal O(logBn) amortized time. We also extend this data structure to handle 3-sided, 2-dimensional searching with optimal I/O query-time, at the expense of slightly higher storage and update overheads.

REFERENCES

• BaM: R. Bayer and E. McCreight, "Organization of Large Ordered indexes," Acta Informatzca 1 (1972), 173-189.
• Ben: J. L. Bentley, "Algorithms for Klee's Rectangle Problems," Dept. of Computer Science, Carnegie Mellon Univ. unpublished notes, 1977.
• BlGa: G. Blankenagel and R. H. Giiting, "XP-Trees - External Priority Search Trees," FernUniversit/it Hagen, Informatik-Bericht Nr. 92, 1990.
• BlGb: G. Blankenagel and R. H. Giiting, "External Segment Trees," FernUniversitgt Hagen, Informatik-Bericht, 1990.
• ChT: Y.-J. Chiang and R. Tamassia, "Dynamic Algorithms in Computational Geometry," Proceedzngs of IEEE, Speczal Issue on Computa- Izonal Geometry 80(9) (1992), 362-381.
• Cod: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• Com: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• Edea: H. Edelsbrunner, "A new Approach to Rectangle Intersections, Part I," Int. J. Computer Mathematics 13 (1983), 209-219.
• Edeb: H. Edelsbrunner, "A new Approach to Rectangle Intersections, Part II," Inl. J. Computer Mathemat,cs 13 (1983), 221-229.
• Gün: Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
• Gut: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• IKO: Ch. Icking , R. Klein , Th. Ottmann, Priority search trees in secondary memory (extended abstract), Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.84-93, July 1988, Kloster Banz/Staffelstein, Germany
• KKR: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• KRV: Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
• KKD: Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989 [doi>10.1145/63320.66510]
• KiL: Won Kim , Frederick H. Lochovsky, Object-oriented concepts, databases, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1989
• LoS: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• LOL: Chee Chin Low , Beng Chin Ooi , Hongjun Lu, H-trees: a dynamic associative search index for OODB, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.134-143, June 02-05, 1992, San Diego, California, United States
• McC: E. M. McCreight, "Priority Search Trees," SIAM Journal of Computzng 14(2)(1985), 257- 276.
• NHS: 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]
• Ore: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• OSB: Mark H. Overmars , Mark T. de Berg , Marc J. van Kreveld , Michiel H. M. Smid, Maintaining range trees in secondary memory. Part I: partitions, Acta Informatica, v.27 n.5, p.423-452, 1990 [doi>10.1007/BF00289018]
• Rob: J. T. Robinson, "The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes," Proc. ACM SIGMOD(I984), 10-18.
• Sama: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Samb: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SRF: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• SmO: Michiel H. M. Smid , Mark H. Overmars, Maintaining range trees in secondary memory. Part II: lower bounds, Acta Informatica, v.27 n.5, p.453-480, 1990 [doi>10.1007/BF00289019]
• ZdM: Stanley B. Zdonik , David Maier, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989

INDEX TERMS

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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Theory