Deduplication and disambiguation

Systems and methods for deduplication and disambiguation are disclosed. In example embodiments, a server accesses stored information about a first entity and stored information about a second entity. The server determines, based on the accessed stored information about the first entity and the accessed stored information about the second entity, a set of information items known about both the first entity and the second entity. The server computes, based on the set of information items, a probability that the first entity corresponds to the second entity by computing one or more expressiveness scores corresponding to a value of a first information item and a value of a second information item from the set of information items. The server provides, as a digital transmission, an output representing the computed probability.

RELATED APPLICATIONS

This application is related to U.S. patent application Ser. No. 15/341,711, titled “IDENTIFYING USER INFORMATION FROM A SET OF PAGES,” and filed on Nov. 2, 2016, which is incorporated herein by reference in its entirety. This application is related to U.S. patent application Ser. No. 15/274,418, titled “MESSAGING SERVICE INTEGRATION WITH DEDUPLICATOR,” and filed on Sep. 23, 2016, which is incorporated herein by reference in its entirety. This application is related to U.S. patent application Ser. No. 15/274,464, titled “APPLICANT TRACKING SYSTEM INTEGRATION WITH DEDUPLICATOR,” and filed on Sep. 23, 2016, which is incorporated herein by reference in its entirety.

TECHNICAL FIELD

The present disclosure generally relates to machines configured for deduplication and disambiguation of data stored in a data repository, including computerized variants of such special-purpose machines and improvements to such variants, and to the technologies by which such special-purpose machines become improved compared to other special-purpose machines that provide deduplication technology. In particular, the present disclosure addresses systems and methods for deduplication and disambiguation of data stored in a data repository.

BACKGROUND

Deduplication and disambiguation of data stored in a data repository may be useful in multiple contexts. In one example, a person may combine multiple contact lists (e.g., an email contact list, a social network contact list, and a mobile phone contact list) and wish to remove duplicate entries. In another example, a team of recruiters may be prohibited (e.g., for legal, company policy or best practice reasons) from contacting candidates that the team has previously contacted during a time period (e.g., in the last six months). Thus, when reviewing a potential candidate, the recruiter may wish to compare the candidate with previously contacted candidates. As the foregoing illustrates, techniques for deduplication and disambiguation of data stored in a data repository may be desirable.

DETAILED DESCRIPTION

Overview

The present disclosure describes, among other things, methods, systems, and computer program products that individually provide various functionality. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the various aspects of different embodiments of the present disclosure. It will be evident, however, to one skilled in the art, that the present disclosure may be practiced without all of the specific details.

Some aspects of the subject technology address the problem in the computer arts of deduplication and disambiguation. According to some implementations, the solution to the problem of deduplication and disambiguation includes a server accessing, in a data repository, stored information about a first entity and stored information about a second entity. The data repository may be a database or may have any other structure. In some examples, the stored information includes one or more of a first name, a last name, a telephone number, an email address, a postal address, a social networking link or handle, and the like. The server determines, based on the accessed stored information about the first entity and the accessed stored information about the second entity, a set of information items known about both the first entity and the second entity. The server computes, based on the set of information items, a probability or a score that the first entity corresponds to the second entity by computing one or more expressiveness scores corresponding to a value of a first information item and a value of a second information item from the set of information items. The server provides, as a digital transmission (e.g., to another machine or to a different component of the server), an output representing the computed probability or score. In some cases, if the computed probability or score exceeds a threshold probability (e.g., 80% or 95%) or threshold score, the server determines that the first entity and the second entity represent a common individual or organization based on the computed probability or score exceeding the threshold probability or score. The server combines, within the data repository, the first entity and the second entity into a single entity in response to determining that the first entity and the second entity represent a common individual or organization. As used herein, a data repository may include any data storage unit, for example, Random-Access Memory (RAM), a database, cloud storage, and the like. In some cases, the two entities being de-duplicated might reside in different data storage units. According to one mode of operation, one piece of information is inserted in the data repository (but does not yet reside in the data repository) and is de-duplicated against numerous potential matches already in the data repository. However, any amount of the information ranging from none to all of it may live in the data repository.

