Patent ID: 12197438

The Figures described above are a representative set and are not exhaustive with respect to embodying the invention.

DESCRIPTION

Disclosed are a system, method, and article of matching platform for entities. The following description is presented to enable a person of ordinary skill in the art to make and use the various embodiments. Descriptions of specific devices, techniques, and applications are provided only as examples. Various modifications to the examples described herein can be readily apparent to those of ordinary skill in the art, and the general principles defined herein may be applied to other examples and applications without departing from the spirit and scope of the various embodiments.

Reference throughout this specification to “one embodiment,” “an embodiment,” “one example,” or similar language means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment, or according to some embodiments. Thus, appearances of the phrases “in one embodiment,” “in an embodiment,” and similar language throughout this specification may, but do not necessarily, all refer to the same embodiment.

Furthermore, the described features, structures, or characteristics of the invention may be combined in any suitable manner in one or more embodiments. In the following description, numerous specific details are provided, such as examples of programming, software modules, user selections, network transactions, database queries, database structures, hardware modules, hardware circuits, hardware chips, etc., to provide a thorough understanding of embodiments of the invention. One skilled in the relevant art can recognize, however, that the invention may be practiced without one or more of the specific details, or with other methods, components, materials, and so forth. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention.

The schematic flow chart diagrams included herein are generally set forth as logical flow chart diagrams. As such, the depicted order and labeled steps are indicative of one embodiment of the presented method. Other steps and methods may be conceived that are equivalent in function, logic, or effect to one or more steps, or portions thereof, of the illustrated method. Additionally, the format and symbols employed are provided to explain the logical steps of the method and are understood not to limit the scope of the method. Although various arrow types and line types may be employed in the flow chart diagrams, they are understood not to limit the scope of the corresponding method. Indeed, some arrows or other connectors may be used to indicate only the logical flow of the method. For instance, an arrow may indicate a waiting or monitoring period of unspecified duration between enumerated steps of the depicted method. Additionally, the order in which a particular method occurs may or may not strictly adhere to the order of the corresponding steps shown.

Definitions

Example definitions for some embodiments are now provided.

Application programming interface (API) can be an application specific computing interface to allow third parties to extend the functionality of a software application.

Bidirectional Encoder Representations from Transformers (BERT) is a transformer-based machine learning technique for natural language processing (NLP) pre-training.

Cloud computing can be the on-demand availability of computer system resources, especially data storage and computing power, without direct active management by the end user.

Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance.

Data manipulation language (DML) is a family of computer languages used by computer programs or database users to retrieve, insert, delete, and update data in a database.

Entity refers to a real-world artifact such as, for example, a person, company, product, parts, etc. For example, a person can take different forms such as: customer, patient, user, etc. Similarly, a company can be a business entity that can be, for example, a merchant, supplier, provider of a service, etc.

Entity Query Language (EQL) is a storage-independent query language that follows similar syntax to SQL. EQL enables users to describe operations that can be performed on an entity (e.g., customers). These operations include, for example, aggregations, union, intersections, and best-value calculations. EQL is parsed and translated into code. The code is then executed on the entity data to calculate the results. For example, a customer of a retail company can be defined by name, addresses (one or more), emails, telephone numbers, shopping locations, web site cookies, website activities, and the like.

High-throughput linking can use a software module that creates clusters of records that correspond to real-world entities. The software module can process large amounts of data (e.g., in the range of hundreds of terabytes) stored on disk in one batch. In certain examples it can be configured to run every few hours.

Identifying attributes of an entity are the attributes that act as a contributing factor to identify a real-world entity.

Linking can include the task of identifying records that belong to the same real-world entity. Linking creates clusters of records that belong to real-world entities.

