MAT-Index: an index for fast multiple aspect trajectory similarity measuring

Abstract

O enriquecimento semântico dos dados de mobilidade com diversas fontes de informação levou a um novo tipo de dado móvel, conhecido como trajetória de múltiplos aspectos. Comparar trajetórias é crucial para diversas tarefas de análise como consultas, clusterização, similaridade, classificação etc. Medir a similaridade de trajetórias de múltiplos aspectos é uma tarefa complexa e computacionalmente custosa, pois o grande número de aspectos e a heterogeneidade das dimensões espaço, tempo, e semânticas requerem diferentes tratamentos. Apenas alguns trabalhos na literatura focam na otimização de todas essas dimensões em uma solução, e, ao melhor do nosso conhecimento, nenhum propõe uma comparação ponto-a-ponto otimizada. Nesta pesquisa, é proposto o Multiple Aspect Trajectory Index (MAT-Index), uma estrutura de dados indexada para otimização de comparações ponto-a-ponto de trajetórias de múltiplos aspectos, considerando suas três dimensões básicas de espaço, tempo e semânticas em uma estrutura integrada. Avaliações quantitativas mostraram a redução do tempo de execução em até 98.1%.

Abstract: The semantic enrichment of mobility data with several information sources has led to a new type of movement data, the so-called multiple aspect trajectories. Comparing multiple aspect trajectories is crucial for several analysis tasks like querying, clustering, similarity, classification, etc. Multiple aspect trajectory similarity measuring is more complex and computationally expensive, because of the large number and heterogeneous aspects of space, time, and semantics that require a different treatment. Only a few works in the literature focus on optimizing all these dimensions in a single solution, and, to the best of our knowledge, none of them propose a fast point-to-point comparison. In this research, we propose the Multiple Aspect Trajectory Index (MAT-Index), an index data structure for optimizing the point-to-point comparison of multiple aspect trajectories, considering its three basic dimensions of space, time, and semantics in an integrated data structure. Quantitative evaluations show a processing time reduction of up to 98.1%.