期刊文献+

空间数据库中反最远邻查询方法 被引量:2

Efficient algorithm for reverse furthest neighbor in spatial databases
下载PDF
导出
摘要 在欧式空间下反最远邻查询算法的研究已取得了很多成果,但反最远邻查询问题还未得到有效解决。本文提出一种反最远邻查询算法,有效地解决了反最远邻查询问题,查询算法采用了过滤-提炼的解决模型。在过滤阶段,提出了反远中垂线裁剪方法。该裁剪法是通过做中垂线来过滤不是查询点的反最远邻的点。在提炼阶段,提出了反远范围查询提炼方法。该提炼方法是通过判断对象点是否在设定的范围外来验证该点是否是查询点的反最远邻。最后通过实验验证了所提算法的有效性。 At present, the reverse furthest neighbor query algorithm research has made a lot of achievements in spatial databases. But the problem of reverse furthest neighbor query is not effectively resolved in spatial databases. In this paper, a new reverse k furthest neighbor query algorithm is proposed, which effectively solve the reverse k furthest neighbor query problem in spatial dat- abases. The filter-refining solution model is used in this algorithm. In the filter stage, the reverse furthest perpendicular bisector cutting method is put forward, which can filter these points that are not the reverse k furthest neighbor points through the perpen- dicular bisectors. And in the refining stage, the reverse furthest range-k refining method is proposed, which can verify the point by determining whether it is out of the range. The experimental results show that the proposed algorithm is effective and efficiency.
出处 《燕山大学学报》 CAS 2013年第5期412-419,共8页 Journal of Yanshan University
关键词 空间数据库 反最远邻 最远邻 spatial database reverse k furthest neighbor k furthest neighbor furthest neighbor
  • 相关文献

参考文献10

  • 1Roussopoulos N, Kelley S, Vincent E Nearest Neighbor Queries [C] //Proceedings of the 1995 ACM SIGMOD international con- ference on Management of data, San Jose, California, USA. 1995: 71-79.
  • 2Kom F, Muthukrishnan S. Influence sets based on reverse nearest neighbor queries [C] //Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, USA, 2001): 21)1-212.
  • 3Stanoi 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, Roma, Italy, 2001: 99-108.
  • 4Stanoi I, Agrawal D, Abbadi A E. Reverse nearest neighbor queries for dynamic databases[C]//ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2000: 44-53.
  • 5Tao Y, Papadias D, Lian X. Reverse kNN Search in Arbitrary Di- mensionality [C] //Proceedings of the Thirtieth international con- ference on Very large data bases, Toronto, Canada, 2004: 744-755.
  • 6李博涵,郝忠孝.反向最远邻的有效过滤和查询算法[J].小型微型计算机系统,2009,30(10):1948-1951. 被引量:9
  • 7Yao B, Li F, Kumar P. Reverse furthest neighbors in spatial databases [C] //Proceedings of the 25th; International Conference on Data Engineering, Shanghai, China, 2009: 664-675.
  • 8Liu J, Chen H, Furuse K, et el.. An efficient algorithm for reverse furthest neighbors query with metric index [C] //Proceedings of the 21 st international conference on Database and expert systems applications: Part II, Bilbao, Spain, 2010: 437-451.
  • 9Tran Q T, Taniar D, Safer M. Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks [J]. Transac- tions on Large-Scale Data- and Knowledge-Centered Systems, 2009,1: 353-372.
  • 10Wu W, Yang F, Chan C Y, et al.. FINCH: evaluating reverse k Nearest Neighbor queries on location data [J]. Proceedingsofthe VLDBEndowment, 2008,1 (1): 1056-1067.

二级参考文献6

  • 1Flip K, MuthttklJshnan S. Influence sets based on reverse nearest neighbor queries[ C]. SIGMOD, 2000, 201-212.
  • 2Tao Yu-fei, Yiu Man-lung. Mamoulis Nikos. Reverse nearest neighbor search in metric spaces [ J ]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(9), 1239-1252.
  • 3Sergio Cabello, Miguel Diaz-Banez J, Stefan Langerman, et al. Reverse facility location problems [ C ]. In: Proceedings of the 17 th Canadian Conference on Computational Geometry, 2005, 68-71.
  • 4Bohm C, Berchtold S, Keim D. Searching in high-dimensional spaces-index structures for improving the performance of multimedia databases[J]. ACM Computing Surveys, 2001, 33(3) : 322- 373.
  • 5Ciaccia P, Patella M, Zezula P. M-tree: an efficient access method for similarity search in metficspaces[ C]. VLDB, 1997, 426-435.
  • 6李松,郝忠孝.基于Voronoi图的反向最近邻查询方法研究[J].哈尔滨工程大学学报,2008,29(3):261-265. 被引量:27

共引文献8

同被引文献3

引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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