一种聚类分离的分布式索引方法

摘要

本发明提出了一种聚类分离的分布式索引方法，简称CS‑Chord（Clustering separation‑Chord）。在M‑Chord分布式索引中，聚类的边缘向量一般比较稀少，这些稀少的向量使得每个聚类的半径变得很大。在范围查询的时候，半径越大的聚类越容易与范围查找的区域相交，从而使得候选查找的区域增多。而聚类的边缘向量又通常是高访问量的向量，性能进一步降低。本发明所述的CS‑Chord将聚类边缘的稀疏向量分离出来并集中存储在独立的服务器上，将稠密向量存储在Chord环中，查找时一方面高频的查询集中在独立服务器的向量，另一方面也减少了Chord环上的搜索范围，从而提高检索效率。

主权项

一种聚类分离的分布式索引方法，其特征在于，包括以下步骤：步骤一：分离边缘稀疏向量，并使用独立的服务器集中存储边缘稀疏向量；步骤二：建立分布式索引，计算需要加入Chord环的边缘稀疏向量S的一维关键值Key(S)，并将该向量插入到分布式索引，向量插入的具体过程为；(21)如果Key(S)≥n*C，其中n为聚类子空间的个数，C是一个常量，其值大于IDistance索引结构中环体内的向量映射到一维轴上的所有值，则将关键值Key(s)和向量S发送到独立的服务器上，然后将向量S插入到该独立服务器的B⁺‑Tree索引中，则该新向量插入完成；若Key(s)<n*C转向步骤(22)；(22)通过位置保持哈希函数对Key(s)进行哈希，生成分配到Chord环上的关键值Key_Chord，利用Chord定位算法，查找关键值Key_Chord应存储的节点IP地址，将Key_Chord和该向量S发送到该节点上，然后将向量S插入到节点的B⁺‑Tree索引中，索引建立完成；步骤三：基于所构建的索引进行范围查询，设聚类分离的分布式索引方法CS‑Chord的范围查询Range(Q，r)，其中Q为待查向量，r为查询范围半径，步骤如下：(31)通过IDistance计算出范围查询Range(Q，r)与聚类的相交区域，映射为多个关键值区间[xi，yi]；(32)如果xi≥n*C，则将步骤(31)计算范围查询Range(Q，r)与聚类的相交区域发送到独立服务器上，转步骤(34)，如果xi＜n*C则转向步骤(33)；(33)生成Chord环中的关键值范围[h(xi)，h(yi)]，通过查询路由表定位关键值h(xi)所在的节点，如果h(yi)大于节点中所存数据的关键值最大值Key_max，则将范围[Key_max，h(yi)]发送到该节点的后继节点，如果h(yi)仍比后继节点的Key_max大，则继续往它的后继节点发送查询信息，(34)每一个节点接收到查询请求，在此节点的B⁺‑Tree中检索关键值范围中是否有向量存在，若存在向量Z则与待查向量Q进行距离计算，当距离小于查询半径r，则将向量Z返回到最初发送请求的节点，若距离大于或等于查询半径r时，则返回空值；若不存在向量，也返回空值。