The class of k Nearest Neighbor (k NN) queries in spatial networks has been studied in the literature. Existing approaches for k NN search in spatial networks assume that the weight of each edge in the spatial network is constant. However, real-world edge-weights are time-dependent and vary significantly in short durations, hence invalidating the existing solutions. The problem of k NN search in time-dependent spatial networks, where the weight of each edge is a function of time, is addressed herein. Two indexing schemes (Tight Network Index and Loose Network Index) are proposed to minimize the number of candidate nearest neighbor objects and reduce the invocation of the expensive fastest-path computation in time-dependent spatial networks. We demonstrate the efficiency of our proposed solution via experimental evaluations with real-world data-sets, including a variety of large spatial networks with real traffic-data.
Efficient K-nearest neighbor search in time-dependent spatial networks
23.06.2015
Patent
Elektronische Ressource
Englisch
Efficient Nearest Neighbor Search on Metric Time Series
Deutsches Zentrum für Luft- und Raumfahrt (DLR) | 2022
|Nearest neighbor search for relevance feedback
IEEE | 2003
|Nearest Neighbor Search for Relevance Feedback
British Library Conference Proceedings | 2003
|Fast nearest-neighbor search algorithm [2669-11]
British Library Conference Proceedings | 1996
|Kernelized pyramid nearest-neighbor search for object categorization
British Library Online Contents | 2014
|