As used herein, the term “deduplication” may refer to, among other things, removing duplicate entries from a data repository. For example, if a data repository includes the following entities: (1) “John Sample,” mobile phone 650-555-1212, and (2) “John Q. Sample,” mobile phone 650-555-1212, a server may conclude that these entries are duplicates (due to similar name and same mobile phone number) and remove one of the duplicate entries or combine the entries.

As used herein, the term “disambiguation” may refer to, among other things, replacing ambiguous entries with full entries. For example, if a data repository includes the entities: (1) “John Sample,” mobile phone 650-555-1212, and (2) “J. Sample,” mobile phone 650-555-1212, a server may conclude, based on the common last name and mobile phone numbers, that the initial J represents John and replace “J” with “John.”

FIG. 1illustrates an example network system100, in accordance with some embodiments. As shown, the system100includes client devices110, a server120, and a data repository130connected to one another and capable of communicating with one another via a network140. The network140may include one or more networks and may include one or more of the Internet, a wide area network (WAN), a local area network (LAN), a virtual private network (VPN), an intranet, and the like.

The subject technology may be implemented with multiple client devices110. Each client device110may be a laptop computer, a desktop computer, a mobile phone, a tablet computer, a smart watch, a personal digital assistant (PDA), a digital music player, and the like. The client devices110may be used to add data to the data repository130and to access data stored in the data repository130.

The data repository130may be implemented as a database or any other data storage unit. The data repository130stores a set of entities and information about each entity. The entity may represent a contact, such as an individual or an organization. The data repository130is described in more detail in conjunction withFIG. 2, below.

The server120is configured to apply deduplication and disambiguation to the data repository, for example, as set forth above. More details of the operation of the server120are provided in conjunction withFIG. 3, below.

As used herein, the term “configured” encompasses its plain and ordinary meaning. In one example, a machine is configured to carry out a method by having software code for that method stored in a memory that is accessible to the processor(s) of the machine. The processor(s) access the memory to implement the method. In another example, the instructions for carrying out the method are hard-wired into the processor(s). In yet another example, a portion of the instructions are hard-wired, and a portion of the instructions are stored as software code in the memory.

FIG. 2is a block diagram illustrating an example of the data repository130ofFIG. 1, in accordance with some embodiments. As shown, the data repository130stores information220.1-N about multiple entities210.1-N. Each entity210.k(where k is a number between 1 and N) may be an individual or an organization. The information220.kabout the entity210.kmay include one or more of a first name, a last name, a telephone number, an email address, a postal address, a social networking link or handle, and the like. Other attributes in the information items220.kmay include employer(s), educational institution(s), and the like. The list of attributes provided here is not exhaustive. In some cases, one or more of the information items in the information220.kmay be missing (e.g., a name and a telephone number, but no email address, may be stored). The data repository130may correspond to a contact list of a user of an email service, a mobile phone, or an online contact storage service. Multiple information items220.kmay be stored for each entity210.k.

In some cases, a new entity230(similar to entity210) having new information240(similar to information220) may be added to the data repository130. For example, the data repository may store an online contact list, and a user of a client device110may decide to add a new entity230to his/her contact list, and to provide some new information240for the new entity.

In these cases, the server120may determine, using the techniques described herein, whether the new entity230represents a new individual or organization or an individual or organization that is already associated with one of the entities210.1-N. In the latter case, the new entity may be combined with the one of the entities210.1-N representing the same individual or organization.

FIG. 3is a flow chart illustrating an example method300for identifying duplicate data. After duplicate data is identified, the duplicate data may be combined into a single data entry. In some examples, the method300is implemented at the server120. It should be noted that, if entities are combined, the server120(or another machine) retains a copy of the original record so that the decision to combine these entities may be revisited in the future as more information is acquired or as improvements/modification are made to the disambiguation techniques used. Combined entities and original source entities may be stored separately.

