索引
sa-tree: 通过空间接近在度量空间中进行搜索
采用从空间上逐渐接近查询结果的策略,不同于通常的对候选点进行划分的做法。Navarro提出的sa-tree专门用于空间搜索(spatial searching),不同于对数据点集进行分割的分治策略,sa-tree从某个随机点开始,逐渐接近查询对象。
GNAT:大度量空间中的近邻搜索
基因序列比对、声音识别、图片识别等数据都在分布上存在一定关联性,利用这些关联性可以提升近邻搜索的性能。为了达到这个目的,要求数据结构能够反映数据的内在几何特征。GNAT通过在多个层次上将数据分割为多个区域来保留基本几何结构。
如何用度量树实现通用的相似性查询
很多实际问题需要对有限集中的元素进行有效的识别,高效的算法通常可以避免对所有点进行遍历。很多相关问题将“邻近(proximity)”定义为排列空间中的距离测量。大量用来表示高维点的数据结构仅仅考虑了凸区域中的邻近查询(proximity queries).例如k-d树,但k-d树存在的问题是当维度超过O(log n)时,找不到一种分割方法可以区分所有坐标,这意味着对树的邻近搜索只能基于坐标的一个子集。目前对通用度量树划分平面的选择还没有被广泛研究。