Method and system for deterministic matching of objects and events which are not uniquely identified

A method, and a system for carrying out that method, for deterministically matching first elements of a first set of objects or events with second elements of a second set of objects or events. Matching first and second elements are associated with common values of an identification code pn having |pn| characters, and where the identification code can be insufficient to uniquely identify the first elements, and portions of the identification code values associated with the first and second elements can be unknown. The method includes the steps of: a) generating a mapping θ for the first set such that, for each element li of the first set θ(li) equals <ki, ppni>, where pni is at least a portion of the identification code value associated with the element li and ppni is defined as the first ki characters of pni, and ki is selected to be the minimum number of characters required to uniquely identify li in the first set, whereby values for ki greater than |pn| imply that the element li is not uniquely identified by the portion ppni; b) determining pnj for an element ej in the second set, where pnj is at least a portion of the identification code value associated with the element ej; and c) matching the element ej and the element li only if the first ki characters of pnj equal ppni and not matching the element ej and the element li if the element li is not uniquely identified in the first set by the portion pnj. The system can be controlled in accordance with program code on a computer readable medium. In one embodiment of the invention the first elements are letters and the second elements are events which occur during processing of the letters. In another embodiment of the invention the method includes a step of performing an additional consistency test and matching said letter li and event ej only if said consistency test confirms such match.

BACKGROUND OF THE INVENTION

S:“the set S”|S|:“the number of elements in S.”|x|:“the number of characters in ‘x’”S U s:“the addition of element s to S”<v1, . . . vn>:“the n-tuple of values vi”→:“maps to”

The subject invention relates to deterministic matching of objects or events in a first set with objects or events in a second set when the objects or events are not all uniquely identified. More particularly it relates to matching letters to events which occur during the delivery of such letters. By “deterministic matching” herein is meant matching of events (or elements in the second set) to letters (or elements in the first set) if and only if sufficient information is available to uniquely associate events with particular letters.

It is often useful to be able to match objects or events in a first set with objects or events in other sets. For example, a hypothetical automobile assembly process may require that a particular engine be assembled with a particular style body, paint color, etc. to produce a car as ordered. An effective way to achieve this is to associate codes with the objects or events to be matched so that objects or events which match are associated with the same code. This a relatively simple process where the codes suffice to uniquely identify the objects or events within each set. However, if the codes are not sufficient to uniquely identify the objects or events which match, the task of matching becomes much more difficult. Thus, in the automotive example given above, if order number 123456 calls for a high performance engine but the engine is coded 12345; either because of a mistake or because of a systematic problem (e.g. the engine encoder can only specify 5 digits) it may or may not be possible to deterministically match the engine to an order. Assuming that it is desirable that orders be filled in the normal process where possible, but more important that no unordered cars be assembled; the need for a deterministic matching method can be seen.

An actual example of a process in which a deterministic matching method can be used to good effect is the mail tracking program recently introduced by the United States Postal Service (hereinafter sometimes “USPS”)under the trademark CONFIRM®. The CONFIRM program tracks mailpieces through the delivery process and provides the mailer with information about the status of the mailpiece in the delivery process.

