[1]刘大有,吕倩楠,王生生.面向多维对象的RC-反k近邻查询新方法[J].深圳大学学报理工版,2011,28(No.5(377-470)):410-416.
 LIU Da-you,LU Qian-nan,and WANG Sheng-sheng.A new method of RkNN querry on multidimensional objects[J].Journal of Shenzhen University Science and Engineering,2011,28(No.5(377-470)):410-416.
点击复制

面向多维对象的RC-反k近邻查询新方法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第28卷
期数:
2011年No.5(377-470)
页码:
410-416
栏目:
电子与信息科学
出版日期:
2011-09-20

文章信息/Info

Title:
A new method of RkNN querry on multidimensional objects
文章编号:
1000-2618(2011)05-0410-07
作者:
刘大有吕倩楠王生生
吉林大学计算机科学与技术学院,长春 130012
Author(s):
LIU Da-youLU Qian-nanand WANG Sheng-sheng
College of Computer Science and Technology, Jilin University, Changchun 130012, P.R.China
关键词:
数据库系统查询处理信息检索空间数据库R树反k近邻查询过滤-精炼两步式处理
Keywords:
database systemsquery processinginformation retrievalspatial databaseR-treesreverse k nearest neighbor queriesfilter and refinement steps
分类号:
TP 39;TP 18
文献标志码:
A
摘要:
分析现有反k近邻(reverse k nearest neighbor,RkNN)查询在效率、数据维度等方面的不足,提出基于R树结点覆盖值(R-tree’s cover-value)的RC-反k近邻查询方法.该方法需预先计算R树每个结点的覆盖值,采用过滤-精炼两步式处理方法,在过滤阶段采用两种剪枝启发式.该方法可有效处理数据库更新,适用于任意k值、任意维的对象集,查询结果精确,且计算量较小.实验结果表明,在k>6时RC-反k近邻查询时间比同类工作更短.
Abstract:
Reverse k-nearest neighbor (RkNN) queries have been popular in recent decades,although previous researches have some limitations,i.e.,the low query efficiency and inability in multidimensional case. The proposed RkNN method based on R-tree’s cover-value, namely RC-RkNN, pre-calculated the cover-values of every node in the R-tree. This method was composed of filter stage and refinement stage. Two novel pruning heuristics were developed in the filter stage. Database can be updated efficiently with RC-RkNN,and querying results can be retrieved accurately. The value of k in RC-RkNN can be choosen arbitrarily and RC-RkNN is applicable to the multidimensional case. The simulation results on several real-world datasets and artificial datasets demonstrate that RC-RkNN need less querying time in comparison with other methods when k is larger than 6.

参考文献/References:

[1] 高云君.时空数据库查询处理关键技术研究[D].杭州:浙江大学,2008.
[2] Korn F,Muthukrishnan S.反近邻查询的影响集[C]// ACM数据管理国际会议论文集.达拉斯(美国):ACM计算机协会,2000:201-212.(英文版)
[3] Stanoi I,Agrawal D,Abbadi A E.动态数据库的反近邻查询[C]// ACM SIGMOD数据挖掘和知识发现国际会议论文集.达拉斯(美国):ACM计算机协会,2000:44-53.(英文版)
[4] TAO Yu-fei,Papadias D,LIAN Xiang,等.多维反k近邻查询[J].超大型数据库国际期刊,2007,16(3):293-316.(英文版)
[5] Singh A,Ferhatosmanoglu H,Tosun A.高维反近邻查询[C]// 第12届信息和知识管理国际会议论文集.新奥尔良(美国):计算机协会,2003:91-98.(英文版)
[6] WU Wei,YANG Fei,CHAN Chee-Yong,等.Finch:评估位置数据的反k近邻查询[C]// 超大型数据库国际会议论文集.奥克兰(新西兰):超大型数据库有限公司,2008,1(1):1056-1067.(英文版)
[7] Benetis R,Jensen C S,Karciauskas G,等.移动对象的近邻和反近邻查询[C]// 国际数据库工程与应用会议论文集. [s.l.]:[s.n.], 2002:44-53.(英文版)
[8] Cheema M A,LIN Xue-min,ZHANG Ying,等.更新滞后:连续管治反k近邻的有效技术[C]// 超大型数据库会议论文集. 里昂(法国):超大型数据库有限公司,2009,2:1138-1149.(英文版)
[9] XIA Tian,ZHANG Dong-hui.连续反近邻查询的管治[C]// 第22届数据挖掘国际会议论文集.华盛顿:IEEE计算机协会,2006:77-86.(英文版)
[10] 张明波,陆锋,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):289-300.
[11] Guttman A.R树:空间搜索的动态索引结构[C]// ACM SIGMOD 数据管理国际会议论文集.纽约:计算机协会,1984:47-57.(英文版)
[12] Güting R H,Behr T,XU Jian-qiu.移动对象轨迹的有效k近邻查询[J].超大型数据库国际期刊,2010,19(5):687-714.(英文版)


