# US 11,113,254 B1 · Scaling record linkage via elimination of highly overlapped blocks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,254 B1 - Document ID: US11113254B1 - Status: Granted - Kind: B1 - Application number: 16/587,902 - Filed: 2019-09-30 - Granted: 2021-09-07 - Earliest claimed: 2019-09-30 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Andrew Borthwick; Stephen Michael Ash - Web page: https://patentgrep.com/patent/US11113254B1 ## CPC - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F 16/2379: {Updates performed during online database operations; commit processing} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques for scaling record linkage via elimination of highly overlapped blocks are described. A method for scaling record linkage via elimination of highly overlapped blocks includes identifying a first plurality of blocks based at least on a plurality of records stored in a storage service of a provider network, identifying a plurality of sets of matching blocks from the first plurality of blocks, deleting the plurality of sets of matching blocks except for a first block from each set from the plurality of sets of matching blocks, and iteratively performing dynamic blocking based at least on the first block to generate subsequent pluralities of blocks until the subsequent pluralities of blocks are below a threshold size. ## Claims ### Claim 1 A computer-implemented method comprising: obtaining records from a plurality of data sources based at least on credentials received from a client device; normalizing the records; storing the records in a data lake service in a provider network; determining one or more blocking parameters based at least on the records; identifying a first plurality of blocks based at least on the records stored in the data lake service using the one or more blocking parameters, each block representing a subset of records sharing at least one blocking key; identifying a plurality of matching blocks from the first plurality of blocks; deleting the plurality of matching blocks except for a first block from the plurality of matching blocks; iteratively performing intersection dynamic blocking based at least on the first block to generate a subsequent plurality of blocks until an end condition is detected; performing pairwise matching on a plurality of records represented by the subsequent plurality of blocks; generating a weighted graph of records, wherein each vertex of the graph represents a record from the plurality of records and each edge is weighted based at least on the pairwise matching of the plurality of records; and identifying a plurality of matching records using a transitive closure clustering algorithm applied to the weighted graph of records. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the one or more blocking parameters include at least one of a maximum block size, a first one or more columns of the records to use as blocking keys, identification of level 1 and level 0 keys, a second one or more columns to be used to perform locality sensitive hashing, or normalization rules applied to one or more columns of the records. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the end condition includes at least one of a minimum threshold value has been reached or each block from the subsequent plurality of blocks is associated with a number of records that is less than or equal to a maximum block size parameter. ### Claim 4 A computer-implemented method comprising: identifying a first plurality of blocks based at least on a plurality of records stored in a storage service of a provider network; identifying a plurality of sets of matching blocks from the first plurality of blocks; deleting the plurality of sets of matching blocks except for a first block from each set from the plurality of sets of matching blocks; and iteratively performing dynamic blocking based at least on the first block to generate subsequent pluralities of blocks until the subsequent pluralities of blocks are below a threshold size. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, further comprising: identifying the first block from the plurality of matching blocks based at least on a number of records associated with the first block, wherein the number of records associated with the first block is greater than a number of records associated with any of the other blocks from the plurality of matching blocks. ### Claim 6 (depends on 4) The computer-implemented method of claim 4, wherein dynamic blocking is intersection dynamic blocking. ### Claim 7 (depends on 4) The computer-implemented method of claim 4, wherein identifying a plurality of matching blocks from the plurality of blocks further comprises: determining a similarity metric associated with each pair of blocks from the plurality of blocks, wherein the plurality of matching blocks includes at least two blocks having a similarity metric greater than a threshold value. ### Claim 8 (depends on 7) The computer-implemented method of claim 7, wherein the threshold value decreases with each iteration of dynamic blocking. ### Claim 9 (depends on 8) The computer-implemented method of claim 8, further comprising: detecting an end condition; and outputting a third plurality of blocks generated during a last dynamic blocking. ### Claim 10 (depends on 9) The computer-implemented method of claim 9, wherein the similarity metric is a Jaccard similarity index. ### Claim 11 (depends on 9) The computer-implemented method of claim 9, further comprising: performing pairwise matching on the plurality of records represented by the third plurality of blocks; and generating a weighted graph of records, wherein each vertex of the graph represents a record from the plurality of records and each edge is weighted based at least on the pairwise matching of the plurality of records. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, further comprising: identifying a plurality of matching records using a clustering algorithm applied to the weighted graph of records. ### Claim 13 (depends on 9) The computer-implemented method of claim 9, wherein the end condition includes at least one of a minimum threshold value has been reached or each block from the third plurality of blocks is associated with a number of records that is less than or equal to a maximum block size parameter. ### Claim 14 (depends on 4) The computer-implemented method of claim 4, wherein the maximum block size parameter is based at least on a total number of records in the plurality of records and a value received from a client device. ### Claim 15 (depends on 4) The computer implemented method of claim 4, further comprising: identifying at least one block associated with more than a threshold number of blocking keys after a particular number of iterations of dynamic blocking; for each record in the at least one block, randomly selecting a subset of blocking keys from the blocking keys associated with the at least one block and assigning the subset of blocking keys to the record; identifying a second plurality of blocks based at least on the records in the at least one block that have been assigned a random subset of blocking keys; and iteratively performing dynamic blocking on the second plurality of blocks. ### Claim 16 A system comprising: a storage service implemented by a first one or more electronic devices; and a data lake service implemented by a second one or more electronic devices, the data lake service including instructions that upon execution cause the data lake service to: identify a first plurality of blocks based at least on a plurality of records stored in a storage service of a provider network; identify a plurality of sets of matching blocks from the first plurality of blocks; delete the plurality of sets of matching blocks except for a first block from each set from the plurality of sets of matching blocks; and iteratively perform dynamic blocking based at least on the first block to generate subsequent pluralities of blocks until the subsequent pluralities of blocks are below a threshold size. ### Claim 17 (depends on 16) The system of claim 16, wherein the instructions, when executed, further cause the data lake service to: identify the first block from the plurality of matching blocks based at least on a number of records associated with the first block, wherein the number of records associated with the first block is greater than a number of records associated with any of the other blocks from the plurality of matching blocks. ### Claim 18 (depends on 16) The system of claim 16, wherein dynamic blocking is intersection dynamic blocking. ### Claim 19 (depends on 16) The system of claim 16, wherein to identify a plurality of matching blocks from the plurality of blocks, the instructions, when executed, further cause the data lake service to: determine a similarity metric associated with each pair of blocks from the plurality of blocks, wherein the plurality of matching blocks includes at least two blocks having a similarity metric greater than a threshold value. ### Claim 20 (depends on 19) The system of claim 19, wherein the threshold value decreases with each iteration of dynamic blocking.