GENERATING A QUERY INDEX AND QUERYING ON THE BASIS OF THE QUERY INDEX

• US 20160033298A1
• Filed: 07/24/2015
• Published: 02/04/2016
• 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
• Granted Patent: US 9,816,834 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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 each road segment in the road segment set is reachable via the road network from a location of the event; and

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

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 each road segment is within a predefined influence range around the location of the event, and 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, wherein the identifying the road segment set influenced by the event on the basis of the connected network comprises:

identifying each reachable road segment within a predefined influence range to form, from an edge representing a road segment to which the location of the event belongs, the road segment set.

6. The method of claim 5, further comprising:

in response to a second predefined influence range around a location of a second event in the road network overlapping the predefined influence range, identifying within an overlap range a second road segment set influenced by the second event on the basis of the connected network, wherein each road segment in the second road segment set is reachable via the road network from the location of the second event; and

updating the query index on the basis of the second event and the second road segment set.

7. The method of claim 1, further comprising:

in response to determining that a road segment on which a vehicle is travelling is a road segment in the road segment set, notifying the vehicle of the event.

8. The method of claim 1, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining, on the basis of status information about the road network, a travel time for the vehicle to reach the location of the event; and

in response to the determination that the road segment on which the vehicle is travelling is a road segment in the road segment set and to the determined travel time being less than a predicted duration of the event, notifying the vehicle of the event.

9. The method of claim 1, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling;

sorting the plurality of events on the basis of at least one item selected from a group consisting of;

types of the plurality of events, distances from locations of the plurality of events to a location of the vehicle, and severities of the plurality of events; and

notifying the vehicle of the plurality of the sorted events.

10. The method of claim 1, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling;

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

sorting the plurality of events on the basis of the detour indicators; and

notifying the vehicle of the plurality of the sorted events.

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

an identifying module configured to identify 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 each road segment in the road segment set is reachable via the road network from a location of the event; and

a generating module configured to generate the query index on the basis of the event and the road segment set.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 12, 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.

14. The apparatus of claim 11, wherein the each road segment is within a predefined influence range around the location of the event, and 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.

15. The apparatus of claim 11, wherein the identifying module comprises:

a traversing module configured to identify each reachable road segment within the predefined influence range to form, from an edge representing a road segment to which the location of the event belongs, the road segment set.

16. The apparatus of claim 15, wherein the identifying module is further configured to, in response to a second predefined influence range around a location of a second event in the road network overlapping the predefined influence range, identify within an overlap range a second road segment set influenced by the second event on the basis of the connected network, wherein each road segment in the second road segment set is reachable via the road network from the location of the second event, and wherein the apparatus further comprises:

an updating module configured to update the query index on the basis of the second event and the second road segment set.

17. The apparatus of claim 11, further comprising:

a notifying module configured to, in response to determining that a road segment on which a vehicle is travelling is a road segment in the road segment set, notify the vehicle of the event.

18. The apparatus of claim 11, further comprising:

a notifying module configured to determine that a road segment on which a vehicle is travelling is a road segment in the road segment set; and

a determining module configured to determine, on the basis of status information about the road network, a travel time for the vehicle to reach the location of the event,

wherein the notifying module is further configured to, in response the determination that the road segment on which the vehicle is travelling is a road segment in the road segment set and to the determined travel time being less than a predicted duration of the event, notify the vehicle of the event.

19. The apparatus of claim 11, further comprising:

a notifying module configured to determine that a road segment on which a vehicle is travelling is a road segment in the road segment set;

a determining module configured to determine that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling; and

a sorting module configured to sort the plurality of events on the basis of at least one item selected from a group consisting of;

types of the plurality of events, distances from locations of the plurality of events to a location of the vehicle, and severities of the plurality of events,

wherein the notifying module is further configured to notify the vehicle of the plurality of the sorted events.

20. The apparatus of claim 11, further comprising:

a notifying module configured to determine that a road segment on which a vehicle is travelling is a road segment in the road segment set;

a determining module configured to determine that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling;

a calculating module configured to determine a detour indicator for each event of the plurality of events, each detour indicator describing a ratio of a linear distance to a travel distance from a location of the corresponding event of the plurality of events to a location of the vehicle; and

a sorting module configured to sort the plurality of events on the basis of the detour indicators, wherein

the notifying module is further configured to notify the vehicle of the plurality of the sorted events.

21. 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; and

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

22. The method of claim 21, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining, on the basis of status information about the road network, a travel time for the vehicle to reach the location of the event; and

in response to the determination that the road segment on which the vehicle is travelling is a road segment in the road segment set and to the determined travel time being less than a predicted duration of the event, notifying the vehicle of the event.

23. The method of claim 21, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling;

sorting the plurality of events on the basis of at least one item selected from a group consisting of;

types of the plurality of events, distances from locations of the plurality of events to a location of the vehicle, and severities of the plurality of events; and

notifying the vehicle of the plurality of the sorted events.

24. The method of claim 21, further comprising:

determining that a road segment on which a vehicle is travelling is a road segment in the road segment set;

determining that the query index contains a plurality of events associated with the road segment on which the vehicle is travelling;

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

sorting the plurality of events on the basis of the detour indicators; and

notifying the vehicle of the plurality of the sorted events.

25. The method of claim 21 further comprising:

identifying, based on vehicle travel direction and 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.