[1] GAO Yun-jun.Research on Key Techniques of Query Processing in Spatio-temporal Databases[D].Hangzhou:Zhejiang University,2008.(in Chinese)
[2] Korn F,Muthukrishnan S.Influence sets based on reverse nearest neighbor queries[C]// Proceeding of the ACM SIGMOD International Conference on Management of Data.Dallas(USA):Association for Computing Machinery,2000:201-212.
[3] Stanoi I,Agrawal D,Abbadi A E.Reverse nearest neighbor queries for dynamic databases[C]// Proceeding of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.Dallas(USA):Association for Computing Machinery,2000:44-53.
[4] TAO Yu-fei,Papadias D,LIAN Xiang,et al.Multidimensional reverse kNN search[J].The International Journal on Very Large Data Bases,2007,16(3):293-316.
[5] Singh A,Ferhatosmanoglu H,Tosun A.High dimensional reverse nearest neighbor queries[C]// The 12th International Conference on Information and Knowledge Management.New Orleans (USA):Association for Computing Machinery,2003:91-98.
[6] WU Wei,YANG Fei,CHAN Chee-yong,et al.Finch:evaluating reverse k-nearest-neighbor queries on location data[C]// Proceeding of Very Large Data Bases. Ackland(New Zealand): Very Large Data Boses Endowent Inc,2008,1(1):1056-1067.
[7] Benetis R,Jensen C S,Karciauskas G,et al.Nearest neighbor and reverse nearest neighbor queries for moving objects[C]// Proceedings of International Database Engineering and Applications Symposium. [s.l.]:[s.n.],2002:44-53.
[8] Cheema M A,LIN Xue-min,ZHANG Ying,et al.Lazy updates:an efficient technique to continuously monitoring reverse kNN[C]// Proceeding of the VLDB Endowment. Lyon(France): Very Large Data Boses Endowent I,2009,2:1138-1149.
[9] XIA Tian,ZHANG Dong-hui.Continuous Reverse Nearest Neighbor Monitoring[C]// Proceedings of the 22th International Conference on Data Engineering.Washington:IEEE Computer Society,2006:77-86.
[10] ZHANG Ming-bo,LU Feng,SHEN Pai-wei,et al.The evolvement and progress of R-tree family[J].Chinese Journal of Computers,2005,28(3):289-300.(in Chinese)
[11] Guttman A.R-trees:a dynamic index structure for searching[C]// Proceedings of the ACM SIGMOD International Conference on Management of data.New York:Association for Computing Machinery,1984:47-57.
[12] Güting R H,Behr T,XU Jian-qiu.Efficient k-nearest neighbor search on moving object trajectories[J].The International Journal on Very Large Data Bases,2010,19(5):687-714.

备注/Memo

备注/Memo:
收稿日期:2011-01-19;修回日期:2011-04-15
基金项目:国家自然科学基金资助项目(60773099,60973088)
作者简介:刘大有(1942-),男(汉族),河北省乐亭县人,吉林大学教授、博士生导师.E-mail:liudy@jlu.edu.cn
通讯作者:王生生(1974-),男(汉族),吉林大学教授、博士生导师.E-mail:wss@jlu.edu.cn
更新日期/Last Update: 2011-09-22