Redundant Bit Vectors for Searching High-Dimensional Regions
author: John Platt,
Microsoft Research
published: Feb. 25, 2007, recorded: October 2004, views: 3553
published: Feb. 25, 2007, recorded: October 2004, views: 3553
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.
Description
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: