结合聚类和街区距离的高维向量搜索方法

摘要

本发明是结合聚类和街区距离的高维向量搜索方法。在本发明中，提出了一种结合聚类和街区距离的索引结构CBlockB-tree，它首先采用聚类算法对高维向量集进行簇划分，然后为各簇数据构建BlockB-tree，形成CBlockB-tree。该索引结构进行检索时，通过聚类能过滤一部分与查询区域不相交的簇数据，通过高维到一维转换后的key值比较，能进一步减少最终向量相似度匹配的运算量，加快高维向量的搜索速度。同时，该索引结构能够有效支持简单高效的街区距离进行匹配搜索。

主权项

结合聚类和街区距离的高维向量搜索方法，其特征在于具体步骤如下：1)采用聚类算法对高维向量集进行簇划分，得到各簇数据的聚类中心和聚类半径；2)为各簇数据选取一个参考点，然后将该簇数据中的各高维向量逐一采用该高维向量对所选参考点间的街区距离映射为一维key值，并采用该簇数据的所有高维向量和其对应的key值为该簇数据构建BlockB‑tree，该BlockB‑tree采用B+‑tree索引结构来管理上层的key值，同时叶子节点层的每个key值都绑定一个指向对应高维向量的指针；3)将各簇数据的聚类中心和聚类半径都绑定一个指向其对应簇数据所构建BlockB‑tree的指针，形成CBlockB‑tree；当向CBlockB‑tree插入一个高维向量时，首先根据该高维向量到各簇数据聚类中心的距离值，选取距离该高维向量最近的簇数据进行插入操作，更新聚类半径，然后根据待插入向量到该簇数据所选参考点间的街区距离得到待插入向量的一维key值，根据该key值的大小定位其应插入到该簇数据对应BlockB‑tree中的某一叶子节点，如果该叶子节点未满，则直接将key值插入到该叶子节点中，并产生指向对应高维向量的指针，更新其父节点对应的key值；如果该叶子节点已满，处理的方式如下：31)如果该叶子节点的左右兄弟节点存在未满的情况，则结合其左右兄弟节点，进行待插入高维向量和key值的插入，并更新其父节点对应的key值；32)如果其左右兄弟节点均满，则结合待插入的高维向量和key值，直接对该叶子节点进行分裂，并将分裂后新产生的叶子节点插入到其父节点中，同时更新其父节点对应的key值，如果父节点也已满，分裂过程继续向上传递，并更新对应的key值；4)进行检索时，通过查询范围过滤掉那些与查询区域不相交的各簇数据，对与查询范围相交的各簇数据进行搜索，在与查询范围相交的各簇数据中的搜索方法为：计算查询向量和该簇数据所选参考点间的街区距离得到在该簇数据中的查询key值，根据查询范围和查询key值，得到需要进行搜索的key值的起始位置和结束位置，扫描计算这些key值对应的高维向量与查询向量间的距离，将在查询范围内的高维向量返回，得到检索结果。