Registration and maintenance of address data for each service point in a territory

• US 7,542,972 B2
• Filed: 01/27/2006
• Issued: 06/02/2009
• Est. Priority Date: 01/28/2005
• Status: Active Grant

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Owens, Timothy C., Anderson, Duane
• Primary Examiner(s): Cottingham; John
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US11/342,041
• Publication Number:
  US 20070282900A1
• Time in Patent Office: 1,222 Days
• Field of Search: 705/404, 705/26, 705/6, 705/7, 705/1, 707/1, 707/100, 707/6, 707/4, 235/380
• US Class Current: N/A
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer system and method is disclosed for mining current and archived address data in order to identify a preferred address for each service point in a territory. The data mining system may start in response to the presentation of a candidate address for matching. The set of mined data may be prioritized by clustering like characteristics, building similarity matrices, and by constructing dendrograms with nodes joined according to common characteristics. A computer system and method for maintaining a central database of preferred addresses is also disclosed. Selected address data gathered in a queue may be scored by characteristic, grouped by consignee location, and staged for processing. The scored queue of data may be prioritized by clustering like characteristics, building similarity matrices, and by constructing dendrograms.

Claims

1. A computer-implemented method of mining address data to locate a preferred address for each of a plurality of parcels, comprising:

maintaining a package-level detail database of active shipment records in associated memory, each active shipment record comprising an active tracking number, an active ship-to address, and an active delivery pattern code;

maintaining an electronic archive of delivery records in said memory, each delivery record comprising a past tracking number, a past ship-to address, a past delivery pattern code, and a stop identifier;

receiving address indicia associated with a current parcel;

assigning a mining key to said current parcel, said mining key comprising a parcel tracking number and a current delivery pattern code related to said address indicia;

comparing said mining key to said package-level detail database and said archive by having one or more computer components execute logic for;

(a) retrieving from said archive those select delivery records having a past delivery pattern code that matches said current delivery pattern code, each of said select delivery records having a select past ship-to address;

(b) retrieving from said package-level detail database those select active shipment records having an active ship-to address that matches any said select past ship-to address in said select delivery records;

building a set of mined data comprising said select delivery records and said select active shipment records;

prioritizing said set of mined data in order of the records most closely associated with said mining key, such that a preferred address related to said mining key occurs first, wherein said step of prioritizing said set of mined data comprises having at least one of said one or more computer components execute logic for;

(a) replacing one or more sequence values in a plurality of ship-to address records having the same stop identifier;

(b) clustering together those said ship-to address records having the same delivery pattern code;

(c) building a delivery pattern similarity matrix by counting the coincidence of each delivery pattern code and each ship-to address within said set of mined data;

(d) summing the overlapping delivery pattern occurrences within said delivery pattern similarity matrix for each pair of ship-to addresses;

(e) building a stop identifier similarity matrix by counting the coincidence of each stop identifier and each ship-to address within said set of mined data;

(f) summing the overlapping stop occurrences within said stop identifier similarity matrix for each pair of ship-to addresses; and

(g) sorting said set of mined data in order of the highest number of overlapping delivery pattern occurrences and the highest number of overlapping stop occurrences; and

assigning said preferred address to said current parcel for delivery.

2. The method of claim 1, wherein said step of comparing further comprises having at least one of said one or more computer components execute logic for:

(c) retrieving from said archive those additional delivery records having a past delivery pattern code that matches any said current delivery pattern code in said select active shipment records, each of said additional delivery records having an additional past ship-to address;

(d) retrieving from said package-level detail database those additional active shipment records having an active ship-to address that matches any said select additional ship-to address in said additional delivery records; and

repeating steps (c) and (d) in a plurality of iterations until said step of building a set of mined data reaches a limit condition.

3. The method of claim 1, further comprising:

selecting said preferred address as a preferred consignee address for a single consignee location;

assigning a unique consignee token related to said single consignee location; and

storing said unique consignee token and said preferred consignee address in a master address database located in said memory.

4. The method of claim 1, wherein said step of prioritizing said set of mined data further comprises having at least one of said one or more computer components execute logic for:

