Produção Nacional
k-Nearest Neighbors Queries in Time-Dependent Road Networks
2012; Volume: 3; Issue: 3 Linguagem: Inglês
ISSN
2178-7107
AutoresLívia Almada Cruz, Mário A. Nascimento, José Antônio Fernandes de Macêdo,
Tópico(s)Automated Road and Building Extraction
ResumoIn this article, we study the problem of processing k-nearest neighbors (kNN) queries in road networks considering traffic conditions, in particular the case where the speed of moving objects is time-dependent. For instance, given that the user is at a given location at certain time, the query returns the k points of interest (e.g., gas stations) that can be reached in the minimum amount of time. Previous works have proposed solutions to answer kNN queries in road networks where the moving speed in each road is constant. Obviously, these solutions cannot be simply applied to the problem we are interested in. Our approach uses the well-known A∗ search algorithm by applying incremental network expansion and pruning unpromising vertices. We discuss the design and correctness of our algorithm and present experimental results that show the efficiency and effectiveness of our solution.
Referência(s)