Efficient Reuse of Metric Indexes for Multi-resolution Queries
Abstract
Performing similarity queries using resolutions different from those used for the data employed during the index construction is a challenge for traditional Metric Access Methods (MAMs). Varying data resolution occurs, for example, in scenarios involving reduced data fidelity, such as when reducing data resolution for efficient network transmission. This work proposes a novel way to extend a MAM, using the Slim-tree as a case study, to efficiently and adaptively support queries over transformed data using indices built using only the original, full-resolution data. The proposed approach modifies the pruning heuristic to incorporate safe upper bounds on distances in the transformed domain, guaranteeing correct query results while preserving much of the pruning power of the original MAM. Experimental results on image datasets demonstrate substantial performance improvements over sequential search, even under conditions of high compression.
Keywords:
Similarity Retrieval, Similarity Measurements, Metric Access Methods, Indexing, Data Representation, Haar Transform
References
Abdel-Hamid, L. (2024). Multiresolution analysis for covid-19 diagnosis from chest ct images: wavelet vs. contourlet transforms. Multimedia Tools and Applications, 83(1):2749–2771.
Berchtold, S., Keim, D. A., and Kriegel, H.-P. (1996). The x-tree: An index structure for high-dimensional data. In Very large data-bases, pages 28–39.
Cazzolato, M. T., Rodrigues, L. S., Ribeiro, M. X., Gutierrez, M. A., Traina Jr, C., and Traina, A. J. M. (2022). Sketch+ for visual and correlation-based exploratory data analysis: A case study with COVID-19 databases. JIDM – Journal of Information and Data Management, 13(2):308.
Cazzolato, M. T., Rodrigues, L. S., Scabora, L. d. C., Zabot, G. F., Vasconcelos, G. Q., Chino, D. Y. T., Jorge, A. E. S., Cordeiro, R. L. F., Traina Jr, C., and Traina, A. J. M. (2019). A DBMS-based framework for content-based retrieval and analysis of skin ulcer images in medical practice. In Proceedings of SBBD 2019, pages 109–120, Fortaleza, CE, Brazil. SBC.
Chen, L., Gao, Y., Song, X., Li, Z., Zhu, Y., Miao, X., and Jensen, C. S. (2023). Indexing metric spaces for exact similarity search. ACM Comput. Surv., 55(6):39.
Daubechies, I. (1990). The wavelet transform, time-frequency localization and signal analysis. IEEE Transactions on Information Theory, 36(5):961–1005.
Deza, M. M. and Deza, E. (2016). Encyclopedia of Distances. Springer, Heidelberg, 4th edition.
Elharrouss, O., Akbari, Y., Almadeed, N., and Al-Maadeed, S. (2024). Backbones-review: Feature extractor networks for deep learning and deep reinforcement learning approaches in computer vision. Computer Science Review, 53:22.
Eliasof, M., Bodner, B. J., and Treister, E. (2024). Haar wavelet feature compression for quantized graph convolutional networks. IEEE Transactions on Neural Networks and Learning Systems, 35(4):4542–4553.
Gupta, S., Thakar, U., and Tokekar, S. (2025). A comprehensive survey on techniques for numerical similarity measurement. Expert Systems with Applications, 277:127235.
Guttman, A. (1984). R-tree : A dynamic index structure for spatial searching. In ACM SIGMOD International Conference on Management of Data, pages 47–57, Boston, MA. ACM PRess.
Khosla, A., Jayadevaprakash, N., Yao, B., and Fei-Fei, L. (2011). Novel dataset for fine-grained image categorization. In IEEE Conference on Computer Vision and Pattern Recognition First Workshop on Fine-Grained Visual Categorization, Colorado Springs, CO.
Marques, P. M. d. A. and Rangayyan, R. M. (2013). Content-based Retrieval of Medical Images: Landmarking, Indexing, and Relevance Feedback. Synthesis Lectures on Biomedical Engineering. Morgan & Claypool Publishers, San Rafael, California, USA.
Mulcahy, C. (1997). Image compression using the haar wavelet transform. Spelman Science and Mathematics Journal, 1(1):22–31.
Santana, D. R. and Ribeiro, L. A. (2023). Approximate similarity joins over dense vector embeddings. In Proceedings of SBBD 2023, pages 51–62. SBC.
Saouabe, A., Tkatek, S., Oualla, H., and Mourtaji, I. (2024). Image indexing approaches for enhanced content-based image retrieval: An overview.
Sharma, S., Gupta, V., and Juneja, M. (2019). A survey of image data indexing techniques. Artificial Intelligence Review, 52(2):1189–1266.
Traina Jr, C., Traina, A., Seeger, B., and Faloutsos, C. (2000). Slim-trees: High performance metric trees minimizing overlap between nodes. In International Conference on Extending Database Technology, pages 51–65. Springer.
Vadivel, A., Majumdar, A., and Sural, S. (2003). Performance comparison of distance metrics in content-based image retrieval applications. In International Conference on Information Technology (CIT), Bhubaneswar, India, pages 159–164.
Yianilos, P. N. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. In Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pages 311–321, Austin, TX.
Zaki, M. J. and Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms [link]. Cambridge University Press, 2nd edition.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2006). Similarity Search: The Metric Space Approach. Advances in Database Systems. Springer New York, New York, NY, USA.
Berchtold, S., Keim, D. A., and Kriegel, H.-P. (1996). The x-tree: An index structure for high-dimensional data. In Very large data-bases, pages 28–39.
Cazzolato, M. T., Rodrigues, L. S., Ribeiro, M. X., Gutierrez, M. A., Traina Jr, C., and Traina, A. J. M. (2022). Sketch+ for visual and correlation-based exploratory data analysis: A case study with COVID-19 databases. JIDM – Journal of Information and Data Management, 13(2):308.
Cazzolato, M. T., Rodrigues, L. S., Scabora, L. d. C., Zabot, G. F., Vasconcelos, G. Q., Chino, D. Y. T., Jorge, A. E. S., Cordeiro, R. L. F., Traina Jr, C., and Traina, A. J. M. (2019). A DBMS-based framework for content-based retrieval and analysis of skin ulcer images in medical practice. In Proceedings of SBBD 2019, pages 109–120, Fortaleza, CE, Brazil. SBC.
Chen, L., Gao, Y., Song, X., Li, Z., Zhu, Y., Miao, X., and Jensen, C. S. (2023). Indexing metric spaces for exact similarity search. ACM Comput. Surv., 55(6):39.
Daubechies, I. (1990). The wavelet transform, time-frequency localization and signal analysis. IEEE Transactions on Information Theory, 36(5):961–1005.
Deza, M. M. and Deza, E. (2016). Encyclopedia of Distances. Springer, Heidelberg, 4th edition.
Elharrouss, O., Akbari, Y., Almadeed, N., and Al-Maadeed, S. (2024). Backbones-review: Feature extractor networks for deep learning and deep reinforcement learning approaches in computer vision. Computer Science Review, 53:22.
Eliasof, M., Bodner, B. J., and Treister, E. (2024). Haar wavelet feature compression for quantized graph convolutional networks. IEEE Transactions on Neural Networks and Learning Systems, 35(4):4542–4553.
Gupta, S., Thakar, U., and Tokekar, S. (2025). A comprehensive survey on techniques for numerical similarity measurement. Expert Systems with Applications, 277:127235.
Guttman, A. (1984). R-tree : A dynamic index structure for spatial searching. In ACM SIGMOD International Conference on Management of Data, pages 47–57, Boston, MA. ACM PRess.
Khosla, A., Jayadevaprakash, N., Yao, B., and Fei-Fei, L. (2011). Novel dataset for fine-grained image categorization. In IEEE Conference on Computer Vision and Pattern Recognition First Workshop on Fine-Grained Visual Categorization, Colorado Springs, CO.
Marques, P. M. d. A. and Rangayyan, R. M. (2013). Content-based Retrieval of Medical Images: Landmarking, Indexing, and Relevance Feedback. Synthesis Lectures on Biomedical Engineering. Morgan & Claypool Publishers, San Rafael, California, USA.
Mulcahy, C. (1997). Image compression using the haar wavelet transform. Spelman Science and Mathematics Journal, 1(1):22–31.
Santana, D. R. and Ribeiro, L. A. (2023). Approximate similarity joins over dense vector embeddings. In Proceedings of SBBD 2023, pages 51–62. SBC.
Saouabe, A., Tkatek, S., Oualla, H., and Mourtaji, I. (2024). Image indexing approaches for enhanced content-based image retrieval: An overview.
Sharma, S., Gupta, V., and Juneja, M. (2019). A survey of image data indexing techniques. Artificial Intelligence Review, 52(2):1189–1266.
Traina Jr, C., Traina, A., Seeger, B., and Faloutsos, C. (2000). Slim-trees: High performance metric trees minimizing overlap between nodes. In International Conference on Extending Database Technology, pages 51–65. Springer.
Vadivel, A., Majumdar, A., and Sural, S. (2003). Performance comparison of distance metrics in content-based image retrieval applications. In International Conference on Information Technology (CIT), Bhubaneswar, India, pages 159–164.
Yianilos, P. N. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. In Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pages 311–321, Austin, TX.
Zaki, M. J. and Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms [link]. Cambridge University Press, 2nd edition.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2006). Similarity Search: The Metric Space Approach. Advances in Database Systems. Springer New York, New York, NY, USA.
Published
2025-09-29
How to Cite
ARBOLEDA, Rodrigo César; TRAINA, Agma Juci Machado; TRAINA JR., Caetano.
Efficient Reuse of Metric Indexes for Multi-resolution Queries. In: BRAZILIAN SYMPOSIUM ON DATABASES (SBBD), 40. , 2025, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 236-249.
ISSN 2763-8979.
DOI: https://doi.org/10.5753/sbbd.2025.247069.
