Method and system for detecting duplicate travel path information

• US 9,400,959 B2
• Filed: 08/23/2012
• Issued: 07/26/2016
• Est. Priority Date: 08/31/2011
• Status: Active Grant

• Current Assignee: Concur Technologies Incorporated (SAP SE)
• Original Assignee: Concur Technologies Incorporated (SAP SE)
• Inventors: Ollenberger, Brian Jeffrey, Silveria, Lisa Anne, Denmark, Richard Thor
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Glasser, Dara J
• Application Number:
  US13/593,108
• Publication Number:
  US 20130054542A1
• Time in Patent Office: 1,433 Days
• Field of Search: 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Methods and systems for detecting a likelihood that a travel path is a correct travel path of a user using possible duplicate travel path information. A set of travel paths comprising at least two travel paths is obtained. Any paths that break up more than one reservation are removed. Each travel path is broken into at least one leg. Each leg in each travel path is compared to each leg in every other travel path to determine whether any travel paths are duplicates. A likelihood that each of the at least two travel paths is the correct travel path is determined using information about whether any of the at least two travel paths are duplicates.

Claims

1. A method for detecting a likelihood that a travel path is a correct travel path of a user using possible duplicate travel path information, comprising:

obtaining a set of travel paths comprising at least two travel paths from a travel path database in communication with at least one processor;

at the at least one processor, removing any paths that break up more than one reservation;

at the at least one processor, breaking each travel path into at least one leg, wherein the at least one leg comprises at least one segment, wherein the at least one segment comprises a single unit of travel with an origin and a destination;

at the at least one processor, comparing each leg in each travel path to each leg in every other travel path in the set of travel paths to determine whether any travel paths are duplicates by determining whether any segments in any legs are similar by determining whether any segments have the same origin and/or the same destination as other segments in other legs in the set of travel paths wherein the legs are defined as computerized sequences of segment origins and destinations, and at least one computerized subsequence is utilized to find common segment origins and destinations; and

at the at least one processor, determining a likelihood that each of the at least two travel paths is the correct travel path using information about whether any of the at least two travel paths are duplicates.

2. The method of claim 1, comprising, at the at least one processor, listing of any candidate travel paths that are possible duplicates, the listing further comprising:

constructing at least one similar leg graph where nodes of the leg graph represent origins and destinations of legs.

3. The method of claim 1, further comprising:

at the at least one processor, allowing the user to select the correct travel path from a list of candidate travel paths that are possible duplicates.

4. The method of claim 1, wherein possible duplicates are sorted according to which travel path information was imported into the system most recently.

5. The method of claim 3, further comprising:

at the at least one processor, resolving any duplicate similar travel paths.

6. The method of claim 1, wherein the at least two travel paths compare:

air travel, car travel, rail travel, or bus travel, or any combination thereof.

7. The method of claim 1, further comprising:

determining whether any legs are similar to any other legs by determining whether any segments in any legs contain at least one start point and/or at least one end point.

8. The method of claim 1, further comprising:

at the at least one processor, excluding any candidate travel path that incorporates more than zero but fewer than all possible segments from more than one reservation.

9. A system for detecting a likelihood that a travel path is a correct travel path of a user using possible duplicate travel path information, comprising:

at least one processor configured for;

obtaining a set of travel paths comprising at least two travel paths from a travel path database in communication with the at least one processor;

removing any paths that break up more than one reservation;

breaking each travel path into at least one leg, wherein the at least one leg comprises at least one segment, wherein the at least one segment comprises a single unit of travel with an origin and a destination;

comparing each leg in each travel path to each leg in every other travel path in the set of travel paths to determine whether any travel paths are duplicates by determining whether any segments in any legs are similar by determining whether any segments have the same origin and/or the same destination as other segments in other legs in the set of travel paths wherein the legs are defined as computerized sequences of segment origins and destinations, and at least one computerized subsequence is utilized to find common segment origins and destinations; and

determining a likelihood that each of the at least two travel paths is the correct travel path using information about whether any of the at least two travel paths are duplicates.

10. The system of claim 9, wherein the at least one processor is further configured for listing any candidate travel paths that are possible duplicates, the listing further comprising:

constructing at least one similar leg graph where nodes of the leg graph represent origins and destinations of legs.

11. The system of claim 9, wherein the at least one processor is further configured for:

allowing the user to select the correct travel path from a list of candidate travel paths that are possible duplicates.

12. The system of claim 9, wherein possible duplicates are sorted according to which travel path information was imported into the system most recently.

13. The method of claim 11, wherein the at least one processor is further configured for:

resolving any duplicate similar travel paths.

14. The system of claim 9, wherein the at least two travel paths compare:

air travel, car travel, rail travel, or bus travel, or any combination thereof.

15. The system of claim 9, wherein the at least one processor is further configured for:

determining whether any legs are similar to any other legs by determining whether any segments in any legs contain at least one start point and/or at least one end point.

16. The method of claim 9, wherein the at least one processor is further configured for:

excluding any candidate travel path that incorporates more than zero but fewer than all possible segments from more than one reservation.