AngleTree: the Smarter Search in High Dimensional Space
Generalisation of kd-tree to take advantage of intrinsic structure of high dimentional data for more efficent similarity search
Currently, similarity search in high-dimensional space degenerates to brute-force with standard indexing techniques.
In applications such as image search engines where many searches are performed, brute force search is not practical. A fast and efficient indexing structure is needed to make high dimensional search practical.
This technology splits the structure into half-spaces with splitting hyperplanes as in a kd-tree, but in addition this technology stores the angles that these hyperplanes make with the data region.
These angles can then be used to efficiently prune the space during search by obtaining a much tighter lower bound on distance of subspace to query point.
This results in very fast search and low space usage particularly for high dimensional databases ie databases with thousands to over 1 million dimensions.
Multimedia search, content based image/video search, contextual advertising, computer vision, optical character recognition
- Ilia Zvedeniouk
- Sanjay Chawla