The paper "Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces" by Jeffrey S. Beis and David G. Lowe discusses the challenges and solutions for efficient shape indexing in high-dimensional feature spaces. The authors highlight the importance of using high-dimensional features for improved discrimination in large model databases but note that traditional methods, such as hash tables, become inefficient as the dimensionality increases. They introduce a new variant of the k-d tree search algorithm called Best Bin First (BBF) search, which efficiently finds approximate nearest neighbours for a large fraction of queries and very close neighbours for the rest. This technique is integrated into a recognition system that can detect complex objects in cluttered scenes within seconds. The paper reviews previous indexing methods, including hash tables and geometric hashing, and discusses the limitations of these approaches in high-dimensional spaces. It also presents experimental results demonstrating the effectiveness of BBF search in various scenarios, such as uniform distribution, hash table lookup, and synthetic model databases. The authors conclude that BBF search is capable of finding close neighbours over a wide range of dimensions and for large numbers of stored points, making it a practical solution for shape indexing in high-dimensional spaces. The method's efficiency is further highlighted in its potential applications in appearance-based recognition.The paper "Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces" by Jeffrey S. Beis and David G. Lowe discusses the challenges and solutions for efficient shape indexing in high-dimensional feature spaces. The authors highlight the importance of using high-dimensional features for improved discrimination in large model databases but note that traditional methods, such as hash tables, become inefficient as the dimensionality increases. They introduce a new variant of the k-d tree search algorithm called Best Bin First (BBF) search, which efficiently finds approximate nearest neighbours for a large fraction of queries and very close neighbours for the rest. This technique is integrated into a recognition system that can detect complex objects in cluttered scenes within seconds. The paper reviews previous indexing methods, including hash tables and geometric hashing, and discusses the limitations of these approaches in high-dimensional spaces. It also presents experimental results demonstrating the effectiveness of BBF search in various scenarios, such as uniform distribution, hash table lookup, and synthetic model databases. The authors conclude that BBF search is capable of finding close neighbours over a wide range of dimensions and for large numbers of stored points, making it a practical solution for shape indexing in high-dimensional spaces. The method's efficiency is further highlighted in its potential applications in appearance-based recognition.