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

摘要

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.

主权项

1. A computer-readable, non-transitory medium encoding a computer program product operable to cause data processing apparatus of a location-based, geographical points of interest searching system, to perform operations comprising:
partitioning a time-dependent spatial network into cells around the points of interest, the points of interest being associated with locations in the time-dependent spatial network, and the cells comprising a tight cell and a loose cell for each of the points of interest; and finding, in response to a query submitted to the searching system, the query having an associated location in the time-dependent spatial network, a specified number of the points of interest that are nearest to the location, using the tight cells and the loose cells.