Redundant Bit Vectors for Searching High-Dimensional Regions

author: John Platt, Microsoft Research
published: Feb. 25, 2007,   recorded: October 2004,   views: 3553

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Many multimedia applications reduce to the problem of searching a database of high-dimensional regions to see whether any overlap a query point. There is a large literature of indexing techniques based on trees, all of which break down given high enough dimension of stored regions. We have created a new data structure, called redundant bit vectors (RBVs), that can effectively index high-dimensional regions.Using RBVs, we can search a database of 240K 64-dimensional hyperspheres, each with a different radius, up to 56 times faster than an optimized learning scan. RBVs are general-purpose, and may be useful for machine learning applications.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: