BACKGROUND

The present disclosure relates generally to record linkage, and more specifically, to a computer-implemented method for record linkage of an incoming record to a reference data set. The present disclosure relates further to a related record linkage system for a record linkage of an incoming record to a reference data set, and a computer program product.

Content management remains one of the major topics in enterprise IT organizations. This does not only apply to unstructured data but also to a combination of structured data from traditional databases and unstructured data of any kind. For instance, enterprise AI (artificial intelligence) applications require an integration of data from many data sources, as well as the ability to link and establish relations among data of these data sources. This requirement applies especially to cognitive enterprise data platforms in order to produce meaningful results using as many different data sources as possible.

The field of record linkage (RL) has been extensively researched in the last decades. RL is in charge of joining identical entities (e.g., companies, organizations, products, addresses) in structured records of different data sets independently of the representation. Originally, it was formalized by Fellegi and Sunter in 1969 and the tutorial from Lise Getoor provides an excellent overview of use cases and techniques. RL has been used to link entities from different sets or de-duplicated/canonize entities within a given set. To this extent, several approaches have been envisioned ranging from feature matching or rule-based to machine-learning (ML) based approaches. Feature matching approaches tend to be domain and language specific and therefore algorithms need to be selected, composed and tuned for a given task. On the other hand, ML approaches require the ability of sufficiently large and curated training sets which is often a tough challenge. More recently, distributed representations of words—in particular, word embeddings—and deep learning algorithms have drawn the attention of the research community since it may have reduced the amount of human expertise required to construct an RL system. In addition, promising active learning-based approaches have been proposed.

Typically, RL is performed in batch mode to link a large number of entities between two or more databases or other kinds of data sources. A challenge in enterprise AI applications is the ever-increasing amount of unstructured data like news, blocks, social media content, transcripts, etc., and the ever-increasing need of its integration with enterprise data typically stored in a structured form in, e.g., relational databases. As a consequence, RL has to be performed between structured records and unstructured documents. This large amount of data may flow in streams for rapid consumption and analysis by enterprise systems; therefore, RL needs to be executed “on-the-fly”, i.e., in real-time. The entities to be linked in unstructured data may be identified as mentioned by a Named Entity Recognition (NER) module which may be part of a natural language processing (NLP) pipeline.

RL includes scoring input entries against a reference data set (RDS) in order to find the best matching RDS entry according to a certain set of criteria. Considering that the RDS can be potentially very large—i.e., in the order of hundreds of millions of entries—this scoring may become quickly prohibitive in terms of computational complexity and resources. To alleviate this, a classical approach consists of decomposing RDS into blocks comprising “similar” entries. The input entry may be associated with a given block and the scoring (i.e., to find the best match) may be performed only against the RDS entries belonging to that block. Typically, these blocks—and therefore the association in the input entry with a block—may be identified by means of a hashing function computed on one field of the entries. One may define as blocking key the result of the application of the hashing function, also called blocking function.

In the literature, one may also find examples using a blocking function for a single criterion. Now, blocking functions can be applied to multiple fields to obtain multiple blocking dimensions. The set of candidate RDS entries to be scored may then be computed as the intersection of the blocks corresponding to each blocking dimension. This operation, however, is computational-wise expensive, in particular, in the order of the sum of the cardinality of each block and therefore not compatible with real-time operations.

However, the known RL technologies are not well-suited to overcome the resource hunger for ever-increasing amounts of data. Thus, it is an objective of the proposed concept to address the field of record linkage in a way to make it applicable for large amounts of data and real-time environments.

SUMMARY

According to one aspect of the present invention, a computer-implemented method for record linkage of an incoming record to a reference data set may be provided. The method may comprise providing a reference data set comprising a plurality of records. Each of the reference data set's record may comprise a plurality of attributes.

The method may further comprise assigning each of the plurality of records an initial surrogate identifier value, assigning a plurality of block identifiers to each of the records by applying a locality sensitive hashing function to a predefined attribute of the records, resulting in the plurality of the block identifiers, and determining a final surrogate identifier value to each of the records assigned to one of the blocks such that the final surrogate identifier values in each block are uniformly distributed.