Machine learning (ML) is a type of artificial intelligence (AI) that provides computers with the ability to learn without being explicitly programmed. Machine learning focuses on the development of computer programs that can teach themselves to grow and change when exposed to new data. Example machine learning techniques that can be used herein include, among other things, decision tree learning, association rule learning, artificial neural networks, inductive logic programming, support vector machines, clustering, Bayesian networks, reinforcement learning, representation learning, similarity and metric learning, and/or sparse dictionary learning. Random forests (RF) (e.g., random decision forests) are an ensemble learning method for classification, regression, and other tasks, that operate by constructing a multitude of decision trees at training time and outputting the class that is the mode of the classes (e.g., classification) or mean prediction (e.g., regression) of the individual trees. RFs can correct for decision trees' habit of overfitting to their training set. Deep learning is a family of machine learning methods based on learning data representations. Learning can be supervised, semi-supervised or unsupervised.

Maximum likelihood estimation (MLE) is a method of estimating the parameters of a probability distribution by maximizing a likelihood function, so that under the assumed statistical model the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate.

Near-neighbor is a group of entities selected from the universe of entities that likely belong to the same real-world entity.

On-demand linking can use a software module that provides an API which can be called by an external software application. The external software application can call the API with the records that it wants to be linked.

Real-time linking can use a software module that creates clusters of records that belong to real world entities. This software module may continuously consume data from a data stream in micro-batch intervals (e.g., of less than a minute) and processes micro-batches of data as they arrive in the data stream. High-throughput linking can be meant to process large amounts of data, whereas real-time linking can be meant to process small data quickly (e.g., on the order of less than a minute).

Structured Query Language (SQL) is a domain-specific computer programming language designed for managing data held in a relational database management system, or for stream processing in a relational data stream management system.

Transfer learning (TL) uses machine learning (ML) to focus on storing knowledge gained while solving one problem and applying it to a different but related problem.

Transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.

Example Methods and Systems

As shown inFIG.1C, an overall entity database system consists of the following components. Resolution component/engine150efficiently resolves entities from a set of records160and updates the resolution upon receiving new records. Canonicalization component/engine152canonicalizes the trait values to support various entity representations. Persistence component154persists the entities. Query component/engine156queries entities. A parser for supporting a declarative language, which is integrated with resolution component/engine150, canonicalization component/engine152, and query component/engine156, provides users with a means to interact with the entity database system for resolution, canonicalization, or querying.

FIG.1Aillustrates an example system100for implementing an entity database system, according to some embodiments. It is noted that entities can include, for example, customer data about a person, company, product, parts, etc. System100can be used for the task of identifying records that belong to the same real-world entity (e.g., linking processes, etc.), performing canonicalization, persisting, and querying entities.

As shown, system100includes a high-throughput linking104and canonicalizing105that stores its output to a state store108. This can be performed in high-throughput layer120. A high-throughput layer120can be a software module that can process large amounts of data (e.g., hundreds of terabytes) using a cluster of machines (e.g. computer hardware and/or software systems). This cluster of machines may operate in a traditional local computing environment or in a cloud-based virtual computing environment.

System100includes a real-time linking102and canonicalizing103that stores its output to a state change store106. This can be performed in real-time layer118.

System100includes an entity query engine109that reads from the state store108and stage change store106.

It is noted that, in some example embodiments, a layer can be a software module that performs a well-defined set of tasks. A layer can define a list of interfaces and APIs through which other modules can interact with it.

A batch data source126can be from a data storage which stores large amounts of data on storage disks. An event stream124(e.g. a real-time data source and/or streaming data source) includes data that is delivered as a continuous stream of records.

A high-throughput layer120can be a software module that can process large amounts of data (e.g. hundreds of terabytes) using a cluster of machines (e.g. computer hardware and/or software systems). High-throughput layer120can read data from batch data sources and performs linking and canonicalization at a defined interval usually every few hours or every few days. Depending on the input data size, the processing may take a few hours to a few days.

A real-time layer118can be a software module that reads data from an event stream and performs linking and canonicalization every few seconds. This process usually takes less than a few seconds.

An Entity Query Engine109can be a software module that performs queries in response to a user query from an external application. Based on the query, query engine109reads both state store108and state change store106and performs matching and returns the matched results back.

System100can also interact with an application configuration layer (not shown). In some examples, an application configuration layer can be a software module that is used to change the configuration/behavior of the high-throughput layer120, as high-throughput layer120processes large amounts of data in batches. Batch intervals can vary from a few hours, a day, etc. This can be a customization on top of the data processing layers.