At operation310, the server120accesses stored information about a first entity and stored information about a second entity. The stored information about the first entity and the second entity may be stored in the data repository130. In some cases, the first entity is the new entity230being added to the data repository130, and the second entity is one of the entities210.k(where k is a number between 1 and N) in the data repository130. In some cases, the first entity is an entity210.m(where m is a number between 1 and N) in the data repository, and the second entity is another one of the entities210.kin the data repository.

At operation320, the server120determines, based on the accessed stored information about the first entity and the accessed stored information about the second entity, a set of information items known about both the first entity and the second entity. The information items may include (but is not limited to) one or more of a first name, a last name, a telephone number, an email address, a postal address, a social networking link or handle, and the like. The information about the first entity may be stored in information240(if the first entity is the new entity230) or the information220.m(if the first entity is the entity210.m). The information about the second entity may be stored in information220.k(if the second entity is the entity210.k). In some cases, each information item has an information type. The information type may be (but is not limited to) one of a name type (e.g., first name, last name, and the like), a contact type (e.g., email address, telephone number, instant messenger screen name, social network handle, and the like), a business type (e.g., company name, industry, and the like), a geography type (e.g., street address, city, state, country, and the like), and the like.

In one example, the information items known about the first entity include a first name, an email address, and a telephone number. The information items known about the second entity include a first name, a last name, an email address, and a social networking link. In this example, the information items known about both the first entity and the second entity include the first name and the email address. In some cases, information item(s) may be converted into a normalized format using data normalization. For example, names, email addresses, and the like may be converted into a normalized format that recognizes, for example that “John@Example.com” and “john@example.com” represent the same email address and “617-555-1234” and “+1 617 555 1234” represent the same telephone number. Data normalization may also include looking up in a database (or other data structure) that common names are associated with the same entity, for example “Ben” is a nickname for “Benjamin,” and “IBM” and “International Business Machines” are the same. Furthermore, the database may also include historical information, such as the fact that Target-Company was acquired by Buyer-Company in June 2014 (and, therefore, a first entity that is named John Smith and worked for Buyer-Company in August 2014, and a second entity that is named John Smith and worked for Target-Company in July 2014, are likely the same).

At operation330, the server120computes, based on the set of information items known about both the first entity and the second entity, a probability or a score that the first entity corresponds to the second entity (i.e., that the first entity and the second entity represent the same person or organization). The probability is computed by combining a set of computed expressiveness scores. An expressiveness score is computed from a value of a first information item and a value of a second information item (and, in some cases, values of other information items) from the set of information items. The expressiveness score indicates a confidence in whether the information items match or are in conflict with each other and the uniqueness of such a match in the case where the items match. The first information item may have a different information type from the second information item. For example, the first information item may be a first and last name, and the second information item may be an email address.

In some cases, one of the expressiveness scores corresponding to the value of the first information item and the value of the second information item represents a probability that the first entity corresponds to the second entity given that the first information item and the second information item are associated with both the first entity and the second entity. For example, in a given population (e.g., the population of the San Francisco Bay Area), the last name “Patel” may be fairly common and the first name “Isaac” may be fairly common. However, the full name “Isaac Patel” may be fairly uncommon (e.g., because one group of people is associated with the name “Isaac” and another group of people is associated with the name “Patel”). Thus, in this population “Isaac Patel” may have a high expressiveness score. In another example, the first name “Isaac” may be common and the last name “Cohen,” may be common. However, the full name “Isaac Cohen” may have a lower expressiveness score because “Isaac” and “Cohen” are associated with the same sub-group of the population.

In other words, in a population, 1% of people may have the first name “Isaac,” 1% of people may have the last name “Cohen,” and 1% of people may have the last name “Patel.” However out of the people named “Isaac,” 5% may have the last name “Cohen” (multiplied to 0.05% of the whole population), while only 0.1% may have the last name “Patel” (multiplied to 0.001% of the whole population). Thus, people named “Isaac Patel” are rarer than people named “Isaac Cohen,” resulting in a higher expressiveness score for “Isaac Patel,” than for “Isaac Cohen.”

