Paper Info
Title
An Approximate Nearest Neighbours Search Algorithm Based on the Extended General Spacefilling Curves Heuristic
Abstract
In this paper, an algorithm for approximate nearest neighbours search in vector spaces is proposed. It is based on the Extended General Spacefilling Curves Heuristic (EGSH). Under this general scheme, a number of mappings are established between a region of a multidimensional real vector space and an interval of the real line, and then for each mapping the problem is solved in one dimension. To this end, the real values that represent the prototypes are stored in several ordered data structures (e.g. b-trees). The nearest neighbours of a test point are then efficiently searched in each structure and placed into a set of candidate neighbours. Finally, the distance from each candidate to the test point is measured in the original multidimensional space, and the nearest one(s) are chosen.
Year
DOI
Venue
1998
10.1007/BFb0033294
SSPR/SPR
Keywords
Field
DocType
approximate nearest neighbours search,extended general spacefilling curves,data structure,vector space
Data structure,Vector space,Nearest neighbour,Heuristic,Search algorithm,Real line,Computer science,Pattern analysis,Algorithm
Conference
ISBN
Citations 
PageRank 
3-540-64858-5
5
0.65
References 
Authors
17
2
Name
Order
Citations
PageRank
Juan C. Pérez-Cortés113716.20
Enrique Vidal246434.73