INDEXING THE DISTANCE – AN INCISIVE APPROACH FOR QUERY PROCESSING

Given two spatial datasets P (e.g., facilities) and Q (queries), a nearest neighbor (NN) query retrieves the point(s) of P with the smallest group distance(s) to points in Q. Assuming, for example, n users at locations q1, . . . qn, a NN query outputs the facility p ε P that minimizes the sum of distances |pqi | for 1 ≤ i ≤ n that the users have to travel in order to meet there. Similarly, another NN query may report the point p ε P that minimizes the maximum distance that any user has to travel, or the minimum distance from some user to his/her closest facility. If Q fits in memory and P is indexed by an R-tree, we develop algorithms for nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results