FIG. 1shows a simplified representation of the USPS mailpiece delivery process incorporating the CONFIRM mail tracking process. Mailers10deliver large mailings12to local postal facilities14. Mailings12can comprise letters, flats, periodicals, or the like (sometimes hereinafter generally “letters”) and are typically pre-sorted to various degrees by mailers10to obtain discounts offered by the USPS. (While the general principles of the CONFIRM process can be applied to any mailpiece or package, as currently implemented by the USPS it used for tracking large, typically pre-sorted, mailings and reply mail returned in pre-addressed and pre-coded business reply envelopes (sometimes herein “BRE's”) sent out in such mailings.)

At facility14scanner16scans mailings12to establish the times at which mailings12entered the mail delivery process. Typically individual letters are not scanned at facility14, though they can be if appropriate scanners are available, and accompanying documents(not shown) are scanned to establish the time and facility at which each of mailings12entered the delivery process and/or the times at which mailings12are sent on in the delivery process. This information is then sent to programmable data processing system (hereinafter sometimes server)22over one of communications links20. (Links20connect various postal facilities to server22and can take any convenient form or forms; details of which form no part of the subject invention.) Mailings12and other mailpieces (not shown) are then grouped to form assemblies28which are then delivered to sectional postal center30. At center30assemblies28, together with other assemblies28from other facilities (not shown) are processed by conventional high speed scanner/sorters32. As letters are sorted and otherwise processed at center30a POSTNET code (commonly known as a “zipcode” and hereinafter sometimes “pn”) and a code used in the CONFIRM process known by the USPS trademark PLANET Code® (hereinafter sometimes “pc”) are scanned from the letters. The pair <pn, pc> identify, though not necessarily uniquely identify, the letters within a set of letters, and events associated with those letters, as will be described further below. In accordance with USPS requirements the POSTNET Code and PLANET Code are printed as barcodes. As letters are scanned, typically for the first time at center30, the values pn and pc are sent to sever22over one of links20, where they are combined with information about mailings12from facility14, as will be described further below. (Note that the PLANET Code for a letter will identify a corresponding mailing so that the time a letter entered the mail delivery process can be determined by sever22from information provided by facility14.)

Sorted assemblies36are delivered to local postal facilities38for further sorting and delivery of letters l. Letters l can be scanned at facilities by scanners40and information including values for pn and pc sent to server22over one of links20. BRE's included in mailings12can be returned by the receiving customers and are scanned, sorted and delivered in substantially the same manner as described above, except that BRE's are typically returned as individual letters and, of course need not follow the same path through the postal system as mailings12.

As a letter moves through the delivery process and various steps or stages occur (hereinafter sometimes “events”) and these events are recorded as an n-tuple <d, f, t, pn, pc> where:d is the time at which the event occurred;f is the facility at which the event occurred;t is the type of event;pn is the POSTNET (possibly partial) scanned from the letter when the event occurs; andpc is the PLANET Code scanned from the letter when the event occurs.
Server22is programmed to match these events with letters having corresponding values for the pair <pn, pc> and maintain database24of matched letters and events. Mailers10can then access database24through server22and network42, or in any other convenient manner, to determine the status of letters in the mail delivery system. However the <pn, pc> data is often incomplete or inaccurate. Further, different letters may have the same values for <pn, pc>. Thus it is not always possible to uniquely match an event and a corresponding letter. Since mailers would rather have no tracking information than incorrect information, there is a need for a deterministic method and system which will match letters and events in the context of the USPS CONFIRM system. Current methods for matching letters and events attempt to match only those cases where the full (11 digit) POSTNET code and PLANET Code are scanned and allow matching of approximately 80 to 85% of events to letters; rejecting the remaining 15 to 20%.

Program code to control server22in accordance with the subject invention is provided on magnetic or optical disk46-D and input through disk reader46-R, or through any other suitable computer readable medium. The term “computer-readable medium” as used herein refers to any medium that participates in providing program code to a processor for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, or random access read only memory. Volatile media includes random access dynamic memory. Transmission media includes coaxial cables, copper wire and fiber optics. Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. By “program code” herein is meant sequences of indicia recorded on, or signals transmitted by, computer readable media, which, when input by a processor cause a processor to carry out a corresponding sequence of operations, i.e. execute the program code.

InFIG. 2letter l includes a delivery address printed in block50, a return address printed in block52, a stamp or postal indicium indicating payment of postage54, PLANET Code barcode56, and POSTNET barcode58. Letter l can be printed with additional markings which do not relate to the subject invention and can be arranged in somewhat different formats without affect on the teaching of the present application. Barcode58typically represents 5, 9, or 11 digits which specify delivery information with increasing precision. The code used is typically determined by the information available to mailer10or by the extent which mailer10wishes to pre-sort mailings12. PLANET Code56can take on one of two formats, format56-D to track delivery of letters in mailings12and format56-0to track BRE's returned by customers. Format56-D specifies the service (e.g. first class letters, standard mail flats, etc.) subscriber (i.e. mailer) id, and mailing id. Typically there is one PLANET Code used in a mailing. Format56-0specifies the service and a customer id. The CONFIRM system relies on the BRE's POSTNET code to identify the mailer.

While generally the POSTNET and PLANET Code, i.e. the pair<pn, pc>, uniquely specify a letter it is apparent that this need not be so. For example, if a mailer10chooses not to sort a mailing12, letters in that mailing may only have a 5 digit POSTNET code with many letters having the same value for pn. Or scanners at various facilities may not have a capability to scan a full 11 digit POSTNET code so that a event record can not always be uniquely associated with a letter record. More rarely, even the full POSTNET code will not distinguish all letters, as when two letters in a mailing are sent to the same address. (Since the CONFIRM system is relatively new it is believed all PLANET Code scanners can scan the full PLANET Code.)

(The above simplified description of the mail delivery process and the CONFIRM system is given to provide background and those skilled in the art will recognize that substantial differences from actual mail delivery can exist. Such differences however are not believed to affect the present teaching. Further details of the CONFIRM system are found in:The CONFIRM® System Customer Service Guide, United States Postal Service, publication no. 197, September 2002.)

Thus it is an object of the subject invention to provide a method and system for deterministic matching of objects and events, such as letters and events occurring as the letters are delivered, even though the letters and events are not necessarily uniquely identified.

BRIEF SUMMARY OF THE INVENTION

The above object is achieved and the disadvantages of the prior art are overcome in accordance with the subject invention by a method, and a system for carrying out that method. The method deterministically matches first elements of a first set of objects or events with second elements of a second set of objects or events, matching first and second elements each being associated with common values of an identification code pn having |pn| characters, and where the identification code can be insufficient to uniquely identify the first elements, and portions of the identification code values associated with the first and second elements can be unknown; and includes the steps of: a) generating a mapping θ for the first set such that, for each element liof the first set θ(li) equals <ki, ppni>, where pniis at least a portion of the identification code value associated with the element liand ppniis defined as the first kicharacters of pni, and kiis selected to be the minimum number of characters required to uniquely identify liin the first set, whereby values for kigreater than |pn| imply that the element liis not uniquely identified by the portion ppni; b) determining pnjfor an element ejin the second set, where pnjis at least a portion of the identification code value associated with the element ej; and c) matching the element ejand the element lionly if the first kicharacters of pnjequal ppniand not matching the element ejand the element liif the element liis not uniquely identified in the first set by the portion pni. The system can be controlled in accordance with program code on a computer readable medium.

