欧式空间中反向最远邻查询方法的研究

大部分反向最远邻查询算法采用过滤-提纯查询处理框架,对数据集和查询点的位置关系不进行判断。针对这种情况,提出了一种处理欧式空间中反向最远邻查询方法,首先利用查询点与凸包之间的位置关系进行判断,得到三种情况,针对第三种情况再进行过滤和提纯两步处理。在过滤步骤中,使用修改的半平面修剪策略,除去大量的数据点,在提纯步骤排除不是查询点反向最远邻的数据点。实验结果验证了算法的有效性。

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

PIV算法在构建Metric索引时,需要计算凸包顶点与凸包内的全部数据点距离,当数据集较大时,会浪费存储空间并增加查询消耗。为此,改进Metric索引,只存储凸包顶点与凸包内的部分数据点的距离,提出利用凸包内的点与凸包顶点之间的距离,判断该点是否是查询点反向最远邻的方法。测试结果表明,与PIV算法相比,该方法可以正确得到反向最远邻查询结果,并减少占用的存储空间和查询消耗,提高查询效率。

移动对象的动态反向最远邻查询算法

随着无线通信和定位技术的不断发展,对移动对象的位置服务提出更高的要求.为了有效地发现大量的边界区域移动对象对广泛分布的全局查询对象所产生的影响,提出了一种动态的反向最远邻查询算法,以解决移动对象的弱影响集相关问题.针对移动对象是动态环境情况下提出动态反向最远邻查询算法,并以TPR-tree为索引结构,采用半平面修剪策略,给出了改进的FTPL修剪方法.通过过滤-精炼两步骤对查询空间进行安全高效的修剪,提出移动对象的动态反向最远邻查询算法.实验结果验证了本文算法的正确性和查询性能优势.

利用离散边界点判断的反向最远邻查询算法

目前大部分的反向最远邻查询方法对查询点是否存在反向最远邻的情况不进行判断,当查询点不存在反向最远邻的结果集时,也进行全部的操作,增加了查询消耗。针对这种情况,提出了利用离散边界点判断查询点是否存在反向最远邻结果集的方法,利用离散边界点、四分邻域区和半平面修剪策略进行过滤操作,并验证过滤后得到的结果集中数据点的有效性。实验测试了查询点的位置对查询的影响和数据集的大小以及数据分布对查询的影响,并与利用凸包判断的方法进行了对比分析。实验结果表明,当查询点不是离散边界点时,查询消耗几乎为0,当查询点移动到边界时,查询消耗增加。实验表明提出的方法可以得到查询点的反向最远邻结果集。

移动对象的动态反向最近邻算法

针对现有的算法,很多观点都是基于静态对象的,提出以TPR-tree为索引结构,用现有的半平面修剪策略进行改进的,利用剩余MBR的对角线判断是否保留MBR的方法,使原修剪策略性能优化,并采用过滤提纯的方法来获取移动查询点的反向最近邻,实现了移动对象的动态反向最近邻查询.

一种基于移动对象的动态反向最近邻的算法

随着无线通讯技术的发展,移动对象的查询有广阔的应用空间。针对现有反向最近邻算法很多都是基于静态对象的情况,提出了一种新的基于移动对象的反向最近邻的算法——以TPR-tree为索引结构,对原有的半平面修剪策略进行了改进,使其性能优化,并采用过滤验证这两个处理步骤来获取移动查询点的反向最近邻,实现了移动对象的动态反向最近邻的查询。