Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Decomposability of DiSAT for Index Dynamization
Edgar Chávez, María E. Di Genaro, Nora Susana Reyes, Patricia Roggero
DOI:
https://doi.org/10.24215/16666038.17.e15Keywords:
similarity search, dynamism, metric spaces, non-conventional databasesAbstract
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.
Downloads
Download data is not yet available.
References
[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 http://www.sisap.org/Metric Space Library.html .
[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 http://www.sisap.org/Metric Space Library.html .
Downloads
Published
2017-10-01
How to Cite
Chávez, E., Di Genaro, M. E., Reyes, N. S., & Roggero, P. (2017). Decomposability of DiSAT for Index Dynamization: Edgar Chávez, María E. Di Genaro, Nora Susana Reyes, Patricia Roggero. Journal of Computer Science and Technology, 17(02), e15. https://doi.org/10.24215/16666038.17.e15
Issue
Section
Original Articles
License
