Multi-Type Nearest Neighbor Queries with Partial Range Constrained

Multi-type nearest neighbor (MTNN) query is used in real-ife applications more widely than the traditional nearest neighbor query. The concept of multi-type nearest neighbor query with partial range constrained (PCMTNN) is put forward, and the PCMTNN algorithm is proposed, which aims at the ranges constrained with arbitrary simple polygons. The range queries are used to get the qualified points among the datasets that have the constrained ranges; and then, the rest datasets and the new datasets which contain those qualified points are visited to obtain final results. Some characteristics of the minimal circumscribed rectangle of an ellipse are used in this algorithm. For instance, the minimal circumscribed rectangle of an ellipse can be figured out easily and the area which it contains is no better than the area covered with the same ellipse. The search area can be reduced by using these characteristics. A list structure is introduced, which contains two flags. One of the flags is used in downward pruning, and the combination of the two flags can be used in upward pruning. It travels an R tree only one time and can find all points in current different search areas. And it reduces the quantity of useless visited points significantly. Experimental results and analyses show that the algorithm has a better performance.