In some examples, one of the expressiveness scores measures a codependence between the first information item and the second information item. For example, last names and email addresses may be highly codependent (e.g., someone with the last name Smith is likely to have the email address *smith@email-provider.com). Thus, a last name combined with an email address might not be very expressive. On the other hand, a social network handle that corresponds to a “pen name” or unusual nickname (e.g., “silver-bear” or “crazy-climber”) combined with the last name Smith might have a higher expressiveness score, as such pen names/nicknames are not related to the last name.

In yet another example, one of the expressiveness scores may measure or be computed based on a frequency of occurrence of the first information item within the population or a frequency of occurrence of the second information item within the population. In one case, the expressiveness score is computed as the product of the frequency of occurrence of the first information item, the frequency of occurrence of the second information item, and a damping factor (e.g., 1.1). The damping factor may be used to account for the fact that the first information item may be positively correlated with the second information item. In this embodiment, correlation between the first information item and the second information item is not otherwise taken into account.

In some cases, one of the expressiveness scores is inversely proportional to a population size. For example, an employee being associated with “ABC Pizza Shop,” which has approximately 10 employees, is more expressive than an employee being associated with “XYZ Multinational Software Company,” which has approximately 10,000 employees. It is more likely that two records that have the first name “Cindy,” and the employer “ABC Pizza Shop,” are the same, than that two records which have the first name “Cindy,” and the employer “XYZ Multinational Software Company,” are the same, as it is more likely that two of 10,000 people have the same first name, than that two out of 10 people have the same first name. In some cases, names or combinations of names that are rarer have a higher expressiveness score. For example, the first name “Brogan” is rarer than the first name “John,” and thus corresponds to a higher expressiveness score. Covariant expressiveness is also taken into account. For example, the name “Xiaolu Patel” may have a very high expressiveness score as the first name “Xiaolu” is an East Asian name, whereas the last name “Patel” is an Indian name, and it is very unusual for a person to have a first and last name associated with such different geographies. Databases of statistics are used in calculating expressiveness scores. Such databases may be acquired from commercial sources, governmental censuses, computed via entities in a data repository, and the like. An example record from such a database might look like {id:4, stdCompanyName:“XYZ, Corporation”, numEmployees:10000} or {name:“McCann”, count:676244, raceCounts:[white_non_hispanic:664324, hispanic:3212, black:8342, asian:321, american_indian:45]}.

At operation340, the server120provides, as a digital transmission, an output representing the computed probability or score that the first entity corresponds to the second entity. In some cases, the server120determines that the computed probability or score exceeds a threshold probability (e.g., 80% or 95%) or a threshold score. The server120determines that the first entity and the second entity represent a common individual or organization based on the computed probability or score exceeding the threshold probability or score. In some implementations, the server combines the first entity and the second entity into a single entity in response to determining that the first entity and the second entity represent the common individual or organization. In this manner, duplicate entities from the entities210.1-N of the data repository130may be combined into single entities.

In some cases, there may be multiple entities to deduplicate. For example, Entity A may include the name “Bill Clinton.” Entity B may include the telephone number “212-555-1234.” Entity C may include both “Bill Clinton” and “212-555-1234.” The server120may conclude that Entity A and Entity B are the same based on Entity A corresponding to Entity C and Entity B corresponding to Entity C. In some cases, the probability or the score that the first entity corresponds to the second entity is computed initially, and then updated based on changes/improvements to the algorithm or based on additional information being added to the first entity or the second entity. Based on the updated probability or score, the server120may conclude that a first entity and second entity which were previously the same are now different, or vice versa. In some implementations, a graph of pairwise probabilities/scores for first entities and second entities is stored. When a probability/score in the graph changes, due to changes in the algorithm or changes in stored information about the entities, the server120may modify its conclusion about whether a first entity and a second entity represent the same entity.

