Decomposability of DiSAT for Index Dynamization

Edgar Chávez, María E. Di Genaro, Nora Susana Reyes, Patricia Roggero

  • Edgar Chávez Centro de Investigación Científica y de Educación Superior de Ensenada, México
  • María E. Di Genaro Departamento de Informática, Universidad Nacional de San Luis, Argentina
  • Nora Susana Reyes Dep. de Informática, Univ. Nacional de San Luis, San Luis, Argentina
  • Patricia Roggero Dep. de Informática, Univ. Nacional de San Luis, San Luis, Argentina
Keywords: similarity search, dynamism, metric spaces, non-conventional databases


The Distal Spatial Approximation Tree (DiSAT) is one of the most competitive indexes for exact proximity searching. The absence of parameters, the most salient feature, makes the index a suitable choice for a practitioner. The most serious drawback is the static nature of the index, not allowing further insertions once it is built. On the other hand, there is an old approach from Bentley and Saxe (BS) allowing the dynamization of decomposable data structures. The only requirement is to provide a decomposition operation. This is precisely our contribution, we define a decomposition operation allowing the application of the BS technique. The resulting data structure is competitive against the static counterparts.


Download data is not yet available.


[1] E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquı́n, “Searching in metric spaces,” ACM Computing Surveys, vol. 33, pp. 273–321, Sept. 2001.
[2] H. Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2005.
[3] P. Zezula, G. Amato, V. Dohnal, and M. Batko, Similarity Search: The Metric Space Approach, vol. 32 of Advances in Database Systems. Springer, 2006.
[4] M. Hetland, “The basic principles of metric indexing,” in Swarm Intelligence for Multi-objective Problems in Data Mining (C. Coello, S. Dehuri, and S. Ghosh, eds.), vol. 242 of Studies in Computational Intelligence, pp. 199–232, Springer Berlin / Heidelberg, 2009.
[5] G. Navarro, “Searching in metric spaces by spatial approximation,” The Very Large Databases Journal (VLDBJ), vol. 11, no. 1, pp. 28–46, 2002.
[6] J. L. Bentley and J. B. Saxe, “Decomposable searching problems i. static-to-dynamic transformation,” Journal of Algorithms, vol. 1, no. 4, pp. 301–358, 1980.
[7] B. Naidan and M. L. Hetland, “Static-to-dynamic transformation for metric indexing structures (extended version),” Information Systems, vol. 45, pp. 48 – 60, 2014.
[8] E. Chávez, M. E. D. Genaro, N. Reyes, and P. Roggero, “Distal spatial approximation forest,” Libro de Actas del XXII CACIC 2016, pp. 804–813, 2016.
[9] G. R. Hjaltason and H. Samet, Incremental Similarity Search in Multimedia Databases. No. CS-TR-4199 in Computer science technical report series, Computer Vision Laboratory, Center for Automation Research, University of Maryland, 2000.
[10] G. R. Hjaltason and H. Samet, “Index-driven similarity search in metric spaces,” ACM Transactions on Database Systems, vol. 28, no. 4, pp. 517–580, 2003.
[11] E. Chávez, V. Ludueña, N. Reyes, and P. Roggero, “Faster proximity searching with the distal sat,” Information Systems, vol. 59, pp. 15 – 47, 2016.
[12] G. Navarro and N. Reyes, “Dynamic spatial approximation trees,” Journal of Experimental Algorithmics, vol. 12, pp. 1.5:1–1.5:68, June 2008.
[13] M. H. Overmars, The design of dynamic data structures. Lecture notes in computer science, Berlin, New York: Springer-Verlag, 1983.
[14] M. H. Overmars and J. van Leeuwen, “Worst-case optimal insertion and deletion methods for
decomposable searching problems,” Information Processing Letters, vol. 12, no. 4, pp. 168– 173, 1981.
[15] K. Figueroa, G. Navarro, and E. Chávez, “Metric spaces library,” 2007. Available at Space Library.html .
How to Cite
Chávez, E., Di Genaro, M. E., Reyes, N. S., & Roggero, P. (2017). Decomposability of DiSAT for Index Dynamization. Journal of Computer Science and Technology, 17(02), e15.
Original Articles

Most read articles by the same author(s)