高维主存kNN连接索引结构的核心算法

计算机科学 ›› 2011, Vol. 38 ›› Issue (9): 146-149.

高维主存kNN连接索引结构的核心算法

刘艳,郝忠孝

(哈尔滨理工大学计算机科学与技术学院哈尔滨 150080);(长春大学计算机科学技术学院长春 130022);(哈尔滨工业大学计算机科学与技术学院哈尔滨 150001)

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受黑龙江省自然科学基金(F200601)资助

Core Algorithm of High-dimensional Main Memory kNN-Join Index Structure

LIU Yan,HAO Zhong-xiao

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： kNN(k最近邻)连接是高维数据库中的一种重要但代价昂贵的基本操作。随着RAM容量越来越大且价格逐渐低廉，更多的数据集能够被装入主存。如何实现快速主存kNN连接，引起人们的关注。索引p-tree-R和p-tree-S是根据kNN连接的特点专门为主存kNN连接设计的索引。结合编码、节点中心重合技术，给出了构建p-trc} R和p-tree-S的核心算法及相关证明，实验表明，基于该索引的主存kNN连接算法p-tree-KNN-J oin明显优于目前已存在的可用于主存的kNN连接算法Gordcro

关键词: kNN连接，高维空间，主存，索引结构，kNN搜索

Abstract: kNN-Join is an important but costly primitive operation of high-dimensional databases. As RAM gets cheaper and larger,more and more datasets can fit into the main memory,how to realize the kNN-Join efficiently brings people's interests. 4-trecR and 4-trecS were designed especially for main-memory kNN-Join according to the properties of it.The core algorithms and relevant certificates of building them were presented combining with coding and node center coincidence technologies. Experiments show that the algorithrr}p-tree-kNN-Join based on p-tree-R and p-tree-S is superior to the existing kNN-Join algorithm of Gorder that can be used in main memory.

Key words: kNN-Join,High-dimensional space, Main-memory, Index structure, kNN search

刘艳,郝忠孝. 高维主存kNN连接索引结构的核心算法[J]. 计算机科学, 2011, 38(9): 146-149. https://doi.org/

LIU Yan,HAO Zhong-xiao. Core Algorithm of High-dimensional Main Memory kNN-Join Index Structure[J]. Computer Science, 2011, 38(9): 146-149. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed