|
|
|
@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}
}
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.
