Redundant Bit Vectors for Searching High-Dimensional Regions

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.