According to another aspect of the present invention, a related record linkage system for a record linkage of an incoming record to a reference data set may be provided. The system may comprise a reference data set comprising a plurality of records. Each of the records may comprise a plurality of attributes.

The method may also comprise a first assignment unit adapted for assigning each of the plurality of records an initial surrogate identifier value, a blocking function module adapted for assigning a plurality of block identifiers to each of the records by applying a locality sensitive hashing function to a predefined attribute of the records, resulting in the plurality of the block identifiers, and a second assignment unit adapted for assignment of a final surrogate identifier value to each of the records assigned to one of the blocks, such that the final surrogate identifier values in each block are uniformly distributed.

The proposed computer-implemented method for record linkage of an incoming record to a reference data set may offer multiple advantages and technical effects:

The proposed concept may be applied to a plurality of different tasks in the field of record linkage. May it be that entries of two databases should be related or that streaming incoming data from, e.g., a news feed, social media and/or other online sources should be related to records of an existing reference data set, i.e., entries of a database. The proposed concept may allow to look up whether an entity is referenced by a block with a runtime complexity in the order of 1. This may—in contrast to traditional RL approaches—allow also incoming streaming data to be linked to very large reference data sets in the order of hundreds of millions of entries at high speed. In contrast, traditional records linkage and related scoring approaches for finding matching records may quickly become prohibitive in terms of a required time for its competition and the related complexity. It would simply take too long to relate one incoming new record to any of the existing records in a reference data set, i.e., an existing database with records the new incoming record should be related to.

This problem may now elegantly be solved because the reference data set in question is not taken as provided, but may be prepared in a preprocessing step to deal with high-speed RL. The preprocessing may enable a much quicker relationship building of newly received records to already existing records in the reference data set. It may no longer be required to compare the newly received record with each and every record in the existing database. Instead, “shortcuts” in the form of blocks that relate to groups of records in the reference data set may be used such that a two-step approach—determining firstly a potential block and then a record within the block—is way more efficient than any traditional approach.

An instrumental concept is the determination of the uniform distribution of final surrogate identifier values of records within each determined block of records. The blocking function, i.e., the locality sensitive hashing function to determine a block identifier based on the predefined attribute may build the second foundation concept of the proposed inventive method and the related system. Basically, the preprocessing step aims at aligning the records—i.e., entries—such that they can be looked up in constant time by linear interpolation of locations/positions of their identifiers.

Additionally, also the preprocessing is computation-wise not so resource-hungry as one would expect. Also here, a multi-step approach is followed: (a) assign preliminary or initial surrogate identifier values to records in the reference data set and (b) apply a locality sensitive hashing function to a predefined attribute of the records and the reference data set. Last but not least, (c) new, final surrogate identifier values are assigned to records in a way that they are uniformly distributed within each block.

In practical implementations, it may turn out that there are many blocks having only one or two entries. Because two entries in the block are by definition always uniformly distributed—which also applies to blocks with only one entity inside—the reshuffling of those identifiers does not have to be performed for each and every determined block. Also this reduces the computational effort during the preprocessing.

Furthermore, the proposed concept is not limited to only one attribute but may also be applied to a plurality of attributes. Generally, each attribute—or criterion—may be considered separately. Thus, for a second attribute, a second block structure may be managed. In general, there are not any cross dependencies between the blocks relating to the first attributes in the block relating to the second attribute. If computationally possible, however, the two blocks may use the same surrogate identifiers to refer to the records in the RDS.

However, it may also be possible to combine attributes during the block building process. This may be achieved by applying the locality sensitive hashing function to a combination of attributes—e.g., name/first name or company name/location or street name/number or song name/artist. Any other combination should be possible. Such a combination of attributes is also not limited to just two attributes. Any plurality of attributes may be used.

Hence, the proposed concept may with only little effort be expanded to multiple attributes by applying the locality sensitive hashing function to a predefined set of attributes of the records resulting in the plurality of the block identifiers. This may even be done in a single logical step and loop process over all records in the reference data set. Thus, the additional computational cost would be pretty limited.

