高级检索

    局部范围受限的多类型最近邻查询

    Multi-Type Nearest Neighbor Queries with Partial Range Constrained

    • 摘要: 多类型最近邻查询在现实中的应用范围比传统的最近邻查询广泛.基于多类型最近邻查询,提出局部范围受限的多类型最近邻查询(PCMTNN)概念,针对范围约束是任意简单多边形区域的数据集给出PCMTNN算法,利用椭圆最小外切矩形的易求性和与椭圆本身覆盖区域的最近似性特点缩小了搜索范围,并用一个链表结构实现了在一次R树的遍历过程中找到包含在所有搜索区域内的数据集中点的过程,从而大幅度减少了无用点的访问数量.实验结果分析表明算法具有较好的性能.

       

      Abstract: 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.

       

    /

    返回文章
    返回