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

• US 8,386,516 B2
• Filed: 03/14/2011
• Issued: 02/26/2013
• 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): Badawi, Sherief
• Application Number:
  US13/047,565
• Publication Number:
  US 20110208725A1
• Time in Patent Office: 715 Days
• Field of Search: 707/776, 707/756, 707/603
• US Class Current: 707/776
• 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 method of mining address data to locate a preferred address for a parcel, comprising the steps of:

maintaining one or more databases comprising a plurality of active shipment records and a plurality of delivery records;

receiving a current parcel bearing address indicia;

determining a preferred address corresponding to said address indicia based, at least in part, on said active shipment records and said delivery records; and

assigning said preferred address to said current parcel;

wherein said one or more databases comprise a package-level detail database and a delivery records archive;

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

wherein said delivery records archive comprises said plurality 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

wherein said step of determining a preferred address corresponding to said address indicia comprises;

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 delivery records archive by;

(a) retrieving from said delivery records archive a first set of delivery records, each of said first set of delivery records having a past delivery pattern code that matches said current delivery pattern code; and

(b) retrieving from said package-level detail database a first set of active shipment records, each of said first set of active shipment records having an active ship-to address that matches any past ship-to address in said first set of delivery records;

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

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.

2. The method of claim 1, wherein said step of comparing said mining key to said package-level detail database and said delivery records archive further comprises:

(c) retrieving from said delivery records archive a second set of delivery records having past delivery pattern codes that match any said current delivery pattern code in said first set of active shipment records;

(d) retrieving from said package-level detail database a second set of active shipment records having active ship-to addresses that match any ship-to address in said second set of delivery records; and

(e) 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 certain consignee location;

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

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

4. The method of claim 1, wherein said step of prioritizing said set of mined data comprises:

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;

clustering together delivery records in said set of mined data having the same stop identifier and the same ship-to address; and

clustering together delivery records in said set of mined data having the same delivery pattern code and the same ship-to address.

5. The method of claim 4, wherein said step of prioritizing said set of mined data further comprises:

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;

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

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;

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

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

6. The method of claim 5, wherein said step of prioritizing said set of mined data further comprises:

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.

7. 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; and

receiving a selection of said preferred address by said administrator.

8. A method of maintaining address data for a plurality of records in one or more address databases, comprising:

maintaining one or more address databases comprising a plurality of active shipment records and a plurality of delivery records;

determining a preferred address for a select active shipment record or select delivery record based, at least in part, on said active shipment records and said delivery records; and

updating said one or more address databases to associate said preferred address with said select active shipment record or said select delivery record;

wherein said one or more databases comprise a package-level detail database and a delivery records archive;

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

wherein said delivery records archive comprises said plurality 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

wherein said step of determining a preferred address comprises;

gathering address data from said package-level detail database and said delivery records archive into a queue for a period of days;

scoring said address data in said queue;

building a consignee staging queue for storing data in said queue related to a certain 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 delivery records archive by;

(a) retrieving from said delivery records archive a first set of delivery records having past delivery pattern codes that match said current delivery pattern code;

(b) retrieving from said package-level detail database a first set of active shipment records having active ship-to addresses that match any past ship-to address in said first set of delivery records;

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

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.

9. The method of claim 8, wherein said step of comparing further comprises:

(c) retrieving from said delivery records archive a second set of delivery records having past delivery pattern codes that match any current delivery pattern code in said first set of active shipment records;

(d) retrieving from said package-level detail database a second set of active shipment records having active ship-to addresses that match any ship-to address in said second set of delivery records; and

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

10. The method of claim 8, further comprising:

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

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

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

11. The method of claim 8, wherein said step of prioritizing said set of mined data comprises:

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;

clustering together delivery records in said set of mined data having the same stop identifier and the same ship-to address; and

clustering together delivery records in said set of mined data having the same delivery pattern code and the same ship-to address.

12. The method of claim 11, wherein said step of prioritizing said set of mined data further comprises:

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;

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

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;

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

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

13. The method of claim 12, wherein said step of prioritizing said set of mined data further comprises:

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.

14. The method of claim 8, wherein said step of scoring said address data in said queue comprises:

generating a count table for the 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.

15. The method of claim 8, 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; and

receiving a selection of said preferred address by said administrator.

16. A system for locating a preferred address for a parcel, said system comprising:

one or more processors; and

one or more memory storage areas configured for storing one or more databases comprising a plurality of active shipment records and a plurality of delivery records;

wherein said system is configured to;

determine a preferred address corresponding to address indicia of a current parcel based, at least in part, on said active shipment records and said delivery records; and

