|
There are many data structures that can be used for efficient spatial
searches. As with conventional data structures, a spatial data
structure must be selected based on considerations such as the
location of the data (memory or disk), and the mix of update and
search operations. Other factors are due to the spatial nature of the
objects being indexed: the dimensionality of the space, object sizes
and shapes, and the distribution of objects in the space.
Unfortunately, spatial data structures are not as widely available as conventional data structures. Popular class libraries such as C++ STL, Java JDK 1.2 collections, or the RogueWave libraries offer a wide variety of conventional data structures, but none offer even a single spatial data structure. As a result, developers of applications that manipulate spatial objects are often forced to implement from scratch data structures that support fast spatial searches. This is time-consuming and error-prone. Furthermore, these data structures tend to be narrow solutions -- a data structure developed for, say, 2-d points in virtual memory, will not work for 3-d boxes on disk. This can be a problem if requirements change, even slightly. For example, a data structure for providing fast searches of a static set of polygonal objects might not work so well if the set of objects needs to be dynamic after all. Updates might be unacceptably slow, or search performance might degrade over time. |