In accordance with one aspect of the subject invention the first elements are letters and the second elements are events which occur during processing of the letters.

In accordance with another aspect of the subject invention the method includes a step of performing an additional consistency test and matching said letter liand event ejonly if said consistency test confirms such match.

In accordance with still another aspect of the subject invention the method includes: a) generating a minimal k-unique mapping for said first set such that, for each element liof said first set such that limaps to a pair <ki, ppni>, where pniis at least a portion of said identification code value pn associated with said first elements and ppniis defined as the first kicharacters of pni, b) determining pnjfor an element ejin said second set, where pnjis at least a portion of said identification code value associated with said element ej; and c) matching said element ejand said element lionly if the first kicharacters of pnjequal ppniand not matching said element ejand said element liif said element liis not uniquely identified in said first set.

Other objects and advantages of the subject invention will be apparent to those skilled in the art from consideration of the detailed description set forth below and the attached drawings.

FIG. 3shows database24of letters l and events e. File60includes records62-1through62-M, M=|L|, and corresponds to a set L of letters l. Records62include fields l which contain n-tuples <id, pn, pc, s, ed> where:id is a unique identifier for the n-tuple generated by sever22,pn is a POSTNET value,pc is PLANET Code value,s is the time corresponding physical letters entered the mail process (i.e. the time that the corresponding mailing12was received at facility14), anded is the estimated latest time of delivery of corresponding physical letters; and fields64contain the pairs <k, ppn>=<k, pre(pn, k)> (where pre(pn, k) is defined as the first k digits of pn) which map to the pair <pn, pc> such that letter l is minimally k-uniquely identified in L by <pn, pc>, as will be describes further below.

Latest time of delivery ed is determined by the USPS in a known manner in accordance with factors such as the type of mail, degree of pre-sorting, etc., and is typically 7 to 14 days. The pair <s, ed> define a life-span of a letter and if a letter is not delivered within its life-span it is unlikely that it will be delivered at all.

File66includes records68-1through68-M, and corresponds to events e in set E which are matched to letters l, as will be described further below. Records68include fields70which contain a value id identifying a letter l and pluralities of fields72, each field in pluralities72containing an event exto indicate that events e recorded in one of records68are matched to the letter l identified in that record. InFIG. 3event ejhas been expanded to show n-tuple <dj, fj, tj, pnj, pcj>, as described above.

