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

• US 9,062,985 B2
• Filed: 10/21/2013
• Issued: 06/23/2015
• Est. Priority Date: 05/03/2011
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Demiryurek, Ugur, Shahabi, Cyrus, Banaei-Kashani, Farnoush
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): Trivedi, Atul
• Application Number:
  US14/059,212
• Publication Number:
  US 20140046593A1
• Time in Patent Office: 610 Days
• Field of Search: 701532-533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once

Abstract

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.

Claims

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.

2. The computer-readable, non-transitory medium of claim 1, wherein the time-dependent spatial network indicates time-dependent travel times corresponding to a road network serviced by the searching system, wherein the tight cell for a given point of interest is a first sub-network around the given point of interest where any location in the first sub-network is guaranteed to have the given point of interest as its nearest neighbor, and wherein the loose cell for the given point of interest is a second sub-network around the given point of interest where any location outside the second sub-network is guaranteed to not have the given point of interest as its nearest neighbor.

3. The computer-readable, non-transitory medium of claim 1, wherein partitioning the time-dependent spatial network comprises, for each one of the points of interest:

determining the tight cell for the one point of interest by expanding a first sub-network, within the time-dependent spatial network, starting from the one point of interest and using maximum travel-time between nodes, and limiting the expansion of the first sub-network by expanding other sub-networks, within the time-dependent spatial network, starting from other points of interest and using minimum travel-time between nodes; and

determining the loose cell for the one point of interest by expanding a second sub-network, within the time-dependent spatial network, starting from the one point of interest and using minimum travel-time between nodes, and limiting the expansion of the second sub-network by expanding other sub-networks, within the time-dependent spatial network, starting from the other points of interest and using maximum travel-time between nodes.

4. The computer-readable, non-transitory medium of claim 1, wherein the points of interest are of a first type, the time-dependent spatial network includes points of interest of a second type, which is different than the first type, the query has an associated type of point of interest sought, and finding the specified number of the points of interest comprises finding only points of interest that are of the type associated with the query.

5. The computer-readable, non-transitory medium of claim 1, wherein the finding comprises:

checking the tight cells for one tight cell having the location inside it; and

if the one tight cell having the location inside it is found, identifying one point of interest corresponding to the one tight cell as the nearest neighbor,

else, identifying the nearest neighbor using the loose cells for the points of interest.

6. The computer-readable, non-transitory medium of claim 5, wherein the specified number is greater than one, the operations comprising:

determining a subset of the loose cells that are direct neighbors of a loose cell corresponding to a last nearest neighbor identified; and

identifying a next nearest neighbor using the subset of the loose cells by performing time-dependent fastest path computations that are bounded in accordance with the subset of the loose cells.

7. The computer-readable, non-transitory medium of claim 6, wherein identifying the nearest neighbor using the loose cells comprises searching a spatial index structure generated on the loose cells to identify candidates, and performing time-dependent fastest path computations for the candidates;

wherein determining the subset of the loose cells comprises accessing first information stored in the spatial index structure at an entry corresponding to the last nearest neighbor identified, the first information indicating the direct neighbors; and

wherein identifying the next nearest neighbor comprises using second information stored in the spatial index structure at entries corresponding to the loose cells of the subset, the second information indicating network nodes inside the loose cells of the subset by which the time-dependent fastest path computations are bounded.

8. The computer-readable, non-transitory medium of claim 1, wherein the searching system provides online map services.

9. A system comprising:

a user interface device; and

one or more computers operable to interact with the user interface device, the one or more computers comprising at least one processor and at least one memory device, and the one or more computers configured and arranged to perform operations comprising partitioning a network of nodes and edges into sub-networks around data objects of interest within the network, wherein each of the edges has an associated time-dependent weight, and the partitioning comprises (i) expanding one of the sub-networks starting from a corresponding one of the data objects and using a lower-bound for edge weights between nodes, and (ii) limiting the expansion of the one sub-network by expanding other sub-networks starting from remaining ones of the data objects and using an upper-bound for edge weights between nodes; and

the operations comprising finding, in response to a query having an associated location in the network, a specified number of the data objects of interest that are nearest to the location, using the sub-networks around the data objects.

10. The system of claim 9, wherein the sub-networks around the data objects of interest are first sub-networks, the partitioning comprises partitioning the network into second sub-networks around the data objects of interest, including expanding one of the second sub-networks starting from a corresponding one of the data objects and using an upper-bound for edge weights between nodes, and limiting the expansion of the one second sub-network by expanding other sub-networks starting from remaining ones of the data objects and using a lower-bound for edge weights between nodes;

and wherein the finding comprises finding the specified number of the data objects of interest using the first sub-networks and the second sub-networks.

11. The system of claim 10, wherein the one or more computers comprise means for indexing the first sub-networks and the second sub-networks to localize search space and minimize shortest path computation between the data objects of interest in the network.

12. The system of claim 11, wherein the one or more computers comprise a server operable to interact with the user interface device through a data communication network, and the user interface device is operable to interact with the server as a client.

13. The system of claim 12, wherein the user interface device comprises a mobile phone.

14. The system of claim 11, wherein the one or more computers comprises one personal computer, and the personal computer comprises the user interface device.