Simple QSF-trees: an efficient and scalable spatial access method

ABSTRACT

The development of high-performance spatial access methods that can support complex operations of large spatial databases continues to attract considerable attention. This paper introduces QSF-trees, an efficient and scalable structure for indexing spatial objects, which has some important advantages over R*-trees. QSF-trees eliminate overlapping of index regions without forcing object clipping or sacrificing the selectivity of spatial operations. The method exploits the semantics of topological relations between spatial objects to further reduce the number of index nodes visited during the search. A series of experiments involving randomly-generated spatial objects was conducted to compare the structure with two variations of R*-trees. The experiments show QSF-trees to be more efficient and more scalable to the increase in the data-set size, the size of spatial objects, and the number of dimensions of the spatial universe.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 3: Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
• 4: Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States
• 5: Michael Freeston, A general solution of the n-dimensional B-tree problem, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.80-91, May 22-25, 1995, San Jose, California, United States
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989
• 8: O. Günther , J. Bilmes, Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.342-356, September 1991 [doi>10.1109/69.91064]
• 9: 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
• 10: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 11: A. Henrich, and H.W. Six, "How to Split Buckets in Spatial Data Structures," in Geographic Database Management Systems, G. Gambosi, M. Scholl, and H.W. Six eds., Springer-Verlag, Berlin, 212--244, 1991.
• 12: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 13: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 14: Joseph Kuan , Paul Lewis, A study on data point search for HG-trees, ACM SIGMOD Record, v.28 n.1, p.90-96, March 1999 [doi>10.1145/309844.310065]
• 15: 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]
• 16: P. Oosterom, Reactive Data Structures for Geographic Information Systems, Ph.D. Thesis, University of Leiden, Netherlands, 1990.
• 17: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 18: R. Orlandic, "A High-Precision Spatial Access Method Based on a New Linear Representation of Quadtrees," Proc. 1st Conf. on Information and Knowledge Management CIKM-92, 499---508, 1992.
• 19: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben, The Transformation Technique for Spatial Objects Revisited, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.73-88, June 23-25, 1993
• 20: Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States
• 21: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 22: Bernhard Seeger , Hans-Peter Kriegel, Techniques for Design and Implementation of Efficient Spatial Access Methods, Proceedings of the 14th International Conference on Very Large Data Bases, p.360-371, August 29-September 01, 1988
• 23: Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia
• 24: 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
• 25: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
database management, point access methods, spatial access methods, spatial database, topological relations