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

Reverse Furthest Neighbor Query Method Based on Improved Metric Index

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.