assign said preferred address to said current parcel;

wherein said one or more databases comprises a package level detail database and a delivery records archive;

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

wherein said delivery records archive comprising a plurality of delivery records, said delivery records comprising a past tracking number, a past ship-to address, a past delivery pattern code, and a stop identifier; and

wherein, in order to determine said preferred address, said system is configured to;

(a) assign a mining key to a current parcel bearing address indicia, said mining key comprising a parcel tracking number and a current delivery pattern code related to said address indicia;

(b) retrieve from said delivery records archive a first set of delivery records having past delivery pattern codes that match said current delivery pattern code;

(c) retrieve from said package-level detail database a first set of active shipment records having active ship-to addresses that match any past ship-to address in said first set of delivery records; and

(d) generate a set of mined data comprising said first set of delivery records and said first set of 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.

17. The system of claim 16, wherein said system is further configured to:

(e) retrieve from said delivery records archive a second set of delivery records having past delivery pattern codes that match any active delivery pattern code in said first set of active shipment records;

(f) retrieve from said package-level detail database a second set of active shipment records having active ship-to addresses that match any past ship-to address in said second set of delivery records; and

(g) repeating steps (e) and (f) 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 said system is further configured to assign a unique consignee token related to a certain consignee location associated with said preferred address.

19. The system of claim 16, wherein said system is further configured to:

replace one or more sequence values of a plurality of delivery records in said set of mined data with one or more representative symbols;

identify clusters of said plurality of delivery records having the same stop identifier;

identify clusters of said plurality of delivery records having the same delivery pattern code; and

include said identified clusters of delivery records in said set of mined data.

20. The system of claim 19, wherein said system is further configured to:

count the coincidences of each delivery pattern code and each ship-to address within said set of mined data;

generate a delivery pattern similarity matrix comprising said coincidences of each delivery pattern code and each ship-to address;

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

count the coincidences of each stop identifier and each ship-to address within said set of mined data;

generate a stop identifier similarity matrix comprising said coincidences of each stop identifier and each ship-to address;

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

sort said set of mined data according to the number of overlapping delivery pattern occurrences and the number of overlapping stop occurrences.

21. The system of claim 20, wherein said system is further configured to:

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

generate 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;

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

generate 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.

22. A system for maintaining address data for a plurality of records in one or more address databases, the system comprising:

one or more processors; and

one or more memory storage areas configured for storing one or more address databases comprising a plurality of active shipment records and a plurality of delivery records;

wherein the system is configured to;

determine a preferred address for a select active shipment record or a select delivery record based, at least in part, on said active shipment records and said delivery records; and

assign said preferred address to said parcel and update said one or more address databases to associate said preferred address with the select active shipment record or select delivery record;

wherein said one or more databases comprise a package level detail database and a delivery records archive;

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

wherein said delivery records archive comprising a plurality 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

wherein, in order to determine said preferred address, said system is configured to;

queue address data gathered from said package-level detail database and said delivery records archive for a period of days;

assign a score to said address data in said queue;

store data related to a certain consignee location in a consignee stating queue;

assign 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;

compare said mining key to said package-level detail database and said delivery records archive by;

(a) retrieving from said delivery records archive a first set of delivery records having past delivery pattern codes that match said current delivery pattern code; and

(b) retrieving from said package-level detail database a first set of active shipment records having active ship-to addresses that match any past ship-to address in said first set of delivery records; and

generate a set of mined data comprising said first set of delivery records and said first set of 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.

23. The system of claim 22, wherein said comparing step further comprises:

(c) retrieving from said delivery records archive a second set of delivery records having past delivery pattern codes that match any current delivery pattern code in said first set of active shipment records;

(d) retrieving from said package-level detail database a second set of active shipment records having active ship-to addresses that match any additional ship-to address in said second set of delivery records; and

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

24. The system of claim 22, wherein said system is further configured to assign a unique consignee token to a certain consignee location associated with said preferred address.

25. The system of claim 22, 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 delivery records having the same stop identifier and the same ship-to address; and

clusters of delivery records having the same delivery pattern code and ship-to address.

26. The system of claim 25, wherein said system is further configured to:

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

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

generate a stop identifier similarity matrix by counting the coincidences of each stop identifier and each ship-to address within said set of mined data;

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

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

27. The system of claim 26, wherein said system is further configured to:

generate a stop identifier dendrogram by converting said stop identifier similarity matrix;

generate 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;

generate a delivery pattern dendrogram by converting said delivery pattern similarity matrix; and

generate 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.

28. The system of claim 22, wherein said system is configured to assign a score to said address data in said queue by:

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

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

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