A new approach for similarity queries using proximity graphs
Alexander Ocsa, Carlos Bedregal, Ernesto Cuadros-Vargas · 2007
Proximity graphs have been widely used in the area of computa- tional geometry; through a vicinity concept these graphs establish relations of similarity between elements of a set. In this paper we propose the use of Relative Neighborhood Graph (RNG) in metric spaces in order to e-ciently answer similarity queries. Additionally we introduce a new algorithm for range queries and nearest neighbor queries making use of the spatial approx- imation in graphs. Experiments show that our proposal has a comparable performance in terms of Number of Distance Calculations (NDC) and time.