期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

路网中互近邻查询处理方法 被引量：1

Method for Mutual Nearest Neighbor Query in Road Networks
在线阅读 下载PDF
导出
摘要 提出路网中的互近邻查询问题.给定路网G(V,E),对象集P,查询点q,近邻数k1和k2,互近邻查询返回既是q的k1近邻,又是q的反k2近邻的对象集.为解决该问题,首先提出基础算法,即先求出查询点q的k1近邻作为候选,再验证这些候选是否为真正的结果.然后,在此基础上提出了优化算法,根据落在对象点与查询点最短路径边上的标记点个数直接排除掉一些错误的候选对象.最后,通过实验验证了优化算法的有效性. The problem of mutual nearest neighbor（MNN） query in road networks is proposed in this paper. Given road networks G （ V,E）, a set P of objects, a query object q, two parameters k1 and k2 , an MNN query returns from P, the set of objects that are among the k1 nearest neighbors of q; meanwhile, have q as one of their k1 nearest neighbors. To address this problem, firstly, the paper provides a fundamental algorithm that retrieves k1 nearest neighbors of q as candidate objects and then removes the false misses. Then, based on it, an optimal algorithm is proposed, which can remove some false misses directly according to the count of mark points which fall on the edge of shortest path between object and query. Finally, the experimental results show that the optimal algorithm is efficient and effective.
作者 陈子军 王璐 刘文远
机构地区 燕山大学信息科学与工程学院
出处 《小型微型计算机系统》 CSCD 北大核心 2011年第4期606-610,共5页 Journal of Chinese Computer Systems
基金 国家自然科学基金项目(60773100)资助
关键词 互近邻 K近邻 反k近邻 路网 MNN k nearest neighbor reverse k nearest neighbor road networks
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献2

二级参考文献21

  • 1Papadias D, Zhang J, Mamoulis N, et al. Query processing in spatial network databases[ C]. Proceedings of the 29th International Conference on Very Large DataBases, Berlin, Germany, 2003, 802- 813.
  • 2Korn F, Muthukdshnan S. Influence sets based on reverse nearest neighbor queries[ C]. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas: ACM Press, 2000,201-212.
  • 3Yang C, Lin K. An index structure for efficient reverse nearest neighbor queries [ C ]. Proceedings of the 17th International Conference on Data Engineering. Heidelberg: IEEE Computer Society Press,2001,485-492.
  • 4Maheshwari A, Vahrenhold J, Zeh N. On reverse nearest neighbor queries[ C]. Proceedings of the Canadian Conference on Computational Geometry, Alberta:ACM Press, 2002,128-132.
  • 5Stanoi I, Agrawal D, Abbadi A E. Reverse nearest neighbor queries for dynamic databases[ C]. Proceedings of ACM SIGMOD International Conference on Management of Data, Dallas: ACM Press, 2000,44-53.
  • 6Singh A, Ferhatosmanoglu H, Tosun A. High dimensional reverse nearest neighbor queries [ C ]. Proceedings of ACM International Conference on Information and Knowledge Management, New Orleans: ACM Press,2003,91-98.
  • 7Tao Y, Papadias D, Lian X. Reverse kNN search in arbitrary dimensionality [ C ]. Proceedings of the 30th International Conference on Very Large DataBases. Toronto: Morgan Kaufmann Press, 2004,744-755.
  • 8Tian Xia , Zhang Dong-hui. Continuous reverse nearest neighbor monitoring[ A]. Proceedings of the 22th International Conference on Data Engineering [ C ]. Atlanta: Computer Society Press, 2006, 77 -89.
  • 9Kyriakos M, Yiu M L. Dimitris P. Continuous nearest neighbor monitoring in road networks[ A]. Proceedings of the 32nd International Conference on Very Large Data Bases [ C ]. Seoul: ACM Press,2006,43-54.
  • 10Jensen C, Kolarvr J, TPedersen T, et al. Nearest neighbor queries in road networks[ C ]. Proc. of ACM GIS,2003,1-8.

共引文献3

同被引文献11

  • 1YAO B, LI F, Kumar P. Reverse furthest neighbors in spatial databases [C]. Proceedings of the IEEE International Conference on Data Engineering, 2009:664-675.
  • 2Korn F, Muthukrishnan S. Influence sets based on reverse nearest neighbor queries [C]. Proceedings of the ACM SIGMOD International Conference on Management of Data, 2000: 201-212.
  • 3James M Kang, Mohamed F Mokbel, Shashi Shekhar, et al. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors[C]. IEEE 23rd International Conference on Data Engineering, 2007: 806-815.
  • 4Muhammad Aamir Cheema, LIN Xuemin, ZHANG Ying, et al. Lazy updates: An efficient technique to continuously monitoring reverse kNN [J]. Proceedings of the VLDB Endowment, 2009, 2 (1): 1138-1149.
  • 5Mahady Hasan, Muhamrnad Aamir Cheema, Xuemin Lin, et al. Efficient construction of safe regions for moving kNN queries over dynamic datasets [M]. The University of New South Wales Australia SSTD, 2009: 373-379.
  • 6WU W, YANG F, CHAN C, et al. FINCH: Evaluating reverse k-nearest neighbor queries on location data [C]. Auckland, New Zealand VLDB, 2008: 1056-1067.
  • 7WU Wei, YANG Fei, Chee Yong Chan, et al. Continuous reverse k nearest-neighbor monitoring [C]. 9th International Conference on Mobile Data Management, 2008:132-139.
  • 8YIU M L, Papadias D, Mamoulis N, et al. Reverse nearest neighbors in large graphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18 (4):540-553.
  • 9LIU Jianquan, CHEN Hanxiong, Kazutaka Furuse. Hiroyuki kitagawa: An efficient algorithm for reverse furthest neighbors query with metric index [G]. LNCS 6262: Berlin Heidelberg DEXA, 2010:437-451.
  • 10Quoc Thai Tran, David Taniar. Maytham safar.. Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks [J]. Transactions on Large-Scale Data- and Knowledge-Centered Systems Ⅰ, 2009: 353-372.

引证文献1

二级引证文献3

小型微型计算机系统
2011年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部