Faster construction of ball-partitioning-based metric access methods
Jéssica Almeida de Souza, Humberto Razente, Maria Camila N. Barioni · 2013
Most similarity search techniques for multimedia data is performed in metric spaces and with the aid of data structures known as metric access methods (MAM). Herein, we present three new node split strategies for M-tree and Slim-tree construction, the pioneer dynamic MAM. These strategies result in better distribution of elements on the tree nodes and require less distance calculations when compared with the previously proposed ones. Moreover, trees built with these strategies have shown to be more efficient for similarity queries, such as nearest neighbors. The experimental results show that trees built with the proposed strategies outperform those built with the original ones with regard to the number of disk accesses, the amount of distance calculations and time required to run the queries.