An Index Data Structure for Searching in Metric Space Databases
Roberto Uribe, Gonzalo Navarro, Ricardo Barrientos, and Mauricio Marín
This paper presents the Evolutionary Geometric Near-neighbor Access
Tree (EGNAT) which is a new data structure devised for searching
in metric space databases. The EGNAT is fully dynamic, i.e., it allows
combinations of insert and delete operations, and has been optimized
for secondary memory. Empirical results on different databases show that
this tree achieves good performance for high-dimensional metric spaces.
We also show that this data structure allows efficient parallelization
on distributed memory parallel architectures. All this indicates that
the EGNAT is suitable for conducting similarity searches on very
large metric space databases.