Angle-Tree: a new index structure for high-dimensional point data
Daoguo Dong, Xiangyang Xue, Hangzai Luo, Yingqiang Lin · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2001
Many multi-dimensional index structures, such as R-Tree, R*-Tree, X-Tree, SS-Tree, VA-File, etc. have been proposed to support similarity search with l1, l2 or l(infinity ) distance as similarity measure. But they can not support such similarity search with cosine as the similarity measure. In this paper, an index structure Angle-Tree is introduced to resolve the problem. It first projects all the high dimensional points onto the unit hyper-spherical surface, i.e. normalize each original vector in the database into a unit one. Then an index structure similar to R-Tree is built for those projected points. The experimental results show that the Angle-Tree can decrease the cost of disk I/O and support fast similarity search.