If the kind of query you are interested in running is a "K Nearest Neighbor Query" (that is for a give point give me the K nearest objects) you should also cons

If the kind of query you are interested in running is a "K Nearest Neighbor Query" (that is for a give point give me the K nearest objects) you should also consider looking at metric trees. To have a metric tree you must have a metric function which takes two objects and returns a distance between them. The distance must satisfy: 1. d(x, y) ≥ 0 (non-negativity) 2. d(x, y) = 0 if and only if x = y (identity of indiscernibles) 3. d(x, y) = d(y, x) (symmetry) 4. d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality). Metric trees can be highly useful for data which is either highly dimensional (ie having greater than 3 or 4 dimensions) or non dimensional (like strings for instance DNA sequences). The M-Tree is probably the most generally useful metric tree: http://en.wikipedia.org/wiki/M-tree http://en.wikipedia.org/wiki/M-tree If you data is static or only updated very infrequently you should use an MVP tree. It is probably the best static structure, closely followed by Sergey Brin's GNAT structure. MVP Tree: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7492 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7... GNAT: http://infolab.stanford.edu/~sergey/near.html http://infolab.stanford.edu/~sergey/near.html Finally for some data (like strings) it can be very expensive to calculate the distance function. Therefore, there is another set of structures which relax the triangle inequality and are "near metric" trees. These can be useful for pruning your search space. For more info on metric data structures see: http://www.amazon.com/Foundations-Multidimensional-Metric-Data-Structures/dp/0123694469/ref=cm_cr_pr_product_top http://www.amazon.com/Foundations-Multidimensional-Metric-Da...