CROSS-REFERENCE TO RELATED APPLICATION

This application is a National Stage Application under 35 U.S.C. § 371 and claims the benefit of International Application No. PCT/US2018/030486, filed May 1, 2018. The disclosure of the foregoing application is hereby incorporated by reference in its entirety.

BACKGROUND

This specification relates to computing processes for large-scale similarity calculations.

In many cases it may be desired to determine whether, or how well, an input sample matches multiple stored records. As one example, it may be desired to determine whether a DNA sample matches any of the records stored in a database of DNA records. The database is likely to contain many DNA records (for example hundreds of thousands or even millions of records). In general, it may be desired to retrieve some number n of stored records from the database in response to an input sample. The input sample can be the n records in the database that are determined to be the n closest matches to the input sample. The number n of retrieved records is smaller, typically much smaller, than the overall number of records in the database. The n retrieved records may be arranged in the order of most probable first. Conventionally, such a retrieval process can involve calculating a measure of similarity between the input sample and every record stored in the database, and then identifying the n records with the highest values of calculated similarity measure. The n retrieved records may be re-ordered so as to be arranged with reference to the value of calculated similarity measure. As the number of stored records increases, this process becomes increasingly computationally intensive and time consuming.

SUMMARY

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for obtaining data stored at a storage device using a first processor of an entity correlation system. The data includes information about multiple entities. The first processor generates data arrays using the obtained data. Each data array includes parameter values for multiple entities and is configured for processing at a respective computing cell of a second processor. The system provides the data arrays to the second processor. The second processor is configured to execute a correlation algorithm to concurrently process the data arrays at the respective computing cells. The second processor computes a correlation score based on calculations performed at the cells using the algorithm and the parameter values. The system determines relationships among entities of the data arrays based on the correlation score. The relationships indicate overlapping attributes that exist among subsets of entities.

One aspect of the subject matter described in this specification can be embodied in a computer-implemented method. The method includes, obtaining, by a first processing unit of an entity correlation system, data stored at a storage device, the data comprising information about multiple entities; and generating, at the first processing unit, multiple data arrays using the data obtained from the data storage device. Each data array of the multiple data arrays: i) includes parameter values for multiple entities; and ii) is configured for processing at a respective computing cell of a second processing unit. The method includes providing, at the entity correlation system, at least two data arrays to the second processing unit, the second processing unit being configured to execute a correlation algorithm to concurrently process the at least two data arrays at respective computing cells of the second processing unit; computing, at the second processing unit, a correlation score based on calculations performed at the respective computing cells using the correlation algorithm and the parameter values for the multiple entities; and determining, at the entity correlation system, relationships among entities of the at least two data arrays based on the computed correlation score, wherein the relationships indicate overlapping attributes that exist among at least a subset of the entities.

These and other implementations can each optionally include one or more of the following features. For example, in some implementations, computing the correlation score comprises: selecting the particular correlation algorithm as a similarity algorithm or a conditional probability algorithm; calculating, using the particular correlation algorithm, an intersection between entities of the at least two data arrays and a union between entities of the at least two data arrays; and computing the correlation score based on the intersection and the union. In some implementations, the first processing unit is a central processing unit (CPU) that pre-sorts data obtained from the data storage device to generate the multiple data arrays; the second processing unit is a graphics processing unit (GPU) that performs parallel calculations using the parameter values for entities of the at least two data arrays; and the particular correlation algorithm is a jaccard similarity algorithm, a cosine similarity algorithm, or a conditional probability algorithm.

In some implementations, generating comprises: sorting, based on a sketching algorithm, the data comprising information about the multiple entities; and in response to sorting, generating a sketch representation of the data, each sketch representation corresponding to each of the multiple data arrays. In some implementations, each data array is a sketch representation of the data stored at the storage device; and at least a subset of the multiple data arrays comprises respective data arrays that each have a predetermined number of entities. In some implementations, each sketch representation is sized according to a quantity of computing cells that are included at the second processing unit. In some implementations, providing includes: storing each data array at a memory cache of the second processing unit, wherein the memory cache represents a compact memory of the second processing unit and each data array is sized according to the data capacity of the compact memory.

In some implementations, at least one of the data arrays is configured for access by each of multiple computing cells that are included at the second processing unit. In some implementations, determining relationships among entities includes: determining whether the computed correlation scores exceed a threshold score; and in response to determining that the computed correlation scores exceed the threshold score, generating a listing of entities that are ranked using the correlation scores that exceed the threshold score.

