文章基本信息

标题：kNN Search Algorithm with Index of the Minimum Road Travel Time in Time-Dependent Road Networks
本地全文：下载
作者：Yuka KOMAI ; Duong Hong NGUYEN ; Takahiro HARA 等
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2015
卷号：10
期号：2
页码：323-329
DOI：10.11185/imt.10.323
出版社：Information and Media Technologies Editorial Board
摘要：Recently, there has been an increasing interest in search in time-dependent road networks where the travel time on roads depends on the time. In such a time-dependent network, the result of k Nearest Neighbor ( k NN) queries, which search the k nearest neighbors ( k NNs) from the specified location, depends on the query-issuing time. Therefore, existing approaches in static networks are not directly applied for k NN query in time-dependent road networks. In this paper, we propose a k NN search method to achieve a small number of visited vertexes and small response time in time-dependent road networks. In our proposed method, an index structure is constructed based on the minimum travel time on roads in the preprocessing phase. In query processing, a network is expanded by A^* algorithm with referring the minimum travel time in the index until k NNs are found. An experimental result shows that our proposed method reduces the number of visited vertexes and the response time compared with an existing method.