converting said stop identifier similarity matrix into a stop identifier dendrogram;

constructing a stop-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, summing said number of occurrences to form a joined stop node, and by joining the next stop pair of ship-to addresses or joined stop nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next stop pair is zero;

converting said delivery pattern similarity matrix into a delivery pattern dendrogram; and

constructing a pattern-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, using the minimum of said number of occurrences to form a joined pattern node, and by joining the next pattern pair of ship-to addresses or joined pattern nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next pattern pair is zero.

5. The method of claim 1, wherein said step of assigning said preferred address to said current parcel for delivery comprises:

presenting said set of mined data to an address database administrator via an electronic display device; and

receiving a selection of said preferred address by said administrator via an electronic input device.

6. A computer-implemented method of scoring and maintaining address data for any of a plurality of records in an address database, comprising:

maintaining a package-level detail database of active shipment records in associated memory, each active shipment record comprising an active tracking number, an active ship-to address, and an active delivery pattern code;

maintaining an electronic archive of delivery records in said memory, each delivery record comprising a past tracking number, a past ship-to address, a past delivery pattern code, and a stop identifier;

gathering address data from said detail database and said archive into a queue for a period of days;

scoring said address data in said queue;

building a consignee staging queue for storing those data in said queue related to a select consignee location;

assigning a mining key to a current parcel selected from said consignee staging queue, said mining key comprising a parcel tracking number and a current delivery pattern code;

comparing said mining key to said package-level detail database and said archive by having one or more computer components execute logic for;

(a) retrieving from said archive those select delivery records having a past delivery pattern code that matches said current delivery pattern code, each of said select delivery records having a select past ship-to address; and

(b) retrieving from said package-level detail database those select active shipment records having an active ship-to address that matches any said select past ship-to address in said select delivery records;

building a set of mined data comprising said select delivery records and said select active shipment records;

prioritizing said set of mined data in order of the records most closely associated with said mining key, such that a preferred address related to said mining key occurs first, wherein said step of prioritizing said set of mined data comprises having at least one of said one or more computer components execute logic for;

(a) replacing one or more sequence values in a plurality of ship-to address records stored in said set of mined data with a representative symbol;

(b) clustering together those said ship-to address records having the same stop identifier;

(c) clustering together those said ship-to address records having the same delivery pattern code;

building a delivery pattern similarity matrix by counting the coincidence of each delivery pattern code and each ship-to address within said set of mined data;

(d) summing the overlapping delivery pattern occurrences within said delivery pattern similarity matrix for each pair of ship-to addresses;

(e) building a stop identifier similarity matrix by counting the coincidence of each stop identifier and each ship-to address within said set of mined data;

(f) summing the overlapping stop occurrences within said stop identifier similarity matrix for each pair of ship-to addresses; and

(g) sorting said set of mined data in order of the highest number of overlapping delivery pattern occurrences and the highest number of overlapping stop occurrences; and

assigning said preferred address to said current parcel and updating said address database.

7. The method of claim 6, wherein said step of comparing further comprises having at least one of said one or more computer components execute logic for:

(c) retrieving from said archive those additional delivery records having a past delivery pattern code that matches any said current delivery pattern code in said select active shipment records, each of said additional delivery records having an additional past ship-to address;

(d) retrieving from said package-level detail database those additional active shipment records having an active ship-to address that matches any said select additional ship-to address in said additional delivery records; and

repeating steps (c) and (d) in a plurality of iterations until said step of building a set of mined data reaches a limit condition.

8. The method of claim 6, further comprising:

selecting said preferred address as a preferred consignee address for a single consignee location;

assigning a unique consignee token related to said single consignee location; and

storing said unique consignee token and said preferred consignee address in a master address database located in said memory.

9. The method of claim 6, wherein said step of prioritizing said set of mined data further comprises having at least one of said one or more computer components execute logic for:

converting said stop identifier similarity matrix into a stop identifier dendrogram;

constructing a stop-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, summing said number of occurrences to form a joined stop node, and by joining the next stop pair of ship-to addresses or joined stop nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next stop pair is zero;

converting said delivery pattern similarity matrix into a delivery pattern dendrogram; and

