"Adaptive Cluster Distance Bounding"could obtain tighter distance bounds between the query and clusters, but this method suffers large amount of distance bound computations, can't take both filtration capacity and CPU performance when the number of clusters increases, and doesn't provide effective pruning mechanisms inside the candidate clusters yet. In this paper, a new indexing method called TreeHB is provided to improve the performance of nearest-neighbor search, which is based on two improvements of existing hyperplane method. Firstly, this paper divides clusters with hierarchic methods, and manages the clustering results with a tree structure to ensure the premise filtering capabilities and reduce the amount of computation and the CPU cost. Secondly, a new pruning algorithm is designed to reject the irrelevant points in the candidate clusters further and reduce the IO cost. It turns out that the new approach outperforms the original hyperplane method and other popular high-dimensional indexing methods.%"自适应集群距离边界"高维索引方法虽可得到查询点与聚类之间更紧致的距离边界,但该方法需要大量的边界距离计算,当集群个数增加时无法兼顾过滤能力和CPU性能,且没有在候选集群内部提供高效的剪除机制.本文提出一种新的以超平面聚类为基础的索引结构TreeHB来提升最近邻查询性能.首先,用层次化聚类方法聚类,将聚类结果用树形结构进行管理,在保证过滤能力的前提下,可降低距离下界计算量,减少CPU开销.其次,在候选集群内部设计一种新的剪除机制,进一步过滤无关数据元,降低I/O开销.结果证明,这种新方法性能优于原有的超平面索引方法及其他著名的高维索引方法.
展开▼
