Methods and Systems for Discovery of Linkage Points Between Data Sources

[0001] The present invention relates to data management.

[0002] Many increasingly important data management and mining tasks require integration and reconciliation or fusion of data that reside in multiple large and heterogeneous data sources. Data integration is generally defined as combining data that reside in different sources and providing users with a unified view of the data. In data fusion, duplicates are merged and conflicting attributes values are identified and possibly repaired in order to provide a single consistent value for each data attribute. Data fusion, therefore, involves duplicate detection, also known as Entity Resolution or record linkage, where the goal is to identify data records that refer to the same entity.

[0003] The first step in a data integration or fusion system is identification of “linkage points” between the data sources, i.e., finding correspondences between the attributes in the data sources that can be used to link their records or entities. Traditionally, this is performed by schema matching, where the goal is to identify the schema elements of the input data sources that are semantically related. However, the massive growth in the amount of unstructured and semi-structured data in data warehouses and on the Web has created new challenges for this task. With the increasing size and heterogeneity of data sources, the task can no longer be performed manually using simple user interfaces or with specific heuristics that work well only for a certain type of data or domain. In addition, the noise and error present in data extracted from text documents or large legacy repositories make the task even more challenging.

[0004] Exemplary embodiments of systems and methods in accordance with the present invention provide for the discovery of attributes in large heterogeneous and semistructured data sources or databases that can be used to link records or entities across the databases. The solution is a framework that takes in as input semistructured data sets. Each semistructured data set describes a set of entities of the same type, e.g., companies or people. The framework returns as output a ranked list of pair of attributes from the input sources that can be used to link their records. The framework includes a data registry component to register input data sets, a data loading component that transform the input data into a set of record-attribute-value triples, an indexing component that transforms the input values using an analyzer function and builds efficient reverse indices and a set of search algorithms that perform a search for linkage points using a similarity function that measures the similarity of the transformed/analyzed value sets. A set of filtering criteria that filters false positives from the output of search algorithms is also used.

[0007] Referring to FIG. 1, an exemplary embodiment of a system or framework 100 for lining data records across datasets in accordance with the present invention is illustrated. The system includes a plurality of different datasets 102. The datasets can be of different types and formats, e.g., comma separated value datasets, relational databases stored in relational database management systems, resource description framework databases, extensible markup languages databases, web application programming interface databases and javascript object notation databases. In general, these databases contain one or more data records 103 associated with entities, i.e., real-world entities. These real-world entities include, but are not limited to, businesses, individual persons, corporations, government entities, non-profit organizations, religious organizations, schools, colleges, universities, sports teams, historical figures, literary works, and geographical data. Any entity or topic for which data can be gathered, stored and analyzed can be stored in a database and in a format that can be linked using the current invention.

[0008] Each data record in a given database is associated with a real-world entity and includes data about that real-world entity. As the same real-world entity can have data records in more than one database or related real-world entities can have data records in more than one database, the present invention provides for the linking of data records across databases that are associated with a common or related entity. Each data record in each database contains attributes and each attribute has an associated value or values. These attributes are, for example, names, dates, locations, or other descriptive information regarding the entity associated with a given data record. The values are character strings of information that include alpha-numeric characters, non-alphanumeric characters and spaces, e.g., 100 East Main Street.

[0009] The system includes a registration and loading module 104 that is in communication with the datasets. An analysis and indexing module 106 is in communication with the loading module and receives data records from the loading module. The data records are labeled and analyzed for attributes and values. These attributes and values for each data record are placed into a desired format, i.e., label, attribute and value triples. The analysis and indexing module is in communication with a tokenizer and analyzer library 107 and uses the module to analyze and tokenize each value in each triple. Each string of characters is analyzed and broken into a set containing a plurality of tokens, which can be individual characters or sub-strings of characters, e.g., {101, East, Main, Street}.

[0010] A linkage point discovery module 108 is provided that can identify linkage points between data records across datasets. Each linkage point can be used to link data records in each of two data sets that are associated with the same real-world entity or related real-world entities as determined through a comparison of the token sets associated with attributes in each one of the two data records. Therefore, the linkage point discovery module 108 is in communication with a similarity function library 109, and uses one or more of the similarity functions contained in that library to identify pairs of token sets that meet a predetermined similarity threshold based on a comparison of the tokens in those token sets.