In the next section, a generalized more theoretical model of the proposed concept may be described:

An RDS with |E| entries may be assumed. Each entry, representing an entity ei, i∈[0, |E|−1] has H attributes. For example, if the entities are companies, the attributes can be street address, city, country, industry, number of employees, etc.

An RL problem with C<H criteria may be considered. A blocking key bc,ei, c∈[0, C−1], i∈[0, |E|−1] is the result of a blocking function Bc, h∈[0, C−1] applied on the attribute h of entity ei. Entities having the same blocking key—i.e., the same value is returned by the locality sensitive hashing function—belong to the same block. Therefore, for a given dimension h, entities are gathered in blocks noted Bme, where m is in the range of numbers that may be returned by the locality sensitive hashing function. Each Bmcis associated with a blocking key bmc. When processing an input (i.e., an entry to be linked) we need to identify the set of candidate RDS entities.

To this end, one first computes the set of blocking keys {bc,I}, c∈[0, C−1] related to the input I. Given these keys one defines the candidate RDS entities set as CI=∩c∈[0,C−1]Bc,I, Bc,Ibeing the set of RDS entries having bc,Ihas blocking key—in other words, Bc,I=Bmc⇐⇒bc,I=bmc. It may be noted that this concept is depicted inFIG.2for two attribute (see below).

Thus, the here proposed concept may add a preprocessing step to improve the blocking key data structure in order to optimize the search computational complexity. The goal is to compute the intersection between the sets of the various dimensions with a complexity of O(minc∈[0,C−1]|B0|), i.e., linear with the size of the smallest set. In an embodiment, the preprocessing step aims at aligning the entities such that they can be looked up in constant time by linear interpolation of their identifiers.

In the following, additional embodiments of the inventive concept—applicable to the method, as well as the related system—will be described.

According to one advantageous embodiment, the method may also comprise sorting the block identifiers by its cardinality, i.e., by the number of records comprised in the block. The determining of the final surrogate identifier value (FS-ID) may comprise performing for each block, starting with the largest block, i.e., the one having the highest number of records, i.e., highest cardinality:
FS-ID=offset+i*gap, wherein
FS-ID=final surrogate identifier value,
gap=E/B and offset=gap/2, wherein
E=the total number of records in the reference data set,
B=number of records in the given block, and
i=the number of a position of an initial surrogate identifier value in a given block, such that 0=i<B.

The computation way require only simple mathematical operations like add, multiply and divide, which results may be determined without high computational costs. Thus, the preprocessing may be performed advantageously with just little effort.

According to a preferred embodiment of the method, in case a final surrogate identifier value may be determined which value has already been determined during the determining the final surrogate identifiers of a previous block—thus, if a conflict case may happen—a next closest final surrogate identifier value may be chosen for the respective record, provided that the final surrogate identifier values in the respective block continue to be uniformly distributed. Thus, conflicts in values of surrogate identifiers and the condition of a uniform distribution of the surrogate identifiers in each of the blocks may be addressed simultaneously.