A lambda switch128ensures that entities' state remain consistent as it switches from an old generation of state to a new generation. Lambda switch128is configured to ensure that a set of states of the entities remain consistent when the on-demand linking switches a serving from an older generation of state store106and the state change store106to a new generation of the state store108and the state change store106. Lambda switch128provides for the query engine layer109to continue to query without any downtime. The lambda switch128provides functionality that ensures that both real-time layer118and high-throughput layer120continue to work seamlessly. Accordingly, lambda switch128provides the ability to process massive amounts of data as well as the ability to reduce latency while processing real-time data.

System100performs both high-throughput linking104and real-time linking102. In some examples, high-throughput layer120performs linking of large batches of data every few hours, while real-time linking102performs linking on a data stream as the stream is received. High-throughput104linking ensures the accuracy and comprehensiveness of the linking. Real-time linking102minimizes the latency of stream data. System100combines these two layers (i.e. high-throughput104and real-time linking102) to provide the benefit of accuracy, comprehensiveness, and low latency. Lambda switch128can be the software module that ensures that data remains consistent across these two layers.

Entity matching of system100can be used to resolve the following, for example: attribute ambiguity (e.g., same name may refer to different individuals); missing value(s) (e.g., missing email, address); data entry errors (e.g., misspelled names, extra digits); changing attributes (e.g., name change, address change); multi-relational (e.g., family relation); etc. System100can be used to bring all the variations of a real-world entity together. Accordingly, entities (e.g. any type of real-world entity, such as, a person, a merchant, etc.) can be matched using system100.

It is noted that the linking process can be repeated using different matching rules to generate different variations of the matched entities or match different types of entities. It can also be used to generate relationships between entities. These relationships can be hierarchical or associative. For example, linking can resolve subsidiary relationships between a parent and its subsidiaries.

FIG.1Billustrates an example process130for implementing a matching platform for entities, according to some embodiments. In step1, high-throughput linking104reads data from batch data sources at time t0. High-throughput linking104performs linking and saves the output in the state store108. The state store108stores the states of all entities at time t0. This output can be labeled state Generation 0. Process130can mark this as the current state store108.

In step2, real-time linking102is implemented as a continuous process. In one example, real-time linking102reads data from the event stream every few seconds (e.g., in micro batches). In alternative embodiments, the time at which the event stream is read may be varied. Real-time linking102reads data from the state store and performs linking, applies the change on the state of the affected entities, and saves the results in the stage change store106. The output of real-time linking102represents the latest state of an entity.

At step3, when an external application calls API114to perform a query about an entity, API114calls the entity query engine109. Entity query engine109reads both the state store108(e.g., includes generation 0) and state change store106. Based on what is read, Entity Query Engine109performs linking and returns the results.

In step4, at time t1 (e.g., which can be after a few hours or few days after t0) the high-throughput linking104runs. At this point in time, process100reads the batch data sources at time t1 and the event sink116. This run produces a new state store marked as generation 1. This generation of the state stores contains the states of all entities constructed using the data received from both batch and real-time sources at time t1.

In step5, at time t1+t+x, lambda switch128invalidates generation 0 of the state store108, adjusts the state change store, and makes generation 1 the current state store. After the switch, on-demand linking110switches to generation 1 of the state store to serve any queries. Lambda switch128can serve two purposes here. First, lambda switch128ensures that the switch from generation 0 to generation 1 (e.g., the next generation) does not make states of entities inconsistent. Second, lambda switch128ensures that there is no downtime for on-demand linking110(e.g., on-demand linking110can continue serving an external application).

FIG.2illustrates an example process200for implementing high-throughput linking in a matching platform for entities, according to some embodiments. Process200illustrates various steps implemented for a linking process. High-throughput linking can be tuned toward accuracy, etc. In near neighbor generation step202, process200can implement near neighbor generations. Pairwise matching can be implemented within each cluster. This can reduce the number of iterations needed to make comparisons in the matching process. Step202generates identities that are likely to match.

