# Understanding location storage and query algorithms?

One of the most important aspects of a GIS-equipped database is that it provides the user with the capability to quickly query for all points within some arbitrary geographic area that match some additional criteria. (E.g. "Find me the nearest 3 restaurants to this point on a map.")

Can anyone point me to a theoretical discussion of the algorithms involved? I want to learn how they work.

Ultimately, I want to apply the same capability to generalized sets of numerical data - a large cloud of points in an arbitrary, n-dimensional, non-euclidean space. For instance, a person's face can be characterized as a vector of numbers: [distance between eyes, distance from eye to mouth, width of face, length of face, etc.]. I want to film sidewalk traffic, estimate the features of each persons face, and then be able to make queries to the data later such as "given this person's face, find me the 100 most similar faces."

Is there currently any existing software that provides the ability to search over these generalized spaces?

Good accounts of algorithms in 2 and 3 dimensions appear in the classic text by Preparata & Shamos. Algorithms used in GIS are a specialty of Hanan Samet, who has published several books on the subject.

Higher-dimensional searches are usually assisted or sped up by means of preliminary data mining, clustering, or dimension-reducing techniques. This is more a matter of data analysis and statistics, not of GIS, which by its nature focuses on searches in one through four Euclidean dimensions. For more information, search our sister forum stats.stackexchange.com for likely terms such as clustering, dimensionality reduction, and multidimensional scaling and for less obvious ones like pca (principal components analysis) and svm (support vector machines). That is also a good place to ask about existing software.

The classic (paleogeographer) answer is to use a K-D tree to store the data in (see http://en.wikipedia.org/wiki/Kd-tree). These work by roughly halving the data in to two partitions in each dimension in turn as you move down the tree. The advantage of them is that as you find the nearest item you can also create a list of nearest items as you go for no extra cost, so answering what are the three nearest restaurants is as easy as find the nearest.

I read somewhere that eHarmony use K-D trees for finding "compatible matches" in 14 dimensions.

• +1 The brief clear description of an efficient search method is nicely done. Jun 10 '11 at 5:07

I've heard that Netezza has implemented some innovative spatial parallel processing algorithms. The whitepaper is here.

Netezza’s Asymmetric Massively Parallel Processing architecture provides the best combination of symmetric multiprocessing (SMP) and massively parallel processing (MPP), facilitating terascale, complex query processing of both spatial and non-spatial data without the complexity, tuning and aggregations necessary in traditional systems.

Update

I forgot to mention that Netezza heavily leverages Bayes Theorem. Here's a collection of videos here.