论文部分内容阅读
聚合近邻查询(ANN)在空间数据库以及网络环境中是一个相对比较新的操作。与传统的只有一个查询结点的kNN查询相比,ANN具有多个查询结点,由于查询点的数目以及它们在数据库空间中分布的任意性,使得ANN查询比只有一个查询点的kNN查询复杂得多。
实际应用中聚合近邻查询的种类繁多,包括求最大值(要查找所有目标对象P中的对象到查询集Q的最大距离中的最小值),最小值(查找所有目标对象p中距离查询集Q最小距离的最小值),差值运算(目标对象到查询集中的各个查询点的距离之差要符合一个特定条件)等等,对于这些运算在ANN求和查询算法中并不能够有效地解决。而这些聚合运算在实际生活中是应用广泛而又重要的一种运算。尤其对于差值聚合运算,以及在此运算上变化得到的聚合运算,在实际中可以为很多行业提供合理分配资源的依据。
本文提出了一种基于多查询点的差值聚合近邻查询,在ANN求和查询方法中提出的将多个查询点分布于一个MBR的算法并不适用于此类差值查询。根据单查询点的YPK-CNN算法,利用双曲线性质把查询空间分成几大部分,在此基础上计算出双曲线的渐近线以简化删减条件,直接删减掉不符合条件的搜索空间。在此基础上,论文进而扩展得到多查询点的聚合近邻查询算法。实验结果显示,针对这种特定的差值聚合近邻查询,基于双曲线渐近线过滤策略的查询算法要比基本查询算法在查询响应时间和访问结点次数方面效率更高。