constructing a pattern-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, using the minimum of said number of occurrences to form a joined pattern node, and by joining the next pattern pair of ship-to addresses or joined pattern nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next pattern pair is zero.

10. The method of claim 6, wherein said step of scoring said address data in said queue comprises having at least one of said one or more computer components execute logic for:

generating a count table for a number of occurrences of each of a plurality of delivery conditions on each day of said period;

calculating for each stop identifier a measure number for each of a plurality of corresponding outcomes, based upon said count table and a plurality of measure equations; and

building an output message for each parcel tracking number based upon said measure number and said corresponding outcome.

11. The method of claim 6, wherein said step of assigning said preferred address to said current parcel and updating said address database comprises:

presenting said set of mined data to an address database administrator via an electronic display device; and

receiving a selection of said preferred address by said administrator via an electronic input device.

12. A computer system for locating a preferred address for each of a plurality of parcels, comprising:

memory; and

one or more processors, wherein;

said memory configured to store a package-level detail database of active shipment records, each active shipment record comprising an active tracking number, an active ship-to address, and an active delivery pattern code;

said memory is configured to store an electronic archive of delivery records, each delivery record comprising a past tracking number, a past ship-to address, a past delivery pattern code, and a stop identifier; and

at least one of said one or more processors is configured to perform the steps of;

receiving address indicia associated with a current parcel;

assigning a mining key to said current parcel, said mining key comprising a parcel tracking number and a current delivery pattern code related to said address indicia;

comparing said mining key to said package-level detail database and said archive by;

(a) retrieving from said archive those select delivery records having a past delivery pattern code that matches said current delivery pattern code, each of said select delivery records having a select past ship-to address; and

(b) retrieving from said package-level detail database those select active shipment records having an active ship-to address that matches any said select past ship-to address in said select delivery records;

prioritizing a set of mined data comprising said select delivery records and said select active shipment records, said set of mined data prioritized in order of the records most closely associated with said mining key, such that a preferred address related to said mining key occurs first, wherein said set of mined data further comprises;

a plurality of ship-to address records having a representative symbol in place of one or more sequence values;

clusters of said ship-to address records having the same stop identifier;

clusters of said ship-to address records having the same delivery pattern code;

a delivery pattern similarity matrix built upon a counting the coincidence of each delivery pattern code and each ship-to address within said set of mined data;

a sum of the overlapping delivery pattern occurrences within said delivery pattern similarity matrix for each pair of ship-to addresses;

a stop identifier similarity matrix built upon a counting the coincidence of each stop identifier and each ship-to address within said set of mined data;

a sum of the overlapping stop occurrences within said stop identifier similarity matrix for each pair of ship-to addresses; and

said set of mined data sorted in order the highest number of overlapping delivery pattern occurrences and the highest number of overlapping stop occurrences; and

an address database administrator assigning said preferred address to said current parcel for delivery.

13. The system of claim 12, wherein at least one of said one or more processors is further configured to perform the step of comparing said mining key to said package-level detail database and said archive by:

(c) retrieving from said archive those additional delivery records having a past delivery pattern code that matches any said current delivery pattern code in said select active shipment records, each of said additional delivery records having an additional past ship-to address;

(d) retrieving from said package-level detail database those additional active shipment records having an active ship-to address that matches any said select additional ship-to address in said additional delivery records; and

repeating steps (c) and (d) in a plurality of iterations until said step of building a set of mined data reaches a limit condition.

14. The system of claim 12, wherein at least one of said one or more processors is further configured to perform the step of associating a unique consignee token related to a single consignee location with said preferred address.

15. The system of claim 12, wherein at least one of said one or more processors is further configured to perform the steps of:

converting said stop identifier similarity matrix into a stop identifier dendrogram;

constructing a stop-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, summing said number of occurrences to form a joined stop node, and by joining the next stop pair of ship-to addresses or joined stop nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next stop pair is zero;

converting said delivery pattern similarity matrix into a delivery pattern dendrogram; and

constructing a pattern-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, using the minimum of said number of occurrences to form a joined pattern node, and by joining the next pattern pair of ship-to addresses or joined pattern nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next pattern pair is zero.

