Filter Trees for Managing Spatial Data over a Range of Size Granularities.

@inproceedings{DBLP:conf/vldb/SevcikK96,
  author    = {Kenneth C. Sevcik and
               Nick Koudas},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Filter Trees for Managing Spatial Data over a Range of Size Granularities},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {16-27},
  ee        = {db/conf/vldb/SevcikK96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We introduce a new file organization for the storage and manipulation of spatial (or multi-dimensional) data that is able to execute spatial join operations with great efficiency. The Filter Tree information structure is a hierarchical organization that tends to separate spatial entities by size, placing larger e ntities at the higher levels of the Filter Tree, and smaller entities at lower levels. Within each level, index entries for the entities are ordered by a space-filling curve (Hilbert curve). This allows the algorithms to use bulk I/O requests, exploiting the locality in the index information, and minimizing the number of I/O transfers from disk. We provide algorithms for constructing Filter Trees, for performing range queries on a Filter Tree, and for performing spatial joins between a pair of Filter Trees.

Finally, we include results from experiments using a prototype implementation of Filter Trees to treat both synthetic and real s ets of spatial entities. Our experimental results show that full spatialjoins can always be done more efficiently with Filter Trees than with curre nt competitive methods, and that in some cases the improvement in performance is very large.

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Electronic Edition

• From SunSITE Central Europe (Aachen, Germany)
  • Postscript file, via HTTP
  • Sources, via HTTP
• From CS Dept., University Trier (Germany)
  • Postscript file, via HTTP
  • Postscript file, via anonymous FTP
  • Postscript file, compressed by gzip, via anonymous FTP
  • Postscript file, compressed by compress, via anonymous FTP
  • Sources, via HTTP
  • Sources, via anonymous FTP

References

[AS83]

...

[Bia69]

T. Bially: Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory 15(6): 658-664(1969) BibTeX

[BKS93]

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX

[BKSS90]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[Bur91]

...

[Gue91]

...

[Gut84]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[HSW90]

Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379 BibTeX

[Jag90]

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 BibTeX

[Ked82]

...

[KF93]

Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX

[KF94]

Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX

[NH94]

Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155 BibTeX

[OM88]

Jack A. Orenstein, Frank Manola: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629(1988) BibTeX

[Sam90]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

[SK95]

...

[SRF87]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[SW88]

Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 BibTeX

Referenced by

1. H. V. Jagadish, Nick Koudas, Divesh Srivastava: On Effective Multi-Dimensional Indexing for Strings. SIGMOD Conference 2000: 403-414
2. Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.: Spatial Join Selectivity Using Power Laws. SIGMOD Conference 2000: 177-188
3. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
4. Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335