Clindex: Clustering for Similarity Queries in High-Dimensional Spaces.
Cheng‐Xin Li, En‐Chi Chang, Héctor García-Molina, Junting Wang, Gio C. M. Wiederhold · 1999
In this paper we present a clustering and indexing paradigm (called Clindex) for highdimensional search spaces. The scheme is designed for approximate searches, where one wishes to find many of the data points near a target point, but where one can tolerate missing a few near points. For such searches, our scheme can find near points with high recall in very few IOs and performs significantly better than other approaches. Our scheme is based on finding clusters, and then building a simple but efficient index for them. We analyze the tradeoffs involved in clustering and building such an index structure, and present experimental results based on a 30,000 image database.