The subject technology may have multiple different use cases. For example, the subject technology may be implemented to remove duplicate contacts from a contact list of an email account, a mobile phone, a personal digital assistant (PDA), an online contact storage unit, and the like.

In one example, the subject technology is implemented in a recruiting context, where an office of multiple recruiters is prohibited (e.g., due to legal, company policy, or best practice reasons) from contacting the same candidate multiple times within a given time period (e.g., six months or twelve month). In the recruiting context, the first entity represents an employment candidate whom one of the multiple recruiters wishes to contact. The data repository130stores, as the entities210.1-N, a list of employment candidates whom the multiple recruiters have contacted previously during the given time period. The second entity is one of the entities stored in the data repository130. The output representing the computed probability is a notification to the recruiter that the multiple recruiters from the office have likely (e.g., with a likelihood represented by the probability) previously contacted the employment candidate whom the recruiter wishes to contact. In some cases, a notification that the employment candidate has already been contacted may be shown without the probability, for example, if the probability exceeds a threshold value (e.g., 99.6%). A notification that the employment candidate may have been contacted, along with the probability, may be shown if the probability is within a certain range (e.g., between 70% and 99.6%) or if there is reason to believe that stored information about the employment candidate is inconsistent or incorrect.

In summary, the first entity represents an individual (e.g., employment candidate) whom one or more users (e.g., recruiters from a recruiting team, or a specific recruiter on the recruiting team) wish to contact. The second entity represents an individual (e.g., an employment candidate from a data repository storing previously-contacted candidates of the recruiting team) that the one or more users have previously contacted. The output representing the computed probability includes a notification that he one or more users have likely previously contacted the individual represented by the first entity. Other entities, different from individuals, can also be de-duplicated. For example, businesses that appear on multiple different services (e.g., a professional networking service, a mapping service, an employment search service, and the like) may be de-duplicated in a system that stored links to information about businesses.

Embodiments are described herein as being performed in a network system (e.g., system100ofFIG. 1) with different machines carrying out different functions. However, the subject technology is not limited to network system. In some cases, a single machine may perform the functions of both the server and the data repository. This machine may be either a client device or a server. The single machine may either have or lack network connectivity. In some cases, the network140ofFIG. 1may be replaced with a hard-wired or direct wireless connection between two or more machines.

In this manner, this disclosure provides approaches for deduplication and disambiguation of data (e.g., a contact list) stored in a data repository, such as a database. According to some implementations, a server accesses, in a data repository, stored information about a first entity and stored information about a second entity. The data repository may be a database or may have any other structure. In some examples, the stored information includes one or more of a first name, a last name, a telephone number, an email address, a postal address, a social networking link or handle, and the like. The server determines, based on the accessed stored information about the first entity and the accessed stored information about the second entity, a set of information items known about both the first entity and the second entity. The server computes, based on the set of information items, a probability or score that the first entity corresponds to the second entity by computing an expressiveness score corresponding to a value of a first information item and a value of a second information item from the set of information items. The server provides an output representing the computed probability or score. In some cases, if the computed probability or score exceeds a threshold probability (e.g., 80% or 95%) or a threshold score, the server determines that the first entity and the second entity represent a common individual or organization based on the computed probability or score exceeding the threshold probability or score. The server combines, within the data repository, the first entity and the second entity into a single entity in response to determining that the first entity and the second entity represent a common individual or organization.

Modules, Components, and Logic

Machine and Software Architecture

The modules, methods, applications, and so forth described in conjunction withFIGS. 1-3are implemented in some embodiments in the context of a machine and an associated software architecture. The sections below describe representative software architecture(s) and machine (e.g., hardware) architecture(s) that are suitable for use with the disclosed embodiments.

Example Machine Architecture and Machine-Readable Medium