16. A computer system for scoring and maintaining address data for any of a plurality of records in an address database, comprising:

memory; and

one or more processors, wherein;

said memory stores a package-level detail database of active shipment records, each active shipment record comprising an active tracking number, an active ship-to address, and an active delivery pattern code;

said memory stores an electronic archive of delivery records, each delivery record comprising a past tracking number, a past ship-to address, a past delivery pattern code, and a stop identifier; and

at least one of said one or more processors is configured to perform the steps of;

gathering a queue of address data from said detail database and said archive for a period of days;

assigning a score to said address data in said queue;

gathering a consignee staging queue from data in said queue related to a select consignee location;

assigning a mining key to a current parcel selected from said consignee staging queue, said mining key comprising a parcel tracking number and a current delivery pattern code;

comparing said mining key to said package-level detail database and said archive by;

(a) retrieving from said archive those select delivery records having a past delivery pattern code that matches said current delivery pattern code, each of said select delivery records having a select past ship-to address;

(b) retrieving from said package-level detail database those select active shipment records having an active ship-to address that matches any said select past ship-to address in said select delivery records;

prioritizing a set of mined data comprising said select delivery records and said select active shipment records, said set of mined data prioritized in order of the records most closely associated with said mining key, wherein a preferred address related to said mining key occurs first, and said set of mined data further comprises;

a plurality of ship-to address records having a representative symbol in place of one or more sequence values;

clusters of said ship-to address records having the same stop identifier;

clusters of said ship-to address records having the same delivery pattern code;

a delivery pattern similarity matrix built upon a counting the coincidence of each delivery pattern code and each ship-to address within said set of mined data;

a sum of the overlapping delivery pattern occurrences within said delivery pattern similarity matrix for each pair of ship-to addresses;

a stop identifier similarity matrix built upon a counting the coincidence of each stop identifier and each ship-to address within said set of mined data;

a sum of the overlapping stop occurrences within said stop identifier similarity matrix for each pair of ship-to addresses; and

said set of mined data sorted in order the highest number of overlapping delivery pattern occurrences and the highest number of overlapping stop occurrences;

assigning said preferred address to said current parcels; and

updating said address database.

17. The system of claim 16, wherein at least one of said one or more processors is further configured to perform the step of comparing said mining key to said package-level detail database and said archive by:

(c) retrieving from said archive those additional delivery records having a past delivery pattern code that matches any said current delivery pattern code in said select active shipment records, each of said additional delivery records having an additional past ship-to address;

(d) retrieving from said package-level detail database those additional active shipment records having an active ship-to address that matches any said select additional ship-to address in said additional delivery records; and

repeating steps (c) and (d) in a plurality of iterations until said step of building a set of mined data reaches a limit condition.

18. The system of claim 16, wherein at least one of said one or more processors is further configured to perform the step of associating a unique consignee token related to a single consignee location with said preferred address.

19. The system of claim 16, wherein at least one of said one or more processors is further configured to perform the steps of:

converting said stop identifier similarity matrix into a stop identifier dendrogram;

constructing a stop-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, summing said number of occurrences to form a joined stop node, and by joining the next stop pair of ship-to addresses or joined stop nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next stop pair is zero;

converting said delivery pattern similarity matrix into a delivery pattern dendrogram; and

constructing a pattern-joined dendrogram by joining the pair of ship-to addresses having the highest number of overlapping stop occurrences, using the minimum of said number of occurrences to form a joined pattern node, and by joining the next pattern pair of ship-to addresses or joined pattern nodes having the highest number of overlapping stop occurrences, by successive iterations, until said number of overlapping stop occurrences for each said next pattern pair is zero.

20. The system of claim 16, wherein at least one of said one or more processors is further configured to perform the step of assigning a score to said address data in said queue by:

generating a count table for a number of occurrences of each of a plurality of delivery conditions on each day of said period;

calculating for each stop identifier a measure number for each of a plurality of corresponding outcomes, based upon said count table and a plurality of measure equations; and

building an output message for each parcel tracking number based upon said measure number and said corresponding outcome.