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

doi:10.3969/j.issn.1000-3428.2017.04.040

计算机工程

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

杨秀娟¹,董军¹,李慧慧²,袁延忠¹,陈晓丹¹

(1.黑龙江科技大学计算机与信息工程学院,哈尔滨 150022; 2.黑龙江建筑职业技术学院机电工程技术学院,哈尔滨 150025)

收稿日期:2016-03-10 出版日期:2017-04-15 发布日期:2017-04-14
作者简介:杨秀娟(1978—),女,讲师、硕士,主研方向为人工智能;董军,副教授、博士研究生;李慧慧,讲师、硕士;袁延忠,硕士;陈晓丹,讲师、硕士。
基金项目:
黑龙江省教育厅科学技术研究项目(12541731)。

Reverse Furthest Neighbor Query Method Based on Improved Metric Index

YANG Xiujuan ¹,DONG Jun¹,LI Huihui ²,YUAN Yanzhong ¹,CHEN Xiaodan¹

(1.College of Computer and Information Engineering,Heilongjiang University of Science and Technology,Harbin 150022,China;2.College of Mechanical and Electrical Engineering Technology,Heilongjiang Institute of Construction Technology,Harbin 150025,China)

Received:2016-03-10 Online:2017-04-15 Published:2017-04-14

摘要/Abstract

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

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

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

Key words: spatial database, reverse furthest neighbor, Metric index, convex hull, half plane pruning strategy

中图分类号:

TP311.131

杨秀娟,董军,李慧慧,袁延忠,陈晓丹. 基于改进Metric索引的反向最远邻查询方法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.04.040.

YANG Xiujuan,DONG Jun,LI Huihui,YUAN Yanzhong,CHEN Xiaodan. Reverse Furthest Neighbor Query Method Based on Improved Metric Index[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.04.040.

参考文献

参考文献［1］Korn F,Muthukrishnan S.Influence Sets Based on Reverse Nearest Neighbor Queries［C］//Proceedings of ACM SIGMOD International Conference Management of Data.New York,USA:ACM Press,2000:201-212. ［2］Kang J M,Mokbel M F,Shekhar S,et al.Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors［C］//Proceedings of the 29th IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2007:806-815. ［3］Cheong O,Vigneron A,Yon J.Reverse Nearest Neighbor Queries in Fixed Dimension［J］.International Journal of Computational Geometry & Applications,2011,21(2):179-188. ［4］Tran Q T,Taniar D,Safar M.Bichromatic Reverse Nearest Neighbor Search in Mobile Systems［J］.IEEE Systems Journal,2010,4(2):230-242. ［5］Yang Congyun,Lin K.An Index Structure for Efficient Reverse Nearest Neighbor Queries［C］//Proceedings of the 17th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2001:485-492. ［6］Stanoi I,Riedewald M,Agrawal D,et al.Discovery of Influence Sets in Frequently Updated Databases［C］//Proceedings of the 27th International Conference on Very Large Data Bases.San Francisco,USA:Morgan Kaufmann Publishers Inc.,2001:99-108. ［7］Stanoi I,Agrawal D,Abbadi A E.Reverse Nearest Neighbor Queries for Dynamic Databases［C］//Proceedings of ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.New York,USA:ACM Press,2000:44-53. ［8］Tao Yufei,Papadias D,Lian Xiang.Reverse kNN Search in Arbitrary Dimensionality［C］//Proceedings of the 13th International Conference on Very Large Data Bases.Toronto,Canada:VLDB Endowment,2004:744-755. ［9］Yao Bin,Li Feifei,Kumar P.Reverse Furthest Neighbors in Spatial Databases［C］//Proceedings of the 25th International Conference on Data Engineering.Washington D.C.,USA:IEEE Computer Society,2009:664-675. ［10］李博涵,郝忠孝.反向最远邻的有效过滤和查询算法［J］.小型微型计算机系统,2009,30(10):1948-1951. ［11］Liu Jianquan,Chen Hanxiong,Furuse K,et al.An Efficient Algorithm for Reverse Furthest Neighbors Query with Metric Index［C］//Proceedings of the 21st International Conference.Berlin,Germany:Springer-Verlag,2010:437-451. ［12］Liu Jianquan,Chen Hanxiong,Furuse K,et al.An Efficient Algorithm for Arbitrary Reverse Furthest Neighbor Queries［C］//Proceedings of the 14th Asia-Pacific Web Conference.Berlin,Germany:Springer-Verlag,2012:60-72. ［13］Tran Q T,Taniar D,Safar M.Reverse Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks［J］.Transactions on Large Scale Data and Knowledge Centered Systems,2009,5740(1):353-372. ［14］王宝文,彭川,陈子军,等.路网上的单色和双色反k最远邻查询［J］.计算机工程与设计,2012,33(8):3099-3104. ［15］邓成玉,彭川,王宝文,等.空间数据库中反k最远邻查询方法［J］.燕山大学学报,2013,37(5):412-419. ［16］杨秀娟,董军,李慧慧.欧式空间中反向最远邻查询方法的研究［J］.计算机工程与应用,2015,51(4):142-147. 编辑刘冰

[1]	姚钊健,谭台哲. 结合凸包先验与流形排序的显著性检测算法[J]. 计算机工程, 2018, 44(9): 203-211,217.
[2]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[3]	郝晓红，张丽平，赵龄强，李松. 3DR39-3d方位关系模型与反方位关系[J]. 计算机工程, 2014, 40(7): 258-262.
[4]	谭正华,王烈奇,王李管,陈建宏. 基于实测轮廓线的岔道口三维实体建模方法[J]. 计算机工程, 2014, 40(11): 233-236,259.
[5]	杨泽雪，郝忠孝. 基于Voronoi图的连续反向最近邻查询[J]. 计算机工程, 2014, 40(1): 272-274,279.
[6]	朱晨阳, 熊岳山, 谭珂, 潘新华. 基于三角面网格细化策略的改进种子填充算法[J]. 计算机工程, 2013, 39(7): 279-283.
[7]	张丽平, 李松, 李林, 郝晓红. 3DR44模型的动态方向关系与反向关系研究[J]. 计算机工程, 2013, 39(5): 65-68.
[8]	郝晓红, 李松, 张丽平. 3DR44-4d方位关系表示模型[J]. 计算机工程, 2012, 38(3): 57-59.
[9]	魏茂安, 葛传宁, 邢艺兰. 海上交管系统多点定位技术研究[J]. 计算机工程, 2012, 38(18): 218-220.
[10]	张丽平, 李林, 李松, 郝晓红. 预定数据链规模的单纯型连续近邻链查询[J]. 计算机工程, 2012, 38(10): 51-53.
[11]	李松, 张丽平, 蔡志涛, 郝晓, 王淼. 数据集中单纯型连续近邻链查询方法[J]. 计算机工程, 2012, 38(04): 82-83.
[12]	唐英, 李应珍. 线性支持向量机多类分类器几何构造方法[J]. 计算机工程, 2012, 38(04): 152-154.
[13]	李珂, 陈建平. 嫦娥数据管理系统设计与实现[J]. 计算机工程, 2012, 38(04): 218-220.
[14]	李莎莎, 陈荦, 陈宏盛, 钟志农. 行星数据编目模型的设计与实现[J]. 计算机工程, 2011, 37(17): 227-229,232.
[15]	杨泽雪, 郝忠孝. 基于Voronoi图的线段反向最近邻查询[J]. 计算机工程, 2011, 37(16): 30-32.

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

Reverse Furthest Neighbor Query Method Based on Improved Metric Index

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10