FIG. 4is a block diagram illustrating components of a machine400, according to some example embodiments, able to read instructions from a machine-readable medium (e.g., a machine-readable storage medium) and perform any one or more of the methodologies discussed herein. Specifically,FIG. 4shows a diagrammatic representation of the machine400in the example form of a computer system, within which instructions416(e.g., software, a program, an application, an applet, an app, or other executable code) for causing the machine400to perform any one or more of the methodologies discussed herein may be executed. The instructions416transform the general, non-programmed machine into a particular machine programmed to carry out the described and illustrated functions in the manner described. In alternative embodiments, the machine400operates as a standalone device or may be coupled (e.g., networked) to other machines. In a networked deployment, the machine400may operate in the capacity of a server machine or a client machine in a server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine400may comprise, but not be limited to, a server computer, a client computer, PC, a tablet computer, a laptop computer, a netbook, a set-top box (STB), a personal digital assistant (PDA), an entertainment media system, a cellular telephone, a smart phone, a mobile device, a wearable device (e.g., a smart watch), a smart home device (e.g., a smart appliance), other smart devices, a web appliance, a network router, a network switch, a network bridge, or any machine capable of executing the instructions416, sequentially or otherwise, that specify actions to be taken by the machine400. Further, while only a single machine400is illustrated, the term “machine” shall also be taken to include a collection of machines400that individually or jointly execute the instructions416to perform any one or more of the methodologies discussed herein.

The machine400may include processors410, memory/storage430, and I/O components450, which may be configured to communicate with each other such as via a bus402. In an example embodiment, the processors410(e.g., a Central Processing Unit (CPU), a Reduced Instruction Set Computing (RISC) processor, a Complex Instruction Set Computing (CISC) processor, a Graphics Processing Unit (GPU), a Digital Signal Processor (DSP), an ASIC, a Radio-Frequency Integrated Circuit (RFIC), another processor, or any suitable combination thereof) may include, for example, a processor412and a processor414that may execute the instructions416. The term “processor” is intended to include multi-core processors that may comprise two or more independent processors (sometimes referred to as “cores”) that may execute instructions contemporaneously. AlthoughFIG. 4shows multiple processors410, the machine400may include a single processor with a single core, a single processor with multiple cores (e.g., a multi-core processor), multiple processors with a single core, multiple processors with multiples cores, or any combination thereof.

The memory/storage430may include a memory432, such as a main memory, or other memory storage, and a storage unit436, both accessible to the processors410such as via the bus402. The storage unit436and memory432store the instructions416embodying any one or more of the methodologies or functions described herein. The instructions416may also reside, completely or partially, within the memory432, within the storage unit436, within at least one of the processors410(e.g., within the processor's cache memory), or any suitable combination thereof, during execution thereof by the machine400. Accordingly, the memory432, the storage unit436, and the memory of the processors410are examples of machine-readable media.

Communication may be implemented using a wide variety of technologies. The I/O components450may include communication components464operable to couple the machine400to a network480or devices470via a coupling482and a coupling472, respectively. For example, the communication components464may include a network interface component or other suitable device to interface with the network480. In further examples, the communication components464may include wired communication components, wireless communication components, cellular communication components, Near Field Communication (NFC) components, Bluetooth® components (e.g., Bluetooth® Low Energy), Wi-Fi® components, and other communication components to provide communication via other modalities. The devices470may be another machine or any of a wide variety of peripheral devices (e.g., a peripheral device coupled via a USB).

Transmission Medium

The instructions416may be transmitted or received over the network480using a transmission medium via a network interface device (e.g., a network interface component included in the communication components464) and utilizing any one of a number of well-known transfer protocols (e.g., HTTP). Similarly, the instructions416may be transmitted or received using a transmission medium via the coupling472(e.g., a peer-to-peer coupling) to the devices470. The term “transmission medium” shall be taken to include any intangible medium that is capable of storing, encoding, or carrying the instructions416for execution by the machine400, and includes digital or analog communications signals or other intangible media to facilitate communication of such software.

Language