An efficient alternative for deletions in dynamic spatial approximation trees
Keywords:Multimedia database, Metric spaces, Similarity search, Indexing, Algorithms
Metric space searching is an emerging technique to address the problem of similarity searching in many applications. In order to efficiently answer similarity queries, the database must be indexed. In some interesting real applications dynamism is an indispensable property of the index. There are very few actually dynamic indexes that support not only searches, but also insertions and deletions of elements. The dynamic spatial approximation tree (DSAT) is a data structure specially designed for searching in metric spaces, which compares favorably against other data structures in high dimensional spaces or queries with low selectivity. Insertions are efficient and easily supported in DSAT, but deletions degrade the structure over time. Several methods are proposed to handle deletions over the DSAT. One of them has shown to be superior to the others, in the sense that it permits controlling the expected deletion cost as a proportion of the insertion cost and searches does not overly degrade after several deletions. In this paper we propose and study a new alternative deletion method, based on the better existing strategy. The outcome is a fully dynamic data structure that can be managed through insertions and deletions over arbitrarily long periods of time without any significant reorganization.
 S. Brin. Near neighbor search in large metric spaces. In Proc. 21st Conference on Very Large Databases (VLDB’95), pages 574–584, 1995.
 E. Chávez, G. Navarro, R. Baeza-Yates, and J. Marroquín. Searching in metric spaces. ACM Computing Surveys, 33(3):273–321, Sept.2001.
 K. Figueroa, G. Navarro, and E. Chávez. Metric spaces library, 2007. Available at http://www.sisap.org/Metric Space Library.html.
 G. Hjaltason and H. Samet. Incremental similarity search in multimedia databases. Technical Report CS-TR-4199, University of Maryland, Computer Science Department, 2000.
 F. Kasi´an and V. Ludue˜na and N. Reyes and P. Roggero. New Deletion Method for Dynamic Spatial Approximation Trees. Proc. XIX Congreso Argentino de Cs. de la Computación. Págs. 1023–1032, 2013.
 G. Navarro. Searching in metric spaces by spatial approximation. In Proc. String Processing and Information Retrieval (SPIRE’99), pages 141–148. IEEE CS Press, 1999.
 G. Navarro. Searching in metric spaces by spatial approximation. The Very Large Databases Journal (VLDBJ), 11(1):28–46, 2002.
 G. Navarro and N. Reyes. Dynamic spatial approximation trees. ACM Journal of Experimental Algorithmics, 12:article 1.5, 2008. 68 pages.
 G. Navarro and N. Reyes. Dynamic spatial approximation trees for massive data. In T. Skopal and P. Zezula, editors, SISAP, pages 81–88. IEEE Computer Society, 2009.
 R. Uribe and G. Navarro. Una estructura dinámica para b´usqueda en espacios métricos. In Actas del XI Encuentro Chileno de Computación, Jornadas Chilenas de Computación, Chillán, Chile, 2003. In Spanish. In CD-ROM.