TECHNOLOGICAL FIELD

An example embodiment relates generally to a method, apparatus and computer program product for indexing a plurality of records based upon the similarity of the records and, more particularly, to indexing a plurality of multi-dimensional records.

BACKGROUND

A variety of applications require that records be identified from among a plurality of records, such as a database of records, that match or are otherwise similar. In instances in which the number of records is limited, a full pair wise similarity comparison may be made of the records in order to identify those records that match or are otherwise similar. However, as the number of records that are to be reviewed increases, a full pair wise similarity comparison becomes increasingly computationally expensive and, in some instances, potentially even prohibitive or infeasible.

Other typical techniques for identifying records that match or are otherwise similar are designed to identify this single best matching record or a small set of the records that are the best matches. While these techniques may provide relatively accurate results, the results may sometimes not be as complete as would be desired, such as by failing to identify additional records that are similar, but slightly less similar than the records that were identified to be the single best matching record or to be included in the small set of the records. While accuracy of the results is a consideration, the completeness of the results is also a consideration since at least some application prefer a larger set of results from a matching analysis, even if the accuracy of at least some of the results is somewhat less.

In an effort to reduce the computational complexity associated with these matching techniques, records may be indexed according to a key. Once indexed, records can be compared for purposes of identifying records that match or are otherwise sufficiently similar in a manner that consumes fewer computational resources and is more efficient. However, the indexing of the records results in the loss of at least some information, thereby potentially reducing the accuracy of the results that are generated.

In some applications, the records that are reviewed have multiple dimensions with the similarity of the records being considered across the plurality of dimensions. Even with multi-dimensional records, some techniques for identifying records that match or are otherwise substantially similar identify records that match or are substantially similar based upon an analysis along a single dimension. As the records that are identified to match or otherwise be substantially similar in the single dimension may not necessarily match or be substantially similar along one or more of the other dimensions, the results of such a single dimensional matching analysis may be less accurate than is desired and, in some instances, may require further analysis of the records to determine their similarity along one or more of the other dimensions, thereby decreasing the efficiency with which multi-dimensional records that match or are otherwise substantially similar are identified.

BRIEF SUMMARY

A method, apparatus and computer program product are provided in order to index a plurality of records based upon the similarity of the records along a plurality of dimensions. The method, apparatus and computer program product of an example embodiment are configured to index the records in a manner that takes into account the plurality of dimensions, thereby permitting records that match or are otherwise similar to be efficiently identified. Additionally, the method, apparatus and computer program product of an example embodiment are configured to index the multi-dimensional records in such a manner that the similarity of the records is determined over the plurality of dimensions such that the results of the analysis is complete subject to reasonable accuracy by identifying records that are similar along at least one dimension without identifying an undesirable number of dissimilar records.

In an example embodiment, a method is provided for indexing a plurality of records based upon the similarity of the records along a plurality of dimensions. The method includes constructing one or more blocking keys for each of the plurality of records. A respective blocking key represents a string representation that combines components derived from attributes of a respective record, such as by concatenating components derived from attributes of the respective record. For the respective blocking key, the method determines a locality sensitive hash based upon the string representation of the respective blocking key. The method also includes indexing the respective record based upon the locality sensitive hash.

The method of an example embodiment also includes transforming, for the respective blocking key of a respective record, the string representation of the respective blocking key to a numeric vector. In this example embodiment, the method determines the locality sensitive hash based upon the numeric vector. The method of an example embodiment also includes providing, based on the indexing, batches of the plurality of records that, within a respective batch, are similar along at least one dimension to facilitate labeling of the plurality of records in advance of training a machine-learned classification model utilizing the plurality of records, as labeled.

The method of an example embodiment indexes the respective record by associating the respective record with each of a plurality of sub-indices based upon the locality sensitive hash. In this example embodiment, the number of sub-indices corresponds to the number of blocking keys for the respective record. In this regard, the number of sub-indices may equal the number of blocking keys for the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a different string representation that combines components derived from attributes of the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a string representation that combines components that are differently derived from attributes of the respective record or components derived from different attributes of the respective record. The respective blocking key of an example embodiment is based upon attributes representative of the plurality of dimensions of the respective record.

In another example embodiment, an apparatus is provided that is configured to index a plurality of records based upon a similarity of the records along a plurality of dimensions. The apparatus includes processing circuitry and at least one memory including computer program code instructions. The computer program code instructions are configured to, when executed by the processing circuitry, cause the apparatus to construct one or more blocking keys for each of the plurality of records. A respective blocking key represents a string representation that combines components derived from attributes of a respective record, such as by concatenating components derived from attributes of the respective record. The computer program code instructions are also configured to, when executed by the processing circuitry, cause the apparatus to determine, for the respective blocking key, a locality sensitive hash based upon the string representation of the respective blocking key. The computer program code instructions are further configured to, when executed by the processing circuitry, cause the apparatus to index the respective record based upon the locality sensitive hash.

