结构化对等计算系统中的高维相似搜索  

High-Dimensional Similarity Search on a Structured P2P Network

作　　者：徐林昊[1] 周傲英[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机学报》2006年第11期1982-1994,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(60373019);国家教育部博士点基金(20030246023);上海市科委重大项目基金(03DZ15028);新加坡资讯通信发展管理局基金资助.

摘　　要：对等计算数据管理中的一个重要问题是如何有效地支持高维空间中的相似性搜索.文章采用了一种有效的空间划分策略,提出了一种基于Chord系统的相似搜索方法.首先,利用预先选定的代表点对整个数据空间进行划分,使得每个代表点对应唯一的一个子空间且所有子空间的体积之和等于整个数据空间的体积.然后,将这些代表点映射到一维区间,使得每个代表点被赋予一个唯一的标识.将代表点的标识作为Chord系统中的节点散列值,就构造出一种改进的Chord系统.最后,利用Chord系统的路由协议,以代表点的标识为查找键就可以访问到所有与搜索区域相交的子空间对应的节点.仿真实验表明,在查询处理代价和调节负载均衡方面,与现有的方法相比(如MUCK),文中提出的方法更加有效.An important problem that confronts Peer-to-Peer （P2P） based data management is efficient support for similarity search over a high dimensional data space. This paper addresses this problem based on the Chord system by means of an efficient space partitioning strategy. The whole data space is first partitioned based on a set of pre-generated reference points. Each reference point has an associated subspace and the union of all subspaces spans the whole data space. Then, all reference points are mapped into a single-dimensional range, and each reference point is identified with a unique number. Thus, a suitably modified Chord system is formed by treating the identifier of each reference point as the node hash value for Chord system. As such, similarity queries could be accomplished by using the reference points as search key, and nodes corresponding to subspaces that intersect the search region could be reached as in Chord. Finally, the proposed approach is compared with the MUCK via simulation. Extensive experiments show that the approach proposed by the authors has advantages for query processing cost and load balancing.

关 键 词：对等计算 相似搜索 代表点 空间划分 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]