Generating a query index and querying on the basis of the query index

• US 9,816,834 B2
• Filed: 07/24/2015
• Issued: 11/14/2017
• Est. Priority Date: 07/31/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Ning, Gao, Peng, Wang, Baohua, Wang, Feng Juan, Zhang, Xin
• Primary Examiner(s): Ingram, Thomas
• Application Number:
  US14/807,923
• Publication Number:
  US 20160033298A1
• Time in Patent Office: 844 Days
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0125 Traffic data processing
• CPC Class Codes: G08G 1/0133 for classifying traffic situation

Abstract

A road segment set influenced by an event on the basis of a connected network is identified. The connected network is built on the basis of reachability of a road segment in the road network. Furthermore, each road segment in the road segment set is reachable via the road network from the location of the event, or, in the alternative, the location of the event is reachable via the road network from each road segment in the road segment set. A query index is generated on the basis of the event and the road segment set.

Claims

1. A method for using a connected network built on the basis of reachability of a plurality of road segments in a road network, the method comprising:

identifying an event in the connected network;

forming a road segment set influenced by the event on the basis of the connected network by identifying each road segment in the plurality of road segments from which a location of the event is reachable via the road network from that road segment and which is within a predefined influence range from the location of the event;

generating a query index on the basis of the event and the road segment set;

forming a geo-fence around a perimeter of the predefined influence range such that a notification of the event is transmittable to a plurality of vehicles located within the geo-fence;

detecting, based on GPS data about the plurality of vehicles, a location of each vehicle of the plurality of vehicles within the geo-fence;

determining, based on the query index and the location of each vehicle of the plurality of vehicles, that each vehicle of a first vehicle set of the plurality of vehicles is on a road segment in the road segment set and that each vehicle of a second vehicle set of the plurality of vehicles is not on a road segment in the road segment set; and

notifying, based on the determining, each vehicle of the first vehicle set of the event without notifying the vehicles of the second vehicle set of the event.

2. The method of claim 1, wherein connection relationships of the connected network are set on the basis of topology of the road network, and reachability in the connected network is set on the basis of traffic information about the road network.

3. The method of claim 2, wherein reachability of a road segment in the connected network is represented by:

determining, on the basis of an allowed travel direction of the road segment, a direction of an edge in the connected network to represent the reachability of the road segment.

4. The method of claim 1, wherein the predefined influence range is determined on the basis of at least one item selected from a group consisting of:

a physical distance from the location of the event to the road segment;

a travel distance from the location of the event to the road segment along road segments in the road network;

a type of the event; and

a severity of the event.

5. The method of claim 1, further comprising:

determining, based on the query index and the location of each vehicle of the plurality of vehicles, that a first vehicle of the first vehicle set is on a first road segment that is in a second road segment set influenced by a second event,

wherein the notifying each vehicle of the first vehicle set of the event comprises;

determining a detour indicator for each of the event and the second event, each detour indicator describing a ratio of a linear distance to a travel distance from a location of the corresponding event to a location of the first vehicle;

sorting the event and the second event on the basis of the detour indicators; and

notifying the first vehicle of the sorted event and second event.

6. An apparatus for using a connected network built on the basis of reachability of a plurality of road segments in a road network, the apparatus comprising:

a memory; and

a processor in communication with the memory, the processor configured to obtain instructions from the memory that cause the processor to perform a method comprising;

identifying an event in the connected network;

forming a road segment set influenced by the event on the basis of the connected network by identifying each road segment in the plurality of road segments from which a location of the event is reachable via the road network from that road segment and which is within a predefined influence range from the location of the event;

generating a query index on the basis of the event and the road segment set;

forming a geo-fence around a perimeter of the predefined influence range such that a notification of the event is transmittable to a plurality of vehicles located within the geo-fence;

detecting, based on GPS data about the plurality of vehicles, a location of each vehicle of the plurality of vehicles within the geo-fence;

determining, based on the query index and the location of each vehicle of the plurality of vehicles, that each vehicle of a first vehicle set of the plurality of vehicles is on a road segment in the road segment set and that each vehicle of a second vehicle set of the plurality of vehicles is not on a road segment in the road segment set; and

notifying, based on the determining, each vehicle of the first vehicle set of the event without notifying the vehicles of the second vehicle set of the event.

7. The apparatus of claim 6, wherein connection relationships of the connected network are set on the basis of topology of the road network, and reachability in the connected network is set on the basis of traffic information about the road network.

8. The apparatus of claim 7, wherein reachability of a road segment in the connected network is represented by:

determining, on the basis of an allowed travel direction of the road segment, a direction of an edge in the connected network to represent the reachability of the road segment.

9. The apparatus of claim 6, wherein the apparatus further comprises:

a range determining module configured to determine the predefined influence range on the basis of at least one item selected from a group consisting of;

a physical distance from the location of the event to the road segment;

a travel distance from the location of the event to the road segment along road segments in the road network;

a type of the event; and

a severity of the event.

10. The apparatus of claim 6, wherein the method further comprises:

determining, based on the query index and the location of each vehicle of the plurality of vehicles, that a first vehicle of the first vehicle set is on a first road segment that is in a second road segment set influenced by a second event,

wherein the notifying each vehicle of the first vehicle set of the event comprises;

determining a detour indicator for each of the event and the second event, each detour indicator describing a ratio of a linear distance to a travel distance from a location of the corresponding event to a location of the first vehicle;

sorting the event and the second event on the basis of the detour indicators; and

notifying the first vehicle of the sorted event and second event.

11. A method for generating a query index with respect to an event in a road network, comprising:

identifying a road segment set influenced by the event on the basis of a connected network, wherein the connected network is built on the basis of reachability of a road segment in the road network, and a location of the event is reachable via the road network from each road segment in the road segment set;

generating the query index on the basis of the event and the road segment set;

identifying, based on GPS data, a vehicle location;

identifying, based on vehicle travel direction and the vehicle location, a front node for a vehicle travelling on a road segment;

searching, using the identified front node, within the query index;

determining, based on the searching, that at least one road segment directly connected to the front node is a road segment of the road segment set; and

notifying, in response to the determination that at least one road segment directly connected to the front node is a road segment of the road segment set, the vehicle of the event.