Systems and Methods for Summarizing a Guidebook Result

• US 20150170229A1
• Filed: 05/14/2013
• Published: 06/18/2015
• Est. Priority Date: 05/14/2013
• Status: Abandoned Application

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Graells, Albert, Flier, Holger-Frederik Robert
• Application Number:
  US13/894,040
• Publication Number:
  US 20150170229A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

Systems and methods for summarizing a guidebook result are provided. An exemplary system includes a transit trip identification module, a cost function generation module, a service window identification module, a daytime interval conversion module, and a guidebook summarization module. An exemplary method includes identifying a plurality of service windows comprising intervals of time over which the available transit trips satisfy a quality criterion. The exemplary method also includes selecting as a guidebook summary a set of days of the week and a continuous interval of time which include only portions of service windows, such that a total number of hours included in the guidebook summary is maximized

Claims

1. A computer-implemented method for summarizing available transit trips, the method comprising:

generating, based on a plurality of transit trips from an origin to a destination, a cost function specifying a trip cost as a function of time over a time period;

identifying a plurality of service windows comprising intervals of time over which the trip cost specified by the cost function satisfies a quality criterion;

translating the plurality of service windows into a plurality of daytime intervals, each daytime interval being associated with a day of the week and having a duration of twenty-four hours or less; and

identifying a guidebook summary that includes only portions of daytime intervals and maximizes a total number of hours included in such guidebook summary, the guidebook summary describing an interval of time and a set of days of the week.

2. The computer-implemented method of claim 1, further comprising providing the guidebook summary as a text string.

3. The computer-implemented method of claim 1, wherein the cost function is a piecewise linear function comprising a plurality of linear trip segments, each linear trip segment modeling the trip cost, including waiting time, of one of the plurality of transit trips as a function of time.

4. The computer-implemented method of claim 1, wherein:

generating a cost function specifying a trip cost as a function of time comprises generating a cost function specifying, for each point in time over the time period, an expected time until arrival at the destination based on available departures from the origin; and

identifying a plurality of service windows comprising intervals of time over which the trip cost specified by the cost function satisfies a quality criterion comprises identifying a plurality of service windows comprising time intervals over which the expected time specified by the cost function is less than or equal to a threshold value.

5. The computer-implemented method of claim 1, wherein identifying a plurality of service windows comprising time intervals over which the trip cost specified by the cost function satisfies a quality criterion comprises:

identifying a plurality of local maximums exhibited by the cost function over the time period; and

identifying a plurality of service windows comprising time intervals over which the trip cost specified by the cost function is less than a median value of the plurality of local maximums.

6. The computer-implemented method of claim 1, wherein identifying a plurality of service windows comprising time intervals over which the trip cost specified by the cost function satisfies a quality criterion comprises:

determining a global minimum value expressed by the cost function; and

identifying a plurality of service windows comprising time intervals over which the trip cost specified by the cost function is less than or equal to a threshold value, the threshold value having been determined based on the global minimum value.

7. The computer-implemented method of claim 1, wherein each of the plurality of service windows is constrained to begin at a local minimum of the cost function.

8. The computer-implemented method of claim 1, wherein translating the plurality of service windows into a plurality of daytime intervals comprises, for each of the plurality of service windows:

determining whether the service window is greater than twenty-four hours in length;

parsing the service window into two or more service windows when the service window is greater than twenty-four hours in length; and

associating the service window with the day of the week upon which such service window begins.

9. The computer-implemented method of claim 1, wherein identifying the guidebook summary comprises:

computing, for each instance in which portions of two or more of the plurality of daytime intervals share overlapping times independent of their associated days of the week, a total number of hours included in such portions; and

selecting the overlapping portions of the plurality of daytime intervals that include the largest total number of hours as the guidebook summary.

10. The computer-implemented method of claim 1, wherein identifying the guidebook summary comprises:

traversing a graph describing the plurality of daytime intervals, the graph having each day of the week as a unit on a y-axis and units of time on an x-axis;

computing, for each of a plurality of x-axis intervals in which portions of two or more daytime intervals continuously overlap with respect to the x-axis, a total area covered by such portions over such x-axis interval; and

selecting as the guidebook summary the x-axis interval associated with the largest total area and the days of the week associated with the portions of the two or more daytime intervals that continuously overlap over the x-axis interval associated with the largest total area.

11. A computer-program product comprising a non-transitory computer-readable storage medium storing computer-readable instructions for summarizing available transit trips from an origin to a destination, the instructions when executed by a processor, cause the processor to perform operations, the operations comprising:

