Abstract

Proximity searches in metric spaces are related with several real world applications, as pattern recognition and multimedia information retrieval. Information has grown larger with time, so memory efficient structures to store it have been needed. Proximity search K nearest neighbors was implemented in compact data structure k2tree using a priority queue approach, being compared with multiple others structures and their respective approaches, resulting competitive among all, but it is specially surpassed by Quad trees with incremental radius approach in synthetical data. In this work, we propose to implement K nearest neighbors query on k2tree using incremental radius approach with compact count, in order to improve its performance. A theoretical analysis supports our proposal, and preliminary experimental results are shown, where our approach is competitive. A possible improvement is discussed afterwards.