Step202can generate sufficient groups such that if two identities match, they are included into a single block (e.g., of blocks of groups of near neighbors304provided below). Additionally, step202can ensure that said blocks are not too large (e.g., beyond a specified threshold). Step202can return a set of blocks of identities.

FIG.3illustrates an example schematic of a near-neighbors process300, according to some embodiments. This can be implemented by step202. Step202can generate groups of near neighbors304of identities from entities E1-E8302that are likely to match. Step202generates likely matches, ensuring with high probability that true positives at least fall in one of the near neighbor groups.

A custom function can be plugged-in to generate near neighbors. For example, step202can generate a set of keys on each event and group them by the keys.

The generated key can be:

nnf(e1)={k11, k12, k13, . . . k1m}

nnf(e2)={k21, k22, k23, . . . k2m}

. . . .

The group by key can be:

k11→{e1, e6, e7, . . . }

. . . .

Returning toFIG.2, in step204, process200can implement pairwise matching. Step204uses a pre-built AI-based model and set of business rules on pairs of identities in a block. In this way, step204can infer whether the pair match or not. The custom model can be plugged-in. Step204returns all the matched pairs. Each AI-based model can be built for a specific type of real-world entity. For example, an AI-based model can match address, names, certain behavior, etc. to a customer ID based on a probability of a match. AI-based models use, for example, a random forest classifier, an artificial neural network and/or BERT encoding. These models can be trained on pairs identities. During training, the models can learn to distinguish differences across the pairs which can predict either a positive or negative match.

FIG.4illustrates an example of a schematic of pairwise matching, according to some embodiments. Step204can use a pre-built matching function based on an AI architecture. Examples of a pre-built matching function for a person entity can include, for example, matching of names, matching of addresses, etc. Step204can use a matching function that returns a probability of a matching given a pair of identity. Step204can use a plug-in of custom business matching rules and constraints. Step204can re-train a pre-trained model (e.g., transfer learning) and/or build a custom model using an entity resolution (ER) workbench. The ER workbench is an application of an AI-model to perform pairwise matching. As shown inFIG.4, step204can compare entities with each near neighbor group (e.g. of groups of near neighbors304) to generate probability of a match in set of matched pairs:

mf(ei,ej)=probability of match

If (mf(ei,ej))>threshold then a match.

Returning to the description of process200, in step206, process200can implement transitive closure. Step206can perform transitive closure on the matched pairs (e.g., using pairwise matching discussed above). Step206uses a distributed connected component algorithm to scale, in certain embodiments, to hundreds of millions of pairs. Step206returns the transitive closure of the matched pairs.

FIG.5illustrates an example schematic500of a transitive closure process, according to some embodiments. As shown, step206can apply transitive closure on each of the pairs of matched identities and create the clusters. In the illustrated example, there is a match between e1 and e2, a match between e2 and e3, and a match between e3 and e4. Therefore, e1, e2, e3, and e4 are all assigned to the same cluster because of the transitive relationship.

In step208, process200can implement a cluster split (e.g., correlation clustering). The transitive closure can result in a cluster that is imperfect (e.g., contains conflict(s)). Transitive closure on pairs of matching entities can create clusters of entities that contain conflict. Step208can apply a two-disagreeing captain algorithm (e.g., see below) to split the cluster in order to resolve the conflicts. Step208can return clusters containing matched identities.

FIG.6illustrates an example schematic600for cluster splitting, according to some embodiments. Schematic600can be used to implement step208. In this example, step208applies constraints to split the cluster by using a two-disagreeing captain algorithm. The two-disagreeing captain algorithm chooses two captains. Each captain represents a cluster of the two clusters. The two-disagreeing captain algorithm greedily assigns other members in the original cluster to each of the captains. It then calculates an MLE of the two resultant clusters. When the resultant split maximizes the probability then a split is implemented. This process is repeated for every split till a split does not maximize the probability.

