AngleTree: the Smarter Search in High Dimensional Space

Ref: 13132
Generalisation of kd-tree to take advantage of intrinsic structure of high dimentional data for more efficent similarity search

Key advantages
  • Much faster, as accurate
  • Low memory usage
  • Suitable for high-dimensional data eg images, videos

Background

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.

The invention

Figure 1: A query image and its nearest neighbour from the Extended Yale Face Database B, found afte

Figure 1: A query image and its nearest neighbour from the Extended Yale Face Database B, found after searching through only 3.8% of the 2432 images in the database.

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.

Applications

Multimedia search, content based image/video search, contextual advertising, computer vision, optical character recognition

Principal inventors

  • Ilia Zvedeniouk
  • Sanjay Chawla