This paper presents a method for shape indexing using approximate nearest-neighbour search in high-dimensional spaces. The authors propose a new variant of the k-d tree search algorithm called Best Bin First (BBF), which is efficient for finding approximate nearest neighbours in high-dimensional feature spaces. The BBF search is integrated into a recognition system that can detect complex objects in real, cluttered scenes in a few seconds. Shape-based indexing uses feature vectors from an image to access an index structure, rapidly recovering possible matches to a database of object models. This approach is more efficient than exhaustive comparison, though it requires some offline preprocessing to create the index and additional memory to store it. The goal of indexing is to recover the most similar model shapes to a given image shape, which corresponds to finding nearest neighbours in a feature space. Previous indexing methods have used hash tables, but they are inefficient in high-dimensional spaces. The k-d tree is a more efficient data structure for nearest-neighbour search, though it suffers from the "curse of dimensionality." The BBF search algorithm improves upon the k-d tree by efficiently finding approximate neighbours, making indexing in high-dimensional spaces practical. The BBF search is more efficient than other methods, such as restricted k-d tree search, and performs well in high-dimensional spaces. The authors demonstrate that BBF search is effective in high-dimensional spaces, with experiments showing that it can find close neighbours over a wide range of dimensions and for very large numbers of stored points. The BBF method is also applicable to other areas such as appearance-based recognition, where objects are represented as low-dimensional manifolds embedded in high-dimensional spaces. The BBF search is more efficient than current methods for this task. The authors also compare BBF search with hash table lookup, showing that hash tables perform poorly in high-dimensional spaces. They present experiments using synthetic data and non-uniform data, demonstrating the effectiveness of BBF search in various scenarios. The results show that BBF search is significantly faster than exact k-d tree search, with a speedup factor of up to 60 in some cases. The BBF method is able to find a high percentage of the exact neighbours, even when only a small fraction of the points are examined. The method is also robust to noise and occlusion, making it suitable for real-world applications.This paper presents a method for shape indexing using approximate nearest-neighbour search in high-dimensional spaces. The authors propose a new variant of the k-d tree search algorithm called Best Bin First (BBF), which is efficient for finding approximate nearest neighbours in high-dimensional feature spaces. The BBF search is integrated into a recognition system that can detect complex objects in real, cluttered scenes in a few seconds. Shape-based indexing uses feature vectors from an image to access an index structure, rapidly recovering possible matches to a database of object models. This approach is more efficient than exhaustive comparison, though it requires some offline preprocessing to create the index and additional memory to store it. The goal of indexing is to recover the most similar model shapes to a given image shape, which corresponds to finding nearest neighbours in a feature space. Previous indexing methods have used hash tables, but they are inefficient in high-dimensional spaces. The k-d tree is a more efficient data structure for nearest-neighbour search, though it suffers from the "curse of dimensionality." The BBF search algorithm improves upon the k-d tree by efficiently finding approximate neighbours, making indexing in high-dimensional spaces practical. The BBF search is more efficient than other methods, such as restricted k-d tree search, and performs well in high-dimensional spaces. The authors demonstrate that BBF search is effective in high-dimensional spaces, with experiments showing that it can find close neighbours over a wide range of dimensions and for very large numbers of stored points. The BBF method is also applicable to other areas such as appearance-based recognition, where objects are represented as low-dimensional manifolds embedded in high-dimensional spaces. The BBF search is more efficient than current methods for this task. The authors also compare BBF search with hash table lookup, showing that hash tables perform poorly in high-dimensional spaces. They present experiments using synthetic data and non-uniform data, demonstrating the effectiveness of BBF search in various scenarios. The results show that BBF search is significantly faster than exact k-d tree search, with a speedup factor of up to 60 in some cases. The BBF method is able to find a high percentage of the exact neighbours, even when only a small fraction of the points are examined. The method is also robust to noise and occlusion, making it suitable for real-world applications.