Returning to the description ofFIG.2, in step210, process200can implement stable ID assignment. Matched clusters are assigned “Stable ID”. A stable ID preserves the ID that was assigned in a previous ID assignment. In case of an ID split, step210minimizes the change in ID assignment. Step210returns a cluster with a stable ID.

FIG.7illustrates an example schematic700illustrating a stable identifier (ID) assignment, according to some embodiments. Schematic700can be used to implement step210. As shown, matched clusters are assigned a Stable ID.

A custom rule can be plugged in on which ID should be chosen. Step210can return clusters with stable IDs. Custom rules for ID assignments can be used to determine which previous ID to choose when an ID splits or when IDs are merged into one. For example, a custom rule for an ID merge or ID split can preserve the ID of the largest cluster.

In the example ofFIG.7, two runs A and B are performed. Between these two runs, it may be seen that the cluster in run A that contains e4 no longer contains e4 in run B. In addition, e8 and e9 are newly found in run B. The issue then is how to assign IDs based on the changes seen in run B. In this example, it would appear that ID1 from the first cluster of run A should still belong with the first cluster of run B, as only e4 changed. ID2 likewise remains with the second cluster, even though e9 was added in run B. The new cluster including e4 and e8 is assigned a new ID3.

FIG.8illustrates an example process800for real-time/on-demand linking (RTL), according to some embodiments. Unlike with high-throughput matching, process800may not consider the secondary (or tertiary effects) of matching. A secondary impact of a matching is when a matching may affect other matching previously performed. In step802, process800can implement a near-neighbor lookup. Step802can receive and utilize an event stream data and/or a synchronous/asynchronous request to perform linking. In step804, process800can implement pairwise matching. In step806, process800can use a stable ID or create a new ID.

Process800can implement real-time linking by linking identity(s) in a low latency context (e.g., in milliseconds). Process800may, in some embodiments, not consider the secondary impact of a match of real-time events but guarantees the correctness of the match. After the lambda switch, when real-time events received until the switch are fed into a high-throughput linking, then the secondary and subsequent impacts can be considered.

FIG.9illustrates an example data management process900according to some embodiments. Data management process900can be used to minimize data preparation. Data management process900can use data operations management module902. Data operations management module902can include modules for, among other things, data quality, data backout management, data workflow, taxonomy management, compliance, and visibility, etc.

More specifically, in step904, process900can implement low latency validation on the events stream. In step906, process900can implement low latency transformation/enrichment. This can generate real-time events912.

In step908, process900can implement high-throughput validation. The output of step908can be fed into step910. In step910process900can implement a high-throughput transformation/enrichment. High-throughput transformation/enrichment can provide output that is integrated with real-time events912. High-throughput transformation/enrichment can also generate quality metrics914.

Data management process900can also provide for implementing, among other things, data quality management, data backup management, legal compliance workflows, compliance, and visibility protocols, etc.

FIG.10illustrates an example schematic1000of a composite profile creation, according to some embodiments. As shown, an SQL-like Entity Query Language (EQL) can be used to calculate various attributes and/or properties of the entity. All the matched attributes of the entity can be utilized. It is noted that EQL has a rich set of predefined functions to calculate entity specific attributes (e.g. MOST_FREQUENT, MONTHLY, LAST_ACTIVE etc.). Additionally, machine learning (ML) inference functions can be used in EQL as a regular function.

FIG.11illustrates an example process1100for composite profile creation, according to some embodiments. In step1102, all calculations are expressed in an EQL format. In step1104, process1100can implement an execution plan that cuts across all calculations. In step1106, process1100can create in-memory data structures suitable for each entity to execute the plan. In step1108, process1100can calculate the relevant attributes.

Entity Database Management System

An entity database management system is provided to handle and store entity data. The entity database management system utilizes an entity-oriented database, rather than a record-oriented database such as a traditional SQL database. The entity database management system can be used to help enterprises resolve, manage, and query entities. The entity database management system forms a superset of the components described above in an overall system for entity resolution.