According to one additional embodiment, the method may also comprise testing whether a next closest available value for the final surrogate identifier may provide a uniform distribution for a given block B according to the following formula:
pos(id)=round[(B−1)*((id−B(0)/B(B−1)−B(0))],
∀i∈[0,B−1]:B(i)==B(pos(B(i))),  (1)
wherein
id=chosen next closest final surrogate identifier value, i.e., an integer number that should be tested for its existence in the respective block,
pos=position of the value id in a given block, given that the positions within each block may be treated like an index (integer value) of locations in the block; i.e., if a given block may have five surrogate identifiers, they may take the positions, e.g., 1 to 5 (or, 0 to 4);
B=number of records in the given block, and
B(x)=value of identifier in array B(x) at position x.

Thus, if choosing a next closest final surrogate identifier value and finding the same value at pos(id), this counts as uniform distribution. Otherwise, another next identifier value would be used and the test needs to be repeated until a next closest FS_ID without any conflict would be found.

As an example, it may be that there are three blocks with surrogate identifiers B1=[200, 300, 400, 500], B2=[98,196, 294] and B3=[200, 294, 400]. It may also be assumed that one needs to look up whether 294 is comprised in B3. The position pos(294) can be identified by 2*((294-200)/(400-200))=0,94≈1, according to the formula above.

According to a useful embodiment, the method may also comprise assigning the determined final surrogate identifier value also to records in subsequent blocks, i.e., those having a smaller cardinality—which have the same initial surrogate identifier value as the record having been assigned the final surrogate identifier value. Thus, consistency—in particular down-stream consistency—may be guaranteed such that a surrogate identifier always points to only one record.

According to one advantageous embodiment of the method, the blocks with assigned records may be organized as one or more arrays of surrogate identifiers using the surrogate identifier as index in the reference data set. Thus, not the entries, i.e., records, of the data set need to be rearranged, which would mean a significant computations effort, but only the initial and/or final surrogate identifier value may be rearranged in the array. However, it may also be required to exchange a surrogate identifier directly linked (or being part of) to the record in the reference data set in order to keep consistency among a surrogate identifier and the related record.

According to one optional embodiment of the method, the predefined attribute of the records may be a combination of at least two attributes, e.g., first name/last name, company name/location, etc. This may be one option to handle a combination of attributes, in particular those attributes having a logical dependency. In this case, the location sensitive hashing function may be applied to the combination of attributes. The alternative case of independent attributes has already been discussed above. This way, a plurality of attributes may be combined.

Hence, according to one permissive embodiment of the method, the steps of assigning a plurality of block identifiers may comprise determining a final surrogate identifier value for a second predefined attribute. In this case, there may be no logical dependency between the attributes. Thus, a step of assigning initial surrogate identifier values and final surrogate identifier values may be performed for a second attribute, including the conflict checks, as discussed above.

According to one enhanced embodiment, the method may also comprise receiving a new record comprising the predefined attribute—e.g., a social media comment—applying the locality sensitive hashing function to the predefined attribute of the newly received record resulting in an access block number, and accessing the block having the resulting access block number. Then, a scoring function may be used to determine the best matching record identifiable via the final surrogate identifier value in the reference data set. Additionally, in case the incoming record is unstructured or semi-structured, a filtering of the received records by a natural language processing unit and attribute identification unit may become active before the here proposed record linkage process may be performed.

According to one further enhanced embodiment, the method may also comprise assigning a plurality of second block identifiers to each of the records by applying a second locality sensitive hashing function to a second predefined attribute of the records, resulting in the plurality of the second block identifiers. This embodiment may also comprise determining final surrogate identifiers to each of the records assigned to one of the blocks such that the final surrogate identifier values in each block are uniformly distributed.—In one embodiment, the locality sensitive hashing function used for the first attribute and the second locality sensitive hashing function may be the same or different.

According to an even more enhanced embodiment, the method may also comprise receiving a new record comprising the predefined attribute and the second predefined attribute, applying the second location sensitive hashing function to the predefined attribute resulting in an access block number, applying the second location sensitive hashing function to the second predefined attribute resulting in a second access block number, and joining the block having assigned the (first) access block number and the second access block number. This may be performed by looking up each surrogate identifier value—in particular, preferably of the smaller of the two blocks in the larger of the two blocks—at the following pre-determined position: pos(id)=round[(B−1)*((id−B(0)/B(B−1)−B(0))].

Thus, the case of two independent attributes may advantageously comprise a merger of the identified blocks in order to determine, by a scoring function, to which records in the joined block an incoming record would best fit to. Of course, this concept may be expanded to a plurality of attributes.

It should also be noted that if two or more sets of criteria are used, the intersection of the blocks obtained for each criterion may be computed with the run-time complexity in the order of the cardinality of the smallest of the data sets. Thus, if compared to traditional approaches a significant compute resource saving.

Furthermore, embodiments may take the form of a related computer program product, accessible from a computer-usable or computer-readable medium providing program code for use, by, or in connection, with a computer or any instruction execution system. For the purpose of this description, a computer-usable or computer-readable medium may be any apparatus that may contain means for storing, communicating, propagating or transporting the program for use, by, or in connection, with the instruction execution system, apparatus, or device.