The computer program code instructions are further configured to, when executed by the processing circuitry, cause the apparatus of an example embodiment to transform, for the respective blocking key of a respective record, the string representation of the respective blocking key to a numeric vector. In this example embodiment, the computer program code instructions are configured to, when executed by the processing circuitry, cause the apparatus to determine the locality sensitive hash based upon the numeric vector. In an example embodiment, the computer program code instructions are further configured to, when executed by the processing circuitry, cause the apparatus to provide, based on the indexing, batches of the plurality of records that, within a respective batch, are similar along at least one dimension to facilitate labeling of the plurality of records in advance of training a machine-learned classification model utilizing the plurality of records, as labeled.

The computer program code instructions are configured to, when executed by the processing circuitry, cause the apparatus of an example embodiment to index the respective record by associating the respective record with each of a plurality of sub-indices based upon the locality sensitive hash. In this example embodiment, the number of sub-indices corresponds to a number of blocking keys for the respective record. For example, the number of sub-indices may equal the number of blocking keys for the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a string representation that combines components that are differently derived from attributes of the respective record or components derived from different attributes of the respective record. The respective blocking key of an example embodiment is based upon attributes representative of the plurality of dimensions of the respective record.

In a further example embodiment, a computer program product is provided that is configured to index a plurality of records based upon a similarity of the records along a plurality of dimensions. The computer program product includes at least one non-transitory computer-readable storage medium having computer-executable program code instructions stored therein with the computer-executable program code instructions including program code instructions configured, upon execution, to construct one or more blocking keys for each of the plurality of records. A respective blocking key represents a string representation that combines components derived from attributes of a respective record, such as by concatenating components derived from attributes of the respective record. The computer-executable program code instructions also include program code instructions configured, upon execution, to determine, for the respective blocking key, a locality sensitive hash based upon the string representation of the respective blocking key. The computer-executable program code instructions further include program code instructions configured, upon execution, to index the respective record based upon the locality sensitive hash.

The computer-executable program code instructions of an example embodiment also include program code instructions configured, upon execution, to transform, for the respective blocking key of a respective record, the string representation of the respective blocking key to a numeric vector. In this example embodiment, the program code instructions configured to determine the locality sensitive hash include program code instructions configured to determine the locality sensitive hash based upon the numeric vector. In an example embodiment, the computer-executable program code instructions also include program code instructions configured, upon execution, to provide, based on the indexing, batches of the plurality of records that, within a respective batch, are similar along at least one dimension to facilitate labeling of the plurality of records in advance of training a machine-learned classification model utilizing the plurality of records, as labeled.

The program code instructions configured to index the respective record may include program code instruction configured to associate the respective record with each of a plurality of sub-indices based upon the locality sensitive hash. In this example embodiment, the number of sub-indices corresponds to the number of blocking keys for the respective record. For example, the number of sub-indices may equal the number of blocking keys for the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a different string representation that combines components derived from attributes of the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a string representation that combines components that are differently derived from attributes of the respective record or components derived from different attributes of the respective record. The respective blocking key of an example embodiment is based upon attributes representative of the plurality of the dimensions of the respective record.

In yet another example embodiment, an apparatus is provided for indexing a plurality of records based upon the similarity of the records along a plurality of dimensions. The apparatus includes means for constructing one or more blocking keys for each of the plurality of records. A respective blocking key represents a string representation that combines components derived from attributes of a respective record, such as by concatenating components derived from attributes of the respective record. The apparatus also includes means for determining, for the respective blocking key, a locality sensitive hash based upon the string representation of the respective blocking key. The apparatus further includes means for indexing the respective record based upon the locality sensitive hash.

The apparatus of an example embodiment also includes means for transforming, for the respective blocking key of a respective record, the string representation of the respective blocking key to a numeric vector. In this example embodiment, the means for determining the locality sensitive hash includes means for determining the locality sensitive hash based upon the numeric vector. The apparatus of an example embodiment also includes means for providing, based on the indexing, batches of the plurality of records that, within a respective batch, are similar along at least one dimension to facilitate labeling of the plurality of records in advance of training a machine-learned classification model utilizing the plurality of records, as labeled.

The means for indexing the respective record may include means for associating the respective record with each of a plurality of sub-indices based upon the locality sensitive hash. In this example embodiment, the number of sub-indices corresponds to a number of blocking keys for the respective record. For example, the number of sub-indices may equal the number of blocking keys for the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a different string representation that combines components derived from attributes of the respective record. In an example embodiment, each blocking key of the one or more blocking keys represents a string representation that combines components that are differently derived from attributes of the respective record or components derived from different attributes of the respective record. The respective blocking key of an example embodiment is based upon attributes representative of the plurality of dimensions of the respective record.