[0011] A filtering module 110 is included in the system that is used to eliminate false positives in the identified linage points. The module can also rank the identified linkage points by strength or group. Common occurrences of linkage points can be grouped together or linkage points can be aggregated together to identify linkage points, i.e., data records for common entities or related entities, across three or more datasets. All of these modules can run on one or more computing systems, e.g., a distributed or cloud based computing system, and can include other components 112 to support the running of the linkage point identification modules. These other components include one or more data bases to store data required or generated during the linkage point identification process, a task scheduler and an information retrieval index. An interface 111 such as a visual interface, a graphical user interface or a Web-based interface is provided in communication with the linkage point identification system to communicate and to visualize the results of the data records linkage evaluation and linkage point identification.

[0012] Referring to FIG. 2, an exemplary embodiment for linking data records across datasets 200 in accordance with the present invention is illustrated. A plurality of datasets is identified 202 that contain data records that are to be linked by association with a common entity or related entities. Each dataset contains at least one data record, and each data record is associated with an entity, i.e., real world entity, and includes one or more attributes of that entity and a value associated with each attribute. A given attribute in a given data record can have more than one occurrence within that data record or more than one value within that data record, e.g. multiple physical addresses.

[0013] The data records in each identified dataset are transformed into one or more data record triples 204. Each data record triple for a given data record contains an identification, i.e., label, of a given record, a given attribute within that data record and a value for the given attribute. This identification for the given record or label is an alpha-numeric designation. For example, the first entity in first data set this designation can be E₁D₁. This yields a data record triple of the format {E₁D₁, Address, 101 East Main Street}.

[0014] As the data record linking method uses the attributes to identify linkage points between or among data sets, the values associated with these attributes are compared to identify similarities. Value comparison is facilitated by converting the values associated with the attributes into a format that facilitates the identification of similarities among the values. In one embodiment, each value in each data record triple is converted into one or more tokens 206. Each value is a string of characters. Suitable characters include, but are not limited to, alpha-numeric characters, non-alphanumeric characters and spaces. Therefore, a given token can include an entire character string of a given value or a portion or sub-string of a given value character string. This yields one or more tokens for each value. Conversion of a given value into one or more tokens is accomplished by, for example, placing the value string into the set of tokens without changes (exact analyzer), transforming any upper case alpha-numeric character in the value string into a corresponding lower case alpha character (lower analyzer), breaking the value string into a plurality of tokens defined by the spaces in the value string (split analyzer), replacing non-alphanumeric characters with spaces (word token analyzer), breaking the value string into a plurality of tokens comprising all lowercase alpha-numeric strings of a predetermined length (q-gram analyzer) or combinations thereof.

[0015] As a given attribute in a given data record can have multiple instances or multiple values or multiple instances of a given attribute can occur in more than one data record or dataset, the tokens derived from the value or values associated with any given attribute can be grouped into token sets for a given data record or dataset 208. These token sets can be viewed as instance values of a given attribute in a given data record or given dataset. In one embodiment, a token set is created for each attribute in a given data record. Each token set of a given data record includes all tokens obtain from converting all values associated with a given attribute in the given data record into one or more tokens. Alternatively, a token set is created for each attribute in a given dataset. Each token set includes all tokens obtained from converting all values associated with a given attribute in the given data set into one or more tokens.

[0016] Attribute values are then compared across datasets 210. As the attribute values have been tokenized and the tokens group into token sets, values are compared by comparing token sets associated with attributes in different datasets. In one embodiment, the token sets of attributes are compared using a set similarity function or an information retrieval type relevance function. The goal is to identify pairs of attributes satisfying the predetermined similarity threshold based on the similarity of the values of those attributes are expressed in the token sets. Suitable set similarity functions include, but are not limited to, intersection size, Jaccard similarity coefficient, Dice's coefficient and maximum inclusion degree. Suitable information retrieval type relevance functions include, but are not limited to, cosine similarity with term frequency—inverse document frequency or Okapi BM25.

