全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种快速的反向k近邻查找算法及其改进

Keywords: 最近邻,反向k近邻,索引块

Full-Text   Cite this paper   Add to My Lib

Abstract:

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.

References

[1]  CABELLO S,DIAZ-BANEZ J M,LANGERMAN S,et al.Facility location problems in the plane based on reversenearest neighbor queries[J].European Journal ofOperational Research,2010,202:99-106.
[2]  GUTTMAN A.R-trees:a dynamic index structure forspatial searching[C]∥Proceeding of ACM SIGMODinternational conference on management of data,BostonMassachusetts,June 18-21,1984:47-57
[3]  CHEEMA M A,ZHANG Wen-jie,LIN Xue-min,et al.Continuous reverse k nearest neighbors queries inEuclidean space and in spatial networks[J].TheInternational Journal on Very Large Data Bases,2012,21:69-95.
[4]  KORN F,MUTHUKRISHNAN S,SRIVASTAVA D.Reverse nearest neighbor aggregates over data streams[C]∥Proceeding of the 28th VLDB conference,Hong Kong,August 20-23,2002:814-825.
[5]  ACHTERT E,BOHM C,KROGER P,et al.Efficientreverse k-nearest neighbor search in arbitrary metric spaces[C]∥Proceedings of 2006 ACM SIGMOD InternationalConference on Management of Data,Chicaco,June 27-29,2006:515-526.
[6]  ACHTERT E,KRIEGEL H P,KROGER P,et al.Reverse k-nearest neighbor search in dynamic and generalmetric databases[C]∥EDBT,Saint-Petarburg,March24-26,2009:886-897.
[7]  KORN F,MUTHUKRISHNAN S.Influence sets based onreverse nearest neighbor queries[C]∥Proceedings ofACM SIGMOD International Conference Management ofData,Dallas,May 14-19,2000:201-212.
[8]  LIN King-Ip,NOLEN M,YANG Cong-jun.Applying bulkinsertion techniques for dynamic reverse nearest neighborproblems[C]∥Proceeding Database Engineering andApplications Symposium,Hong Kong,July 16-18,2003:290-297.
[9]  YANG Cong-jun,LIN King-Ip.An index structure forefficient reverse nearest neighbor queries[C]∥Proceedingof International Conference on Data Engineering,Heidelberg,April 2-6,2001:485-492.
[10]  TAO Yu-fei,YIU Man-lung,MAMOULIS N.Reversenearest neighbor search in metric spaces[J].IEEETransactions on Knowledge and Data Engineering,2006,18(9):1239-1252.
[11]  CHEEMA M A,LIN Xue-min,ZHANG Wen-jie,et al.Influence zone:efficiently processing reverse k nearestneighbors queries[C]∥IEEE 27th InternationalConference on Data Engineering(ICDE),Hannover,April 11-16,2011:577-588.
[12]  KOLAHDOUZAN M,SHAHABI C.Voronoi-based knearest neighbor search for spatial network databases[C]∥Proceeding of the 30th VLDB Conference,Toronto,August 29-September 3,2004:840-851.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133