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.


    Access

    Download


    Export, share and cite



    Title :

    Efficient K-nearest neighbor search in time-dependent spatial networks


    Contributors:

    Publication date :

    2015-06-23


    Type of media :

    Patent


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    IPC:    G01C Messen von Entfernungen, Höhen, Neigungen oder Richtungen , MEASURING DISTANCES, LEVELS OR BEARINGS / G08G Anlagen zur Steuerung, Regelung oder Überwachung des Verkehrs , TRAFFIC CONTROL SYSTEMS



    Efficient Nearest Neighbor Search on Metric Time Series

    Schäfer, Jörg Peter | German Aerospace Center (DLR) | 2022

    Free access

    Nearest neighbor search for relevance feedback

    Tesic, J. / Manjunath, B.S. | IEEE | 2003


    Nearest Neighbor Search for Relevance Feedback

    Tesic, J. / Manjunath, B. / IEEE | British Library Conference Proceedings | 2003


    Fast nearest-neighbor search algorithm [2669-11]

    Darwish, A. M. / SPIE | British Library Conference Proceedings | 1996


    Kernelized pyramid nearest-neighbor search for object categorization

    Cheng, H. | British Library Online Contents | 2014