identifying a plurality of service windows comprising intervals of time over which the available transit trips satisfy a quality criterion; and

selecting as a guidebook summary a set of days of the week and a continuous interval of time which include only portions of service windows, such that a total number of hours included in the guidebook summary is maximized.

12. The computer-program product of claim 11, wherein identifying a plurality of service windows comprising intervals of time over which the available transit trips satisfy a quality criterion comprises:

generating a cost function describing, based on the available transit trips from the origin to the destination, a total time to arrival at the destination for each point in time over a time period; and

identifying a plurality of service windows comprising maximal time intervals over which the total time to arrival described by the cost function remains at or below a threshold value.

13. The computer-program product of claim 11, storing further instructions for performing further operations comprising, prior to selecting the guidebook summary:

parsing any service window exceeding twenty-four hours in length into two or more service windows; and

associating each of the plurality of service windows with the day of the week in which such service window begins.

14. The computer-program product of claim 13, wherein selecting as a guidebook summary a set of days of the week and a continuous interval of time which include only portions of service windows, such that a total number of hours included in the guidebook summary is maximized comprises:

identifying a plurality of sets of overlapping portions of two or more service windows, each set of overlapping portions having an overlapping interval of time irrespective of the days of the week associated with the overlapping portions of such set;

computing, for each set of overlapping portions, a total number of hours included in such set by multiplying the overlapping interval of time associated with such set by the number of overlapping portions included in such set; and

selecting as the guidebook summary the set of overlapping portions that includes the largest total number of hours.

15. The computer-program product of claim 13, wherein selecting as a guidebook summary a set of days of the week and a continuous interval of time which include only portions of service windows, such that a total number of hours included in the guidebook summary is maximized comprises:

mapping the plurality of service windows on a graph having one unit on a first axis for each day of the week and units of time on a second axis;

computing, for each set of portions of two or more service windows that overlap with respect to the second axis, a total area covered by such set of portions; and

selecting as the guidebook summary the set of portions that covers the largest total area.

16. The computer-program product of claim 11, storing further instructions for performing further operations comprising, prior to selecting the guidebook summary, receiving a desired set of days of the week, wherein the set of days of the week selected as the guidebook summary is a subset of the desired set of days of the week.

17. A computing system for transit trip summarization, the computing system comprising a processor and a memory, the system comprising:

a cost function generation module implemented by the processor, the cost function generation module configured to generate a cost function specifying a trip cost as a function of time over a time period based on a plurality of transit trips from an origin to a destination;

a service window identification module implemented by the processor, the service window identification module configured to identify a plurality of service windows comprising intervals of time over which the trip cost specified by the cost function satisfies a quality criterion;

a daytime interval conversion module implemented by the processor, the daytime interval module configured to convert the plurality of service windows into a plurality of daytime intervals, each of the plurality of daytime intervals being associated with the day of the week on which such daytime interval begins and having a duration twenty-four hours or less in length; and

a guidebook summarization module implemented by the processor, the guidebook summarization module configured to select as a guidebook summary a set of days of the week and a continuous interval of time, the guidebook summary including only portions of daytime intervals and maximizing a probability that the guidebook summary includes a randomly selected time on a randomly selected day of the week.

18. The computing system of claim 17, wherein:

the cost function comprises a piecewise linear function comprising a plurality of linear trip segments, each linear trip segment modeling the cost, including waiting time, of one of the plurality of transit trips as a function of time; and

the quality criterion comprises a threshold cost such that the trip cost specified by the cost function satisfies the quality criterion when it is less than or equal to the threshold cost.

19. The computing system of claim 17, wherein the daytime interval conversion module is configured to convert the plurality of service windows into a plurality of daytime intervals by performing operations comprising:

parsing any service window exceeding twenty-four hours in length into two or more service windows; and

associating each of the plurality of service windows with the day of the week in which such service window begins, such that the plurality of daytime intervals are formed.

20. The computing system of claim 17, wherein the guidebook summarization module is configured to select as a guidebook summary a set of days of the week and a continuous interval of time by performing operations comprising:

traversing the plurality of daytime intervals in a scanline ordering according to the time at which each of the plurality daytime intervals begins;

computing, for each overlapping subset of daytime intervals, a total time encompassed by such overlapping subset of daytime intervals; and

selecting as the guidebook summary the subset of daytime intervals that encompasses the largest total time.