Patent Publication Number: US-2016239515-A1

Title: Method and system for detecting duplicate travel path information

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 13/593,108 filed Aug. 23, 2012, which claims the benefit of U.S. Provisional Application No. 61/529,680, filed Aug. 31, 2011, which are incorporated by reference in their entireities. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIGS. 1 and 7  illustrate a system for detecting duplicate travel path information, according to an embodiment of the invention. 
       FIGS. 2-3C and 8-10B  illustrate a method for detecting duplicate travel path information, according to an embodiment of the invention. 
       FIGS. 4-6  illustrate example embodiments of the invention. 
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION 
       FIG. 1  illustrates a system  100  for detecting duplicate travel path information, according to an embodiment. System  100  may include, but is not limited to: a client  102  communicating with a server  101  over a network  103  utilizing a duplicate path application  105 . The duplicate path application  105  may run utilizing server  101 . The network  103  may comprise an Internet and/or an intranet. The client  102  and server  101  may comprise a computer. The computer may be any programmable machine capable of performing arithmetic and/or logical operations. In some embodiments, computers may comprise processors, memories, data storage devices, and/or other commonly known or novel components. These components may be connected physically or through network or wireless links. Computers may be referred to with terms that are commonly used by those of ordinary skill in the relevant arts, such as servers, PCs, mobile devices, and other terms. It will be understood by those of ordinary skill that those terms used herein are interchangeable, and any computer capable of performing the described functions may be used. For example, though the term “server” may appear in the following specification, the disclosed embodiments are not limited to servers. 
       FIG. 7  sets forth details of the duplicate path application  105 , according to an embodiment. For travel booking and planning, it may be useful to import (e.g., manually, automatically) travel reservation information (e.g., from emails, other booking systems, etc.) about a trip. A trip may be a collection of related reservations. A reservation may be a single version of a travel plan as imported from another system, entered manually, etc. A reservation may contain a sequence of segments. A segment may be a single unit of travel (e.g., individual flight) with an origin and destination. A leg may be a sequence of segments in a reservation that are separated by a certain amount of time (e.g., fewer than 4 hours, such as when the arrival time of one segments is less than four hours before the departure time of the subsequent segment). 
     When importing information, duplicate information may be imported. Exact duplicates may be removed by direct comparison to existing data. Inexact duplicates may also be resolved. The duplicate path application  105  may find inexact duplicates, and may include, but is not limited to: a leg similarity module  705 , a construct leg graph module  715 , a traverse graph module  710 , or a recursive traverse graph module  720 , or any combination thereof. The leg similarity module  705  may determine whether legs are similar. The construct leg graph module  715  may construct a segment graph. The traverse graph module  710  may traverse and recursively traverse the segment graph. 
       FIG. 2  illustrates a method  200  for detecting duplicate travel path information, according to an embodiment. In  205 , a set of travel paths may be obtained. In  210 , each travel path may be broken into one or more legs. Thus, each travel path may be broken in to one or more sequences of segments (e.g., with less than four hours between them). In  215 , each leg in each travel path may be compared to each leg in every other travel path to determine whether any travel paths are duplicates. This may be done by creating a set containing each leg. Then, each leg in a reservation may be compared to each leg in every other reservation. If the sequences in the legs are similar, the sets containing the legs may be merged. Further details on  215  are described below with respect to  FIGS. 3A-3C . In  220 , any travel paths that are possible duplicates may be listed. This may be done by constructing a segment graph (explained in more detail in  FIG. 8 ) and then traversing the segment graph (explained in more detail in  FIGS. 9A-9B ) for each resulting set of similar legs. This may yield a sorted list of candidate paths of segments that may resolve the group of conflicting reservations. Manual intervention may be used to select the correct path from among the candidate paths. In an embodiment, the first path in the sorted list of candidates may be the path most likely to be the correct path. 
       FIGS. 3A-3C  illustrates a method for comparing legs to one another, according to an embodiment. Depending on the form of a reservation record, the reservation record may include a complete travel reservation, an updated travel reservation, or a partial travel reservation, or any combination thereof. In order to group related legs together, the similarity of two legs may be defined as containing a common subsequence, where the common subsequence contains at least one of their start points and one of their end points. The details of FIGURES  3 A- 3 C will be set forth below. The examples in  FIG. 4  and  FIG. 5  will be referred to in explaining the details of  FIGS. 3A-3C . The boxes in the charts in  FIG. 4  and  FIG. 5  have been marked with reference numerals to aid in the discussion of the examples. 
     Referring to  FIGS. 3A-3C , in  302 , legs may be input so that they may be compared. For example, in  FIG. 4 , the leg including the segments SFO to LAX and LAX to JFK may be input, and in  FIG. 5 , the leg including the segment LAX to JFK may also be input. In  304 , flags may be set to track whether the first and last columns and rows differ from their neighbors. These flags indicate whether the first or last segments of each leg are in the common subsequence. An array may also be created to store the current and previous rows of the dynamic programming table. In  306 , each row of the table may be looped, using i as an index. In  308 , each column of the table may be looped, using j as an index. In  310 , in case the first row or first column is being looped, the length of the longest subsequence so far may be initialized to be 0, or, in the case of a segment match, 1. Thus, for example, box  7  in  FIG. 4  takes the value of 0, since SFO does not match LAX. With respect to  FIG. 5 , box  7  takes the value 1, since SFO does match SFO. In  312 , if looping on the second or later row, the previous row may be referred to for a possible longest subsequence so far. Thus, if i is greater than 0 (e.g., are we looping on at least the second row?), the length of the subsequence may be set to up. For example, with respect to  FIG. 4 , box  14  takes the value of 1, which is copied from box  9 , since LAX does not match JFK. With respect to  FIG. 5 , box  12  takes the value of 1, which is copied from box  7 , since SFO does not match DFW. If i is not greater than 0, than in  314 , it is determined if j is greater than 0 (e.g., are we looping on at least the second column?). If j is greater than 0, the length of the subsequence may be set to left. If j is not greater than 0, then in  316 , we can look to the upper left in the previous row and previous column. The length of the common subsequence so far may be set as upleft (e.g., the box diagonal to the box being considered plus one). This subsequence will only be used if the current position in the table occupies the intersection of matching segments in leg 1  and leg 2 . For example, in  FIG. 4 , box  9  takes the value 1, which is the value of box  3  plus 1. This is because a segment origin of LAX in one leg matches a segment origin of LAX in the other leg. Note that  FIG. 4 , box  8  takes the value 0, since a destination of LAX in one leg does not match an origin of LAX in the other leg. With respect to  FIG. 5 , box  25  takes the value 2, which is the value of box  19  plus one. This is because the destination JFK in one leg matches the destination JFK in the other leg. In  318 , if both legl at position i and leg 2  at position j are origins (e.g., i and j are both even), and the identities of the two origins are the same, upleft may be considered as the best subsequence so far. In  320 , if both leg 1  at position i and leg 2  at position j are destinations (e.g., i and j are both odd), and the identities of the two destinations are the same, upleft may be considered as the best subsequence so far. In  322 , if upleft is greater than both up and left, then it is the length of the longest subsequence of which the current match is a part. In  FIG. 4 , box  9 , for example, up is 0, left is 0, and upleft is computed to be 1 (because the value of box  3  is 0, and 0+1=1), since LAX matches LAX. In  FIG. 5 , box  25 , the situation is similar; up is 1, left is 1, and upleft is computed to be 2, since JFK matches JFK and 1 is added to the value of box  19  ( 1 ) to yield 2. In  324 , if we are in the first row, it may be remembered that we detected a difference in the first row. In  326 , if we are in the first column, it may be remembered that a difference was detected in the first column. In  328 , if we are in the last row, it may be remembered that we detected a difference in that row. In  330 , if we are in the last column, it may be remembered that we detected a difference in that column. With respect to  FIG. 4 , there are differences shown in the first rows (e.g., boxes  4  and  5  differ from boxes  9  and  10 ) and the last columns (e.g., boxes  9  and  14  differ from boxes  10  and  15 ). In  FIG. 5 , there are differences shown in the first rows (e.g., boxes  2 ,  3 ,  4  and  5  differ from boxes  7 ,  8 ,  9  and  10 ), first columns (e.g., boxes  6 ,  11 ,  18  and  21  differ from boxes  7 ,  12 ,  17 ,  22 ), last rows (e.g., boxes  17 ,  18 ,  19 , and  20  differ from boxes  22 ,  23 ,  24  and  25 ), and last columns (e.g., boxes  9 ,  14 ,  19 , and  24  differ from boxes  10 ,  15 ,  20  and  25 ). In each case, this may be sufficient to indicate that the first segments or last segments of either leg are included in the common subsequence, which may be a necessary condition for considering the legs to be similar. In  332 , the current table location may be filled with the value of upleft, the length of the longest common subsequence so far. In  334 , it may be checked whether up or left (e.g., the box above or the box to the left) is greater. If up is greater, in  336 , the current table location may be filled with the value of up, the length of the longest common subsequence so far. For example,  FIG. 4 , box  14  and  FIG. 5 , box  12  are filled with the value of the boxes above them, since that value is greater than the values in the boxes to the left of them. If left is greater, in  338 , the current table location may be filled with the value of left, the length of the longest common subsequence so far. For example,  FIG. 4 , box  10  and  FIG. 5 , box  8  are filled with the value of the boxes to the left of them, since that value is greater than the values in the boxes above them. If up and left are equal, we may, without loss of generality choose the value of either up or left to fill the current table location. In  340 , this_row and last row may be swapped to move the current row into the previous row&#39;s position and to make room to store the next row. In  342 , we may loop to the next row. In  344 , we may loop to the next column. In  346 , if the first column and the first row are both the same as their previous neighbors (e.g., all 0), then this may indicate that neither leg&#39;s first segment is represented in the common subsequence, so the match may be rejected in  352 . In  FIG. 4 , this would have been the case if boxes  7 ,  8 ,  9 ,  10 , and  12  were all zero and therefore equal to the previous adjacent rows and columns. In  FIG. 5 , this would have been the case if boxes  7 ,  8 ,  9 ,  10 ,  12 ,  17 , and  22  were all zero and therefore equal to the previous adjacent rows and columns. In neither case was this true, so neither match may be rejected on this basis. In  348 , if the last column and the last row are both the same as their previous neighbors, then this may indicate that neither leg&#39;s last segment is represented in the common subsequence, so the match may be rejected in  352 . In  FIG. 4 , this would have been the case if boxes  10 ,  12 ,  13 ,  14 , and  15  were equal to the previous adjacent rows and columns. In  FIG. 5 , this would have been the case if boxes  10 ,  15 ,  20 ,  22 ,  23 ,  24 , and  25  were equal to the previous adjacent rows and columns. In neither case was this true, so neither match may be rejected on this basis. In  350 , if the bottom-right-most element in the table is greater than 0, then there may be a nonempty common subsequence, so the match may be accepted in  354 . In  FIG. 4 , box  15  takes the value 2 and in  FIG. 5 , box  25  takes the value 2, so in both cases, there may be a nonempty common subsequence. If the answer to  346 ,  348 , or  350  is no, in  352 , the match may be rejected. If the answer to  346 ,  348  and  350  is yes, in  354 , the match may be accepted. 
     After groups of legs that are similar to each other are identified, as shown in  FIGS. 3A-3C , which sequences of segments may represent an accurate representation of the correct travel reservation may be determined. To do this, a segment graph may be created where nodes represent origins and destinations, and edges represent bundles of identical segments. Each edge may represent one or more segments if the segments are identical. If two segments are not identical, but the segments have the same origin and destination, then they may be represented by two separate edges with the same origin and destination, which may result in a multigraph. 
     As explained above,  FIG. 8  illustrates details relating to constructing the segment graph, according to an embodiment. The graph data structure may comprise a collection of edges stored in a two dimensional associative array. The first dimension may be the identity of the origin of the segments in an edge. The second dimension may be the identity of the destination of the segments in an edge. The contents of the two dimensional associative array may be an array containing one or more edges. Each edge may be a set of identical segments. Referring to  FIG. 8 , in  805 , the graph we are building so far and the segment we wish to add to it may be input. The graph may be represented by a two dimensional associative array, indexed by origin and destination of segments. Each element of the graph may be a list of edges. Each edge may be a set of mutually identical segments. In  810 , the set of edges from the segment&#39;s origin and to the segment&#39;s destination may be obtained. In  815 , the existing edges may be looped over. In  820 , when there are no more edges, a new edge may be created with only the new segment, and this may be added to the graph. In  825 , the segments in the existing edge may be looped over. In  830 , it may be determined whether the new segment is identical to the existing segment in the existing edge. In  835 , if the new segment is identical, it may be added to the existing edge. This may maintain the invariant that identical edges occupy the same edge and non-identical segments belong to separate edges in the graph. 
     The process explained in  FIG. 8  may be performed for each segment from each similar leg to construct a graph containing all of the segments. After the segment graph has been constructed, the segment graph may be traversed to find paths of segments that may result in a correct reservation. We may begin from each node with an in-degree of zero and recursively follow edges until we reach a node with an out-degree of zero. We may also impose the restriction that no resulting path may break up more than one reservation. This may prevent forming implausible combinations of travel plans and may reduce the number of plans that must be manually examined for correctness. In addition, we may sort the resulting paths to place the most recently imported plans at the top of the list. Within each edge in a path, we may sort the segments to place the one with the most information first. This may provide a ranking of likelihood of any one candidate travel plan being the current correct plan. 
     Referring to  FIGS. 9A-9B , in  905 , the segment graph to traverse may be input. In  910 , the start nodes may be found (which may represent the starting travel locations) by looking for nodes in the graph with no edges pointing to them. A resulting array of paths to be empty may also be initialized. In  915 , the start nodes may be looped over. In  920 , the paths through the graph starting with a start node may be recursively traversed. A stack may be used to keep track of the current location as we traverse the graph. In  925 , we may check for cycles in the path. In  930 , the set of edges that originate at the current node may be obtained so that we can follow them. In  935 , if there are no edges that originate at the current node, then we have found a final destination node. In  940 , we may return to the path that we took to get to the current final destination mode. In  945 , we may loop over the nodes to which we can travel from the current node. In  950 , we may loop over the edges from the current node to the next node. In  955 , we may recursively traverse the rest of the graph, starting at the next mode. We may need to store our current state on a stack so that we can resume traversing the rest of the graph after traversing the next node. In  960 , once there are no more edges from the current node to traverse, we may pop the previous set of paths from the stack and merge the current set with it. We may then resume recursively traversing the graph starting with the previous node. In  965 , if we have popped the last set of paths from the stack, then we have returned to the start node. We may go back and traverse the graph from the next start mode. In  970 , once there are no more start nodes, we may have a complete collection of paths through the graph. We may remove all paths from the list that break up more than one reservation. In  975 , we may sort the paths so that the most recently imported paths are at the start of the list of paths. This may place the paths that are more likely to be correct at the start of the list. In  980 , within each edge, we may sort the segments so that the segments with the most information are at the start of the list of segments. This way, when a user selects a correct path, we can remove all but the correct segment with the most information. 
     With respect to  FIG. 6 , we traverse the graph as set out above. The only start node is SFO, since it has no edges leading to it. From SFO, we find an edge to LAX and from there two different edges to JFK. JFK is an end node, since it has no edges leading from it. We store each of the paths traversed so far, and backtrack. The paths so far are SFO to LAX to JFK, and a different SFO to LAX to JFK. After backtracking, we follow the path from SFO through DFW to JFK and store that path also. We finally sort those paths so that the most recent is first. If we assume that the path through DFW was imported most recently, then the list of candidate paths is, in sorted order “SFO to DFW to JFK”, “SFO to LAX to JFK”, and “SFO to LAX to JFK”. The last two paths will have different details for their respective LAX to JFK segments. 
     As noted above, at various points in  FIGS. 8-9B  we need to compare segments for identity and for information content. In particular, while sorting segments within an edge to determine the representative segment, we need to be able to compare two segments for the amount of information contained in each segment. Also, while constructing the graph and determining whether a segment should go in an existing edge or a new one, we need to be able to test whether two segments contain identical information. 
     Segments may contain more than just origin and destination information. They may also contain information such as start time and date, end time and date, entity information (e.g., airline, train line, bus line, etc.), travel numbers (e.g., flight numbers, train numbers, bus numbers, etc.) and other information. To define both identity and amount of information content, we may use a process such as the one explained in  FIGS. 10A-10B . 
       FIGS. 10A-10B  illustrates a method for segment comparison, according to an embodiment. In  1005 , the existing segment and the segment to compare with it are input. In  1010 , the list of attributes to compare is listed. In addition, the flag that indicates whether we have found a matching attribute may be set to false. In  1015 , we may interate over the attributes to compare. In  1020 , if the current attribute does not have a value in the existing segment, then we may skip comparing it. In  1025 , if the current attribute in the existing segment matches the value of the same attribute in the new segment, then we may remember that a match was found in  1030 . In  1030 , we may remember that a match was found and continue comparing the rest of the attributes. In  1035 , if no match was found for a value that exists in the existing segment, we may return false, since their values are in conflict. In  1040 , if the flight numbers of the two segments match, we may remember tha a match was found in  1045 . In  1050 , if the flight numbers of the two segments conflict, then we may return “false”, regardless of any other matching attributes, by setting the flag to false in  1055  to override any matches that were found. In  1060 , we may return the final value of the flag. If there are any matches and no conflicts, then the result may be set as “true”. 
     While various embodiments have been described above, it should be understood that they have been presented by way of example and not limitation. It will be apparent to persons skilled in the relevant art(s) that various changes in form and detail can be made therein without departing from the spirit and scope. In fact, after reading the above description, it will be apparent to one skilled in the relevant art(s) how to implement alternative embodiments. Thus, the present embodiments should not be limited by any of the above-described embodiments. 
     In addition, it should be understood that any figures which highlight the functionality and advantages are presented for example purposes only. The disclosed methodology and system are each sufficiently flexible and configurable such that they may be utilized in ways other than those shown. For example, the elements in the flowcharts may be performed in parallel or in a different order. 
     Further, the purpose of any Abstract of the Disclosure is to enable the U.S. Patent and Trademark Office and the public generally, and especially the scientists, engineers and practitioners in the art who are not familiar with patent or legal terms or phraseology, to determine quickly from a cursory inspection the nature and essence of the technical disclosure of the application. An Abstract of the Disclosure is not intended to be limiting as to the scope of the present invention in any way. 
     It should also be noted that the terms “a”, “an”, “the”, “said”, etc. signify “at least one” or “the at least one” in the application (e.g., specification, claims and drawings). 
     Finally, it is the applicant&#39;s intent that only claims that include the express language “means for” or “step for” be interpreted under 35 U.S.C. 112, paragraph 6. Claims that do not expressly include the phrase “means for” or “step for” are not to be interpreted under 35 U.S.C. 112, paragraph 6.