Estendendo Consultas Contínuas por Abrangência aos Dados Métricos

• Enzo Seraphim Universidade Federal de Itajubá
• Thatyana F. P. Seraphim Universidade Federal de Itajubá https://orcid.org/0009-0008-1735-2447
• Lucio F. D. Santos Instituto Federal do Norte de Minas Gerais
• Edmilson Marmo Moreira Universidade Federal de Itajubá https://orcid.org/0000-0001-5059-9080
• Luiz Olmes Carvalho Universidade Federal de Itajubá

DOI: https://doi.org/10.5753/sbbd.2025.247823

Resumo

Diversos estudos mostram a importância e a complexidade para determinar os pontos mais próximos de uma trajetória, através de uma técnica conhecida como Consulta Contínua. As soluções existentes para responder essas consultas utilizam das coordenadas euclidianas em dados espaciais para verificar se o objeto de interesse está dentro da cobertura da rota. No entanto, essa abordagem não se aplica a dados puramente métricos, pois não se pode representá-los em um espaço n-dimensional. Por outro lado, uma função de distância pode inferir segmentos de retas sobre o espaço métrico, semelhante à associação de uma geometria. Neste contexto, o presente trabalho associa propriedades Euclidianas ao espaço métrico para definir a qualificação entre ponto e retas, de modo a expandir consultas contínuas por abrangência a este domínio de dados. Os experimentos evidenciam que esta associação permite consultas contínuas por abrangência eficientes em dados puramente métricos, suprimindo a lacuna das técnicas existentes na literatura.

Palavras-chave: Consulta Contínuas, Trajetória por Abrangência, Dados Métricos

Referências

Afonso, F., Barbosa, F., and Rodrigues, A. (2011). Trajectory data similarity with metric data structures. In Geographical Inf. Science Research United Kingdom, 9p.

Ciaccia, P., Patella, M., and Zezula, P. (1997). M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In Proc. Int. Conf. VLDB, pages 426–435, Morgan Kaufmann, San Francisco, CA, USA.

Chen, L., Özsu, M. T., and Oria, V. (2005). Robust and fast similarity search for moving object trajectories. In Proc. ACM SIGMOD, pages 491–502, New York, NY, USA.

Chen, Z., Shen, H. T., Zhou, X., and Yu, J. X. (2009). Monitoring path nearest neighbor in road networks. In Proc. ACM SIGMOD, pages 591–602, New York, NY, USA.

CodePoint, Open CSV. (2025). [link]

Deng, K., Xie, K., Zheng, K., and Zhou, X. (2011). Trajectory Indexing and Retrieval, pages 35–60. Springer, New York, NY.

Guttman. A. (1984). R-trees: a dynamic index structure for spatial searching. SIGMOD Rec., 14 (2).

Güting, R. H., Das, S. K., Valdés, F., and Ray, S. (2025). Exact trajectory similarity search with n-tree: An efficient metric index for knn and range queries. ACM Trans. Spatial Algorithms Syst., 11(1).

Kalashnikov, D., Prabhakar, S., Hambrusch, S., and Aref, W. (2002). Efficient evaluation of continuous range queries on moving objects. In Proc. DEXA, Berlin, Springer.

LibreOffice. (2025). [link]

Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. (2003). Query processing in spatial network databases. In VLDB Conf., pages 802–813. Morgan Kaufmann, San Francisco.

Shang, S., Deng, K., and Xie, K. (2010). Best point detour query in road networks. In Proc. 18th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, pages 71–80, New York, NY, USA.

Tao, Y., Papadias, D., and Shen, Q. (2002). Continuous nearest neighbor search. In Proc. 28th Int. Conf. on VLDB, pages 287–298. Morgan Kaufmann, San Francisco.

Traina Jr., C., Traina, A. J. M., Faloutsos, C., and Seeger, B. (2002). Fast Indexing and Visualization of Metric Data Sets using Slim-Trees. IEEE TKDE. 14(2).

UniProtKB, TrEMBL Fasta. (2025). [link]

Wang, S., Bao, Z., Culpepper, J. S., and Cong, G. (2021). A survey on trajectory data management, analytics, and learning. ACM Comput. Surv., 54(2).

Xu, W., and Miranker, D. P. (2004). A metric model of amino acid substitution. Bioinformatics. UK, 20(8).

Xuan, K., Zhao, G., Taniar, D., and Srinivasan, B. (2008). Continuous range search query processing in mobile navigation. In Int. Conf. on Parallel and Dist. Syst, pages 361–368.

Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2010). Similarity Search: The Metric Space Approach. Springer Publishing Company, Incorporated, 1st edition.