Another aspect of the subject matter described in this specification can be embodied in a computer-implemented method. The method includes receiving first data items at a first processing unit (e.g., a CPU); generating, by the first processing unit and from at least the received first data items, data structures, each data structure representing a respective dataset; storing the data structures in a memory of a second processing unit (e.g., a GPU); receiving, at the first processing unit, a query from a user; processing in parallel, by the second processing unit, the query against two or more of the data structures stored at the second processing unit; and returning the results of the processing from the second processing unit to the first processing unit.

These and other implementations can each optionally include one or more of the following features. For example, in some implementations, the second processing unit includes multiple processing cores, and processing, by the second processing unit, the query against the data structures comprises: processing the query in parallel in each processing core against a respective one of the data structures. In some implementations, processing, by the second processing unit, the query against the data structures stored at the second processing unit includes, for a data structure stored at the second processing unit, determining a respective measure of similarity between the data structure and the query. In some implementations, returning the results of the processing from the second processing unit to the first processing unit comprises returning information identifying the data structures that are n best matches to the query.

In some implementations, the method includes the first processing unit generating a query data structure from the received query and sending the query data structure to the GPU; and wherein processing the query by the second processing unit comprises processing the query data structure against the data structures stored at the second processing unit. In some implementations, the data structures and the query data structure are KMV sketches. In some implementations, processing, by the second processing unit, the query against a data structure stored at the second processing unit comprises determining the union of the query data structure and the stored data structure. In some implementations, processing, by the second processing unit, the query against a data structure stored at the second processing unit comprises determining the intersection of the query data structure and the stored data structure. In some implementations, processing, by the second processing unit, the query against a data structure stored at the second processing unit includes determining the Jaccard similarity between the query data structure and the data structure.

In some implementations, receiving the data items at the first processing unit comprises receiving the data items from a data hosting service; wherein receiving the data items at the first processing unit comprises receiving the data items from a data hosting service; and wherein the method further comprises returning the results of the processing from the first processing unit to the data hosting service. In some implementations, the method further includes: receiving, at the first processing unit, a second query; and processing, by the second processing unit, the second query against the data structures stored at the second processing unit.

In some implementations, the method further includes: receiving second data items at the first processing unit; generating, by the first processing unit and from at least the received second data items, updated data structures, each updated data structure representing a respective dataset; and storing the updated data structures in the memory of the second processing unit. In some implementations, the method further includes: receiving, at the first processing unit, a third query; and processing, by the second processing unit, the third query against the updated data structures stored at the second processing unit.

In some implementations, a processing system including a first processing unit in communication with a second processing unit is configured to carry out a method as defined in any one of the preceding paragraphs of this summary. In some implementations, a computer-readable medium contains stored instructions that, when executed by a processing system including a first processing unit in communication with a second processing unit causes the processing system to carry out a method as defined in any one of the preceding paragraphs of this summary.

An aspect of the present disclosure provides a method comprising: receiving first data items at a first processing unit; generating, by the first processing unit and from at least the received first data items, data structures, each data structure representing a respective dataset; storing the data structures in a memory of a second processing unit; receiving, at the first processing unit, a query from a user; processing in parallel, by the second processing unit, the query against two or more of the data structures stored at the second processing unit; and returning the results of the processing from the second processing unit to the first processing unit. In this aspect the first processing unit may be a CPU (central processing unit) and the second processing unit may be a GPU (graphics processing unit).

Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. A graphics-processing unit can determine correlation scores, computation results, and/or similarity relationships among entities of pre-sorted data arrays with increased speed relative to other data correlation systems. The graphics processor can perform the necessary calculations associated with executing data correlation algorithms (jaccard similarity algorithms) without sorting/pre-sorting data before executing the correlation algorithm. Additionally, the graphics processor can perform the necessary calculations by engaging little to no inter-thread data communications relative to other correlation systems. This is because each computing cell of the graphics processor performs computations on specific sets of data arrays for each query submitted by a user of the system.

For example, using certain low-cost graphics processors, the described techniques can be implemented to achieve more than 20 million similarity calculations within one second using only a single computing cell of a graphics processor. In some implementations, the one second durations for achieving the at least 20 million similarity calculations is more than 10 times faster than the time required for a standard processor (e.g., a CPU) to perform the same amount of calculations. Hence, the described techniques allow a given processor to process larger data arrays in a given time (or to process a data array of given size in a shorter time) and so effectively provide increased computing power for achieving data correlation calculations relative to other data processing apparatus. Also, the described techniques provide a repeatable automated process that involves minimal human intervention and does not require manual execution of pre-sorting data, generating data arrays, or configuring a size of the data arrays. As such, the techniques enable computing systems to quickly perform operations (e.g., a substantial number of similarity calculations) that the systems were previously unable to automatically perform in a fast manner due to challenges with using a k-min-hash or k-minimum value algorithm for sorting data in a graphics processor/GPU computing environment.

The details of one or more embodiments of the subject matter described in this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

