一种快速的反向k近邻查找算法及其改进 |
| |
引用本文: | 骆炎民,柳培忠,陈汉雄. 一种快速的反向k近邻查找算法及其改进[J]. 北京工业大学学报, 2012, 38(12) |
| |
作者姓名: | 骆炎民 柳培忠 陈汉雄 |
| |
作者单位: | 1. 华侨大学计算机科学与技术学院,厦门,361021 2. 华侨大学工学院,福建泉州,362021 3. 筑波大学计算机科学系,日本茨城305—8577 |
| |
基金项目: | 福建省自然科学基金资助项目,泉州市科技计划项目 |
| |
摘 要: | 提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.
|
关 键 词: | 最近邻 反向k近邻 索引块 |
Fast Reverse k Nearest Neighbor Search Algorithm and Its Improvement |
| |
Abstract: | This paper presents an efficient reverse k nearest neighbor search algorithm.Under the conditions that the secondary storage is cheap and the current computers are powerful enough,the algorithm pre-computes the mutual distance between objects of the dataset,and organizes them into index blocks that are stored in secondary memory and can be update offline automatically by the computer.Only the necessary block into memory is needed,and the reverse k nearest neighbor(RkNN) query for any k can be straightforwardly dore.The time complexity of the query is O(N).To reduce the consumption of the I/O cost for the index block,this paper proposes a method to compress the index block by using the necessary binary bits to store the distance and reducing the redundancy to a minimum level,which effectively improves the efficiency of the algorithm.Finally,experiments show the effectiveness and efficiency of the proposed algorithms. |
| |
Keywords: | nearest neighbor reverse k nearest neighbor (RkNN) index block |
本文献已被 万方数据 等数据库收录! |
|