Indexing support for spatial joins

摘要

We introduce a new file organization for the storage and manipulation of spatial (or multidimensional) data that is able to execute spatial join operations with great efficiency. The Filter Tree access method is a hierarchical organization that tends to separate spatial entities by size. 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. In full spatial joins, a minimum number of index block accesses are needed using Filter Trees, as each leaf block is read at most once. We derive some basic properties of Filter Trees, and analyze the performance of the algorithms. Finally, we include results from experiments using a prototype implementation of Filter Trees to treat both synthetic and real sets of spatial entities. Our experimental results show that full spatial joins can always be done more efficiently with Filter Trees than with current competitive methods, with large performance improvements.