As discussed above, in general it is not always possible to match letters l and events e. Letter l may not be uniquely identified by pair <pn, pc>, or only a portion of pn may be scanned during the event so that insufficient information is available to uniquely match the event to a letter. Such unmatched events can be handled in any convenient manner, details of which form no part of the present invention.

Those skilled in the art will recognize that database24can be organized in other ways, and details of the organization of database24form no part of the subject invention.

FIG. 4shows a flow diagram of the operation of server22in updating or generating a set L which is minimally k-uniquely mapped by a mapping θ such that θ(li)=<ki, ppni>. Set L is defined as k-uniquely mapped if for each letter liin L: li→<ki, ppni>, kian integer such that min|pn|≦ki≦max|pn| (where preferably min|pn|=5, max|pn|=11), if and only if for all letters li, lj, in L, i≠j, <pci, pre(pni, ki)>≠<pcj, pre(pnj, ki)>. Set L is defined as minimally k-uniquely mapped if L is k-uniquely mapped, and for all letters li, lj, in L, ki>|pn|, <pci, pre(pni, ki−1)>=<pcj, pre(pnj, ki−1)>. That is: if set L is minimally k-uniquely mapped then for each letter liki, if it exists, specifies the minimum number, greater than min|pn|, of initial digits of pniwhich are sufficient to distinguish <pci, pni> from all other<pcj, pnj>, and thus distinguish lifrom all other letters ljin L.

(It should be noted that there is a one-to-one correspondence between n-tuples contained in fields l and corresponding physical letters, and a similar correspondence between n-tuples <d, f, t, pn, pc> and events, and that what are actually matched in accordance with the subject invention are corresponding records in database24. Accordingly, except where the difference may be both significant and unclear, the terms “letters” and “events” are used herein to refer to both physical letters and events and the corresponding n-tuples, <id, pn, pc, s, ed> and <d, f, t, pn, pc>, respectively.)

Initially at step80inFIG. 4letter set L includes letters lj, j=1, 2, . . . |L| or may be empty. Letters lj→kj, ppnj>; where kjis a positive integer representing a previous minimal k-unique mapping of |L|. The index k is initially set equal to min|pn|, which is preferably equal to 5. (Set L is assumed to have been previously sorted so that for all letters li, ljin L, it can be assumed, without loss of generality, that pci=pcj.)

After starting, at step82server22sets m=1 and at step84inputs a new letter lm=<idm, pnm, pcm, sm, edm>. For ease of description letter lmis assumed to be input as it is scanned for the first time, as would be the case, for example, with a BRE. For letters in mailings it can be that the life span, <sm, em>, is determined when the mailing is delivered to facility14, as described above, and server22will match letter ljto the appropriate life span in accordance with pcmwhen letter ljis first scanned separately. This operation would be well within the abilities of one skilled in the art and need not be described further here for an understanding of the subject invention. In either case, at step84an arbitrary unique identifier idmis added to field lmin record62-m(shown inFIG. 3). This identifier is used to identify record62-min database24and is typically not included on physical letters l.

Then at step86, server22tests to determine if m=1, and, if so, at step90maps lm=l1to <5, ppnm>, since at this point only l1is in L. Then at step92server22sets m=m+1, and at step94determines if there are any more letters to be input. If not the program ends and, otherwise returns to step84.

Thereafter, for each letter lm, at step98server22sets j=1 and at step100tests to determine if j=m and if not at step102tests if pre(pnj, k)=pre(pnm, k). That is, if the first k characters (initially 5 characters) of pnjequal the first k characters of pnm. If so, at step106the equals flag, EQF, is set equal to 1, and at step108server22tests to determine if kj<k+1, and if so, at step110sets kj=k+1; since step102has shown that at least k+1 characters are necessary to distinguish pnjfrom pnm. Then, or if kjis less than k+1, or if at step102pre(pnj, k)≠pre(pnm, k), at step112server22sets j=j+1 and goes to step100.

If at step102|pnj| or |pnm| are less than k, pnjor pnmare filed out with unknown characters “?” which are considered to match any character. For example, for pn=1,2,3,4,5 pre(pn, 7)≡1,2,3,4,5,?,? and is considered to equal 1,2,3,4,5,x,y; where “x” and “y” can be any character, including “?”.