FIG.12illustrates an example architecture of an entity database1200, according to some embodiments. Entity database1200can be utilized in the entity database management system. Entity database1200can include DML parser1202. DML parser1202parses statements to load data into the Entity Database. The DML statements are declarative instructions used to create an entity and to load data into entity database1200. The loading requires the resolution of entities (e.g., see below). DML parser1202converts parsed statements into a pipeline of instructions. These instructions are then passed to the entity resolution engine1206for execution.

FIG.13illustrates an example DML grammar1300, according to some embodiments. DML grammar can be used to define a statement of entity database1200.

Entity database1200can include query parser1204. Query parser1204parses query statements to perform a query for an entity. The query statements are declarative instructions containing entity traits. Entity resolution engine1206then runs these instructions to perform matching and returns matched entities.FIG.14illustrates an example query-statement grammar1400, according to some embodiments.

Entity database1200can include entity resolution engine1206. Entity resolution engine1206is responsible for creating entities, resolving, and performing queries.FIG.15illustrates an example set of components of an entity resolution engine1206, according to some embodiments. This includes resolution pipeline1502.

Resolution pipeline1502includes trait extractor1504. Trait extractor1504extracts traits from each record and performs de-duplication, that is, removes duplicate records as they come into resolution pipeline1502. Processing them proceeds through near neighbor generation202, pairwise matching204, transitive closure206, cluster split208, and stable ID assignment210as explained above.

Resolution pipeline1502executes the DML resolve statements from DML parser1202to perform resolution and populating the stamped entity store1512, stamped record store1514, and blocking indices1510. These are stored in their own database storage areas or in different areas of one or more physical storage areas. The resolution pipeline1502executes the query statement.

Resolution dictionary1506maintains metadata information about the resolved entities and various metrics. Audit log1508maintains the audit of all the activities including resolution and query. Blocking indices1510maintains the blocking keys and references to every block. Stamped entity store1512stores all of the resolved entities and associated identifiers. It also maintains the lineage of identifiers including identifier history, identifier merges, and identifier splits. Stamped record store1514stores all the records and their associated identifiers.

Example Computer Architecture and Systems

FIG.16depicts an exemplary computing system1600that can be configured to perform any one of the processes provided herein. In this context, computing system1600may include, for example, a processor, memory, storage, and I/O devices (e.g., monitor, keyboard, disk drive, Internet connection, etc.). However, computing system1600may include circuitry or other specialized hardware for carrying out some or all aspects of the processes. In some operational settings, computing system1600may be configured as a system that includes one or more units, each of which is configured to carry out some aspects of the processes either in software, hardware, or some combination thereof.

The main system1602includes a motherboard1604having an I/O section1606, one or more central processing units (CPUs) or processors1608, and a memory section1610, which may have a flash memory card1612related to it. The CPU1608may be a multiprocessor system. The1/O section1606can be connected to a display1614, a keyboard and/or other user input (not shown), a disk storage unit1616, and a media drive unit1618. The media drive unit1618can read/write a computer-readable medium1620, which can contain programs1622and/or data. Computing system1600can include a web browser. Moreover, it is noted that computing system1600can be configured to include additional systems in order to fulfill various functionalities. Computing system1600can communicate with other computing devices based on various computer communication protocols such as Wi-Fi, Bluetooth® (and/or other standards for exchanging data over short distances including those using short-wavelength radio transmissions), USB, Ethernet, cellular, etc. Computing system1600may be implemented as a local system or a cloud-based system, in the latter case operating potentially as a virtual computing system within a cloud-computing environment.

CONCLUSION

Although the present embodiments have been described with reference to specific example embodiments, various modifications and changes can be made to these embodiments without departing from the broader spirit and scope of the various embodiments. For example, the various devices, modules, etc. described herein can be enabled and operated using hardware circuitry, firmware, software or any combination of hardware, firmware, and software (e.g., embodied in a machine-readable medium).

In addition, it can be appreciated that the various operations, processes, and methods disclosed herein can be embodied in a machine-readable medium and/or a machine accessible medium compatible with a data processing system (e.g., a computer system), and can be performed in any order (e.g., including using means for achieving the various operations). Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense. In some embodiments, the machine-readable medium can be a non-transitory form of machine-readable medium.