期刊文献+

一种障碍空间中的反k最近邻查询方法 被引量:14

A Method for Reverse k-Nearest-Neighbor Queries in Obstructed Spaces
下载PDF
导出
摘要 随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象(RkNN)的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种基于障碍Voronoi图的高效的剪枝方法.根据Voronoi图和障碍距离的特性,大幅度减少了数据点处理个数.最后,作者使用真实的数据集和多种方式分布的模拟数据,验证了算法的高效性和准确性. With the rapid development of location-based services(LBS) and the Internet of Things,technologies for spatial queries are becoming more and more important.Moreover,nearest neighbor queries and the variant are widely used spatial queries.Recently,there has been much work on reverse k nearest neighbors(RkNN) queries.However,these studies are proposed for the ideal Euclidean Space.Queries for reverse k nearest neighbors are influenced by obstacles in practice.In this paper,we study a method for reverse k nearest neighbors queries in obstructed spaces,and propose efficient pruning algorithms based on an obstructed Voronoi diagram.Furthermore,these pruning methods greatly reduce the number of searched points by properties of Voronoi diagrams and obstructed distance.Finally,our experiments based on real and synthetic data sets demonstrate the efficiency and accuracy of our proposed approach.
出处 《计算机学报》 EI CSCD 北大核心 2011年第10期1917-1925,共9页 Chinese Journal of Computers
基金 国家自然科学基金(61003058 60873009) 辽宁省博士启动基金(20091025) 中央高校基本科研业务费专项资金(090404013)资助~~
关键词 空间查询 反k最近邻(RkNN) 障碍空间 VORONOI图 spatial query Reverse kNN obstructed space Voronoi diagram
  • 相关文献

参考文献15

  • 1Zhang J, Zhu M, Papadias D, Tao Y. Location-based spatial queries//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York, USA, 2003:443-454.
  • 2Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York, USA, 1995: 71- 79.
  • 3赵政璋 何志新.储层预测技术及应用事例[M].北京:石油工业出版社,2000..
  • 4Gao Y, Zheng B, Chen Get al. Continuous visible nearest neighbor query processing in spatial databases. VLDB Journal, 2010, 20(3): 371- 396.
  • 5Sharifzadeh M, Shahaloi C. The spatial skyline queries//Proceedings of the VLDB. Seoul, Korea, 2006:751-762.
  • 6Lee K C, Lee W C, Zheng B et al. Z-SKY: An efficient skyline query processing framework based on Z-order. VLDB Journal, 2010, 19(3): 333-362.
  • 7Stanoi I, Agrawal D, Abbadi A E. Reverse nearest neighbor queries for dynamic databases//Proceedings of ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 2000: 44-53.
  • 8Tao Y, Papadias D, Lian X. Reverse kNN search in arbitrary dimensionality//Proceedings of the VLDB. Toronto, Canada, 2004:744-755.
  • 9Sharifzadeh M, Shahabi C. VoR-Tree: R-trees with voronoi diagrams for efficient proeessing//Proceedings of the VLDB. Singapore, 2010, 1231-1242.
  • 10Wu W, Yang F, Chan C Yet al. Finch: Evaluating reverse k-nearest-neighbor queries on location data//Proceedings of the VLDB. Auckland, New Zealand, 2008:1056-1067.

共引文献1

同被引文献88

  • 1朱良,孙未未,荆一楠,杜江帆.基于Voronoi图的路网k聚集最近邻居节点查询方法[J].计算机研究与发展,2011,48(S3):155-162. 被引量:5
  • 2卢炎生,何亚军,潘鹏.EINN最近邻居查询索引遍历算法改进[J].计算机工程与科学,2005,27(7):62-64. 被引量:2
  • 3邓聚龙.灰色预测与决策[M].武汉:华中理工大学出版社,1987..
  • 4Zhang J, Zbu ML, Papadias D, Tao YF, Lee DL. Location-Based spatial queries. In: Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. San Diego: ACM Press, 2003. 443-454. [doi:10.1145/872757.872812].
  • 5Roussopoulos N, Kelley S, Vincent F, Nearest neighbor queries. In: Proc. of the '95 ACM SIGMOD Int'l Conf. on Management of Data. San Jose: ACM Press, 1995.71-79. Idol: 10.1145/223784.223794].
  • 6Berchtold S, Ertl B, Keim DA, Kriegel HP, Seidl T. Fast nearest neighbor search in high-dimensional space. In: Proc. of the 14th Int'l Conf. on Data Engineering. Orlando: IEEE Computer Society, 1998.209-218. [doi: 10.1109/ICDE.1998.655779].
  • 7Gao YJ, Zheng BH, Chen GC, Li Q, Guo XF. Continuous visible nearest neighbor query processing in spatial databases. VLDB Journal, 2011,20(3):371-396. [doi: 10.1007/s00778-010-0200-z].
  • 8Sharifzadeh M, Shahabi C. The spatial skyline queries. In: Proc. of the 32nd Int'l Conf. on Very Large Data Bases. Seoul: ACM Press, 2006.751-762.
  • 9Lee KCK, Lee WC, Zheng BH, Li HJ, Tian Y. Z-SKY: An efficient skyline query processing framework based on Z-order. VLDB Journal, 2010,19(3):333-362. [doi: lO.lO07/sOO778-OO9-O166-x].
  • 10Stanoi 1, Agrawal D, Abbadi AE. Reverse nearest neighbor queries for dynamic databases. In: Proc. of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 2000.44-53.

引证文献14

二级引证文献31

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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