基于改进Metric索引的反向最远邻查询方法  

Reverse Furthest Neighbor Query Method Based on Improved Metric Index

作　　者：杨秀娟[1] 董军[1] 李慧慧[2] 袁延忠[1] 陈晓丹[1] 

机构地区：[1]黑龙江科技大学计算机与信息工程学院,哈尔滨150022 [2]黑龙江建筑职业技术学院机电工程技术学院,哈尔滨150025

出　　处：《计算机工程》2017年第4期234-238,共5页Computer Engineering

基　　金：黑龙江省教育厅科学技术研究项目(12541731)

摘　　要：PIV算法在构建Metric索引时,需要计算凸包顶点与凸包内的全部数据点距离,当数据集较大时,会浪费存储空间并增加查询消耗。为此,改进Metric索引,只存储凸包顶点与凸包内的部分数据点的距离,提出利用凸包内的点与凸包顶点之间的距离,判断该点是否是查询点反向最远邻的方法。测试结果表明,与PIV算法相比,该方法可以正确得到反向最远邻查询结果,并减少占用的存储空间和查询消耗,提高查询效率。When using PIV algorithm to build a Metric index,it is needed to calculate the distance between the convex hull vertices and all the data points in the convex hull. When the data set is large, this wastes storage space and increases the consumption of query. In order to solve this problem, this paper improves Metric index so that only the distance between the convex hull vertices and part of the data points within the convex hull is stored, and puts forward a method using the distance between the point of convex hull and the convex hull vertices to judge whether the point is the query result. Test results show that compared with the PIV algorithm,the proposed method can get the correct results of reverse furthest neighbor query, reduce the amount of storage space and query consumption, and improve the query efficiency.

关 键 词：空间数据库 反向最远邻 Metric索引 凸包 半平面修剪策略 

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论]