If at step100j=m, server22goes to step114to determine if EQF is set. Since lmhas been tested at step102against ljfor all j, j<m; and if EQF is not set then the current value of k is sufficient to uniquely distinguish letter lmfrom all letters ljin L, then if EQF is not set at step120kmis set equal to the current value for k and lm→<km, ppnm>, i.e. <k, ppnm> is stored in field64-m(shown inFIG. 3) and L, as currently constituted, is minimally k-uniquely mapped. Then at step122EQF is reset and k is set equal to 5, and server22then goes to steps92and94and either exits or inputs a next letter, as described above.

If EQF is set at step114, then at step124server22determines if k=max|pn| (preferably max|pn|=11) and, if not, at step126sets k=k+1 and resets EQF and goes to step98to repeat the cycle described above for the next value for k. If k=max|pn|, then at step130kmis set equal to max|pn|+1 and lm→<km, X>, i.e. <max|pn|+1, X>, where X is arbitrary, is stored in field64-m; indicating that for at least one j, ≠m, pnj=pnm(and thus that ljand lmare not uniquely identified) and then goes to steps122,92, and94, as described above.

(A file of previously scanned, unmapped letters l can be mapped by modifying the operation of server22as shown inFIG. 4by:setting all kj≦min|pn|setting m=1 at step82, anddeleting step84.)

FIG. 5shows a flow diagram of the operation of server22in matching events e in set E to letters l in set L. At step150server22waits for the occurrence of an event in the delivery process. When an event ejoccurs during delivery of a letter l server22inputs event ej=<dj, fj, tj, pnj, pcj> and sets i=1 at step152. At step154server22gets liand ⊖(li); that is, it obtains fields liand64-iin record62-iin file60(shown inFIG. 3).

Tests at steps156through164are then applied to determine if event ejis uniquely matched to letter li. At step156it is determined if pcjequals pci. If so, at step160it is determined if kiis less than or equal to |pnj|; that is if there are sufficient characters in pnj, as scanned, to uniquely match ejand li. Note that this test prevents a match if kiis greater than max|pn|; i.e. liis not uniquely identified in L. If so, then at step162it is determined if pre(pnj, ki) is equal to ppni; that is if the first kicharacters of pnjand pniare equal; which serves to uniquely establish a match. Then, as a consistency check, at step164it is determined if si<dj<edi; that is if event ejhas occurred during the life period of letter li. If all the above tests are passed then at step168event ejis uniquely matched to letter li;, preferably by storing <dj, fj, tj, pnj, pcj> in field ejin record68-iso that it is associated with identification idiin field70-i(shownFIG. 3).

Approximately 2 to 8% of letters which should have a full POSTNET code are initially produced or described by mailers with less than the full 11 digits. In at least some cases the USPS has the capability to correct this and provide the full POSTNET code, with the result that |pnj| will be greater than |pni|. (The manner in which this correction is made forms no part of the subject invention and need not be described further here.) Accordingly, in the preferred embodiment shown, at step170server22determines if |pnj|>|pni|, and, if so, at step172sets pni=pnjso that the full, or extended, value can be used for matching later, downstream events.

Then at step186server22determines if any more events are pending, and if so returns to step152to process the next event, and otherwise exits. If any of the above described tests are not passed then at step176server22determines if i equals M; that is if all letters l have been tested. If so, at step178a no match is recorded for event ejin any convenient manner and server22goes to step170and continues as described above. Otherwise i is set equal to i+1 at step180and server22returns to step154.

In other embodiments of the subject invention other consistency tests can be used in addition to or in place of the test of step164. For example the type tjand location djcan be tested for consistency; e.g. automatic sortation at a facility lacking such equipment.

Those skilled in the art will recognize that where event ejis the entry of a letter liinto the delivery process then it is only necessary to start a new record68-iin file66including entry event ej.

Returning toFIG. 1, when one of mailers10wishes to determine the status of a letter l in a mailing, or if a BRE in a mailing has been returned, an inquiry can be submitted to server22through network42. Server22can then access database24to identify relevant events which have occurred; and from the above description it will apparent to those skilled in the art that events will be identified if and only if they are deterministically matched to a letter.

The embodiments described above and illustrated in the attached drawings have been given by way of example and illustration only. From the teachings of the present application those skilled in the art will readily recognize numerous other embodiments in accordance with the subject invention. Particularly it will be apparent to those skilled in the art that the sequences of steps and data structures described above can be altered in numerous logically equivalent ways without departing from the scope of the subject invention. Accordingly, limitations on the subject invention are to be found only in the claims set forth below.