[0017] In general, tokens sets can be compared using an entire set or individual tokens. In one embodiment, an attribute in each one of a pair of datasets is selected, and the tokens sets in the data records for the selected attributes are compared by comparing all tokens in the token sets to generate an overall similarity score. A determination is then made if the overall similarity score is above the predetermined similarity threshold. Alternatively, an attribute is selected in each one of a pair of datasets. One or more tokens are selected from one of the token sets for given data records for the selected attributes. The other token set is searched on a token-by-token basis for similar tokens to each one of the selected tokens using a value similarity function and a predefined threshold. The similarity scores for all returned similar tokens are averaged, and the average similarity score is compared to the predetermined similarity threshold to see if it exceeds this threshold value.

[0018] The value or token set comparisons are used to identifying matching attributes having values that satisfy a predetermined similarity threshold 220. These matching attributes are used to identifying linkage points between pairs of datasets 240. Each linkage point links one or more pairs of data records such that each data record in each pair of data records is contained in one of a given pair of datasets, i.e., in different datasets. In addition, each pair of data records is associated with a common entity having matching attributes in the given pair of datasets. These common entities can be the same entity or related entities.

[0019] As an example, a linkage point between two data sets D₁ and D₂ is a pair of attributes (p₁, p₂) such that for some attributed matching function, f, the following set is non-empty:

M_(p1,p2)={(r₁,r₂)|r₁εD₁̂r₂εD₂̂ƒ_(p1,p2)(r₁,r₂)}

M is referred to as the linkage set. The attribute matching function ƒ_(p1,p2)(r₁,r₂) returns true if the instance values of the two attributes are relevant based on a relevance function. The relevance function can be defined using a value similarity function sim( ) and threshold value Θ.

[0020] In one embodiment, the following algorithm is used to identify matching pairs of attributes.

	Input:	Data sets D1 and D2,
		A set similarity function f ,
		A lexical analyzer l,
		A matching threshold Θ
		Ouptut: (Ranked) list of pairs of paths (p1,p2)
	1	for each attribute p1 in D1 do
	2	for each attribute p2 in D2 do
	3	score (p1,p2) ← f (InstancesD1l(p1), InstancesD2l(p2))
	4	end
	5	end
	6	return pairs of (p1,p2) with score (p1,p2) ≧ Θ (in descending
		order of score(p1,p2).

[0021] In another embodiment, the following algorithm is used to identify matching pairs of attributes.

	Input:	Data sets D1 and D2,
		A set similarity function f ,
		A lexical analyzer l,
		A value similarity function sim( ),
		Value similarity threshold τ,
		Value of k for top-k search,
		Sample value set size σv,
		A matching threshold Θ
	Ouptut: (Ranked) list of pairs of paths (p1,p2)
1	for each attribute p1 in D1 do
2	Query_Set ← {Up to σvrandom values in InstancesD1l(ps)}
3	for each value q in Query_Set do
4	M ← {(r2,p2,v)|p2 ε Attrr2(D2)   v ε Instancesr2l(p2)
	sim(v,q) ≧ τ}
5	Mtopk ← {(r2,p2,v) ε M with top k highest sim(v,q)}
6	MS ← Multiset{(p2,sim(v,q))|∃r2:(r2,p2,v) ε Mtopk}
7	end
8	score (p1,p2) ← Average sim value for all (p2,sim) ε MS
9	end
10	return pairs of (p1,p2) with score (p1,p2) ≧ Θ (in descending
	order of score(p1,p2).

[0022] The linkage points identified using the matched attributes are then filtered 260 to remove false positives in the identified linkage points. The identified linkage points can also be ranked, for example, based on the strength or degree of similarity. The linkage points can also be aggregated to cover three or more data sets or entities based on overlap. In one embodiment, filtering of the identified linkage points includes filtering linkage points having a linkage set size below a given threshold (cardinality), filtering linkage points wherein the linkage sets contain only a small percentage of records from one of the data sets (coverage) and filtering linkage points having a strength below a predetermined level (strength). This strength expresses a percentage of distinct records that appear in the linkage set. Strength can be expressed using the following equation:

$\mathrm{Strength}\left(M_{\left(p_1,p_2\right)}\right)=\frac{\{1\left(1,2\right)\in M_{\left(p_1,p_2\right)}\}+\{2\left(1,2\right)\in M_{\left(p_1,p_2\right)}\}}{M_{\left(p_1,p_2\right)}\times 2}$

[0023] In one embodiment, the following algorithm is used to filter identified matching pairs of attributes.

Input:	Data sets D1 and D2,
	List Lof linkage points with their score (p1,p2)with corresponding
	attribute matching
	function f( ) and lexical analyzer l,
	Sample linkage set size σs,
	Cardinality threshold κ,
	Smoothing cutoff limit λ,
	Coverage threshold χ,
	Strength threshold τ,
	Value of k for top-k search,
	A matching threshold Θ
Ouptut: (Ranked) list of pairs of paths (p1,p2)
1	for each pair (p1,p2) ε L do
2	M(p1,p2) ← Ø
3	V ←Sample of size σsof InstanceD1l(p1)
4	for each v ε V do
5	R1 ← {r ε D1|v ε InstancesD1l(p1)}
6	R2 ← {r2|r2 ε D2   f(p1,p2)(r1,r2)}
7	if |R1| > λ then
8	R1 ← subset of size λ of R1
9	end
10	if |R2| > λ then
11	R2 ← subset of size λ of R2
12	end
13	M(p1,p2) ← M(p1,p2) ∪ {(r1,r2)|r1 ε R1   r2 ε R2}
14	end
15	if strength(M(p1,p2)) > τ and coverage(M(p1,p2)) > χ
16	and Cardinality of both p1 and p2 are above κ
17	then
18	score′(p1,p2) ← score(p1,p2) × strength(M(p1,p2))
19	end
20	end
21	return pairs of (p1,p2) with score″ (p1,p2) ≧ Θ (in descending
	order of score(p1,p2).

[0024] The identified and filtered linkage points are then used to link data records associated with common entities across datasets 280. The links are displayed to a user 290 and are also utilized for searching data records for entities across the plurality of data sets.

[0025] As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

[0026] Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

[0027] A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

[0028] Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

[0029] Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

[0030] Aspects of the present invention are described above with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

[0031] These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

[0032] The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

[0033] The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

[0034] Methods and systems in accordance with exemplary embodiments of the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software and microcode. In addition, exemplary methods and systems can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer, logical processing unit or any instruction execution system. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. Suitable computer-usable or computer readable mediums include, but are not limited to, electronic, magnetic, optical, electromagnetic, infrared, or semiconductor systems (or apparatuses or devices) or propagation mediums. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk-read only memory (CD-ROM), compact disk-read/write (CD-R/W) and DVD.

[0035] Suitable data processing systems for storing and/or executing program code include, but are not limited to, at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements include local memory employed during actual execution of the program code, bulk storage, and cache memories, which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution. Input/output or I/O devices, including but not limited to keyboards, displays and pointing devices, can be coupled to the system either directly or through intervening I/O controllers. Exemplary embodiments of the methods and systems in accordance with the present invention also include network adapters coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Suitable currently available types of network adapters include, but are not limited to, modems, cable modems, DSL modems, Ethernet cards and combinations thereof.

[0036] In one embodiment, the present invention is directed to a machine-readable or computer-readable medium containing a machine-executable or computer-executable code that when read by a machine or computer causes the machine or computer to perform a method for linking data records across datasets in accordance with exemplary embodiments of the present invention and to the computer-executable code itself. The machine-readable or computer-readable code can be any type of code or language capable of being read and executed by the machine or computer and can be expressed in any suitable language or syntax known and available in the art including machine languages, assembler languages, higher level languages, object oriented languages and scripting languages. The computer-executable code can be stored on any suitable storage medium or database, including databases disposed within, in communication with and accessible by computer networks utilized by systems in accordance with the present invention and can be executed on any suitable hardware platform as are known and available in the art including the control systems used to control the presentations of the present invention.

[0037] While it is apparent that the illustrative embodiments of the invention disclosed herein fulfill the objectives of the present invention, it is appreciated that numerous modifications and other embodiments may be devised by those skilled in the art. Additionally, feature(s) and/or element(s) from any embodiment may be used singly or in combination with other embodiment(s) and steps or elements from methods in accordance with the present invention can be executed or performed in any suitable order. Therefore, it will be understood that the appended claims are intended to cover all such modifications and embodiments, which would come within the spirit and scope of the present invention.