Filter Trees for Managing Spatial Data over a Range of Size Granularities
Kenneth C. Sevcik, Nick Koudas · 1996
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 information structure is a hierarchical organization that tends to separate spatial entities by size, placing larger entities 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. 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 Fil...