restricting to appropriate ranges of values along each dimension), the data becomes homogeneous enough to analyze, addressing the first challenge. In this context, we call each such cell a *segment* (as in segmented modeling). In our experience, analyzing appropriate features associated with various entities of interest instead of directly analyzing the events themselves helps address the second challenge.

**Monitoring.** The second component of the framework is a monitor that:

1. monitors streams of event based data

2. computes summary or state information,

3. uses this information as input to statistical measures and models

4. compares the outputs of the measures and models to previously computed baselines, and

5. issues alerts in case of statistically significant deviations.

The goal of monitoring is to determine *whether* a statistically significant change has occurred. In other words, rather than starting with a certain expectation of data or information quality, the approach is to detect as quickly as possible changes in data or information quality, addressing the third challenge.

**Root Cause Analysis.** The third component of the framework is a process for exploring the monitored data to understand casual relationships between data and defined outcome variables. A variety of techniques can be used to understand causality, including contingency tables [1], discriminant analysis, regression, and classification and regression trees [13]. The challenge is to understand whether different variables are causally related or simply correlated.

Here is a simple example from the analysis of payments card transactions: The decline rate of transactions is an outcome variable that has obvious business significance. Some declines are due to insufficient funds or fraudulent usage, while others are due to data quality problems. Errors in how a merchant processor sets up an e-commerce system can lead to hidden data quality problems and higher than usual declines. The role of the root cause analysis process is to understand some of the casual reasons for statistically significant changes in baselines. In other words, the goal of root cause analysis is to determine *why* something has happened.

**Amelioration.** Once one or more root causes are identified, the goal of the fourth component of the framework is to take actions to ameliorate the problems. In the example, above this may involve educating the merchant processor so that the identified data quality problems do not occur in the future.

In our experience, data quality problems for complex distributed systems are often the result of documentation that is hard to understand or difficult to interpret. We have been exploring the use of model driven architecture [7] to provide formal business and technical reference models and methods that can directly address this difficulty.

In this paper, we describe this framework and provide some high level experiences of some of the implementations we have done.

Although monitoring, causal analysis and amelioration are components for several different data and information quality methodologies [6], [14], [15], as best as we can tell from reading the literature, our paper makes the following contributions:

1. Most data and information quality methodologies [14], [17], [15] do not distinguish carefully between transaction or event data and summary or profile data that is aggregated from it. This is an important distinction for our targeted applications. As a simple example, the data and information quality issues are quite different for payments card transactions and summary information at the merchant, account, issuer, or acquirer level.

2. A common approach to data and information quality is to measure the quality of data along several dimensions. For example, accuracy, completeness, validity, timeliness, etc. (see, for example, [20]). In contrast, our focus is not on the dimensions themselves but on effective procedures for creating small cells or segments of data (defined by dimensional ranges) that have both business and statistical significance and building effective baselines for each cell. For example, we view data for a transaction process as being naturally divided into cells by logical entity (issuer, acquirer, type of payments card or payment product) and temporal entity (weekday, holiday, weekend, etc.)

3. Our methodology is closely tied to standards, in particular, the Predictive Model and Markup Language or PMML, that dominant standard for statistical and data mining models. This has several important implications. In particular, this allows us to instantiate a data quality in a standards based fashion as an XML file.

## 2. RELATED WORK

There is now quite a bit of research in the field of data and information quality, and several books [18] and [3]. In this section, we briefly discuss some of the research that is most directly relevant.

Our approach to data and information quality is statistical. This tradition goes back at least to Deming [4]. In particular, our focus is on establishing baselines and measuring statistically significant deviations from baselines. This is a standard approach in change detection [2]. In contrast, many approaches for data and information quality are business systems or engineering based (see for example, [14] or [18]).

Once deviations from baselines are detected, a statistical analysis is undertaken to try to determine the underlying reasons. Today, there are a wide variety of approaches for trying to determine causality, including root cause analysis [19], contingency tables [1], discriminant analysis, regression, and classification and regression trees [13].

A common approach to data and information quality is to measure the quality of data along several dimensions. For example, DOD Guidelines recommend using accuracy, completeness, consistency, timeliness, uniqueness and validity. As another example, Strong et. al. [20] introduce 16 dimensions organized into four categories (intrinsic information quality, contextual information quality, representational informational quality, and accessibility information quality).
In this note, we use some, but not all, of these standard dimensions. In particular, most of the work described below are based on metrics measuring completeness, consistency, and validity.

In this note we distinguish formally between input events and persistent states. Although this is standard in dynamical systems, automata theory, and control theory, but does not appear to be a standard approach in statistics or data mining [11].

Most data and information quality methodologies [14], [17], [15], [6] include components for defining, measuring, analyzing, and improving data and information quality issues, as our does. On the other hand, the approach sketched below differs in two significant ways from [14], [17], [15], [6] and related work:

1. Our approach is closely tied to standards based architectures. As many approaches do today, we employ a data warehouse. In addition, we employ a monitor for monitoring streaming data, a component for building baselines, and a scoring engine [12] for measuring the deviation of the streaming data from the baseline.

2. Second, our approach is closely tied to standards for data mining and statistical models [10] and [5], such as the XML-based Predictive Model Markup Language.

### 3. EXAMPLES

We have applied the framework described here to several examples, including those involving payments card transactions, highway traffic data, and multi-modal sensor data. In this section, we provide a bit of background for two of these examples in order to make this note more self contained.

Here is a simplified description of some of the steps involved in a payments card transaction.

1. A cardholder (the card has an account number) purchases an item at a merchant.

2. The merchant has a relationship with a bank called the acquiring bank, which agrees to process the payments card transactions for the merchant. The acquiring bank provides the merchant with a terminal or other system to accept the transaction and to process it.

3. The acquiring bank has a relation with financial payment system, such as those operated by Visa, MasterCard, Discover, etc. The transaction is processed by the acquiring bank and passed to the payment system.

4. The payment system the transaction and passes the transaction to the bank that issued the payments card to the card holder (the issuing bank). In other words, one of the essential roles of the payment system is to act as an intermediary between the acquirer and the issuer.

5. The issuing bank processes the transactions and determines if there are sufficient funds for the purchase, if the card is valid, etc. If so, the transaction is authorized; the transaction can also be declined, or a message returned asking for additional information. In each of these cases, the path is reversed and the transaction is passed from the issuing bank back to the payment system, from the payment system back to the merchant bank, and from the merchant bank, back to the merchant.

One of the challenges of a problem like this is to monitor in real time data and information quality problems for the various different parties when the data is processed transaction by transaction. Our approach is to use event based processing model and to create different summary or feature vector for each entity of interest. In this case, this includes the cardholder, the merchant, the acquirer, the issuer, and the payment system.

As another example, consider the problem of understanding highway traffic congestion. The Gateway System employs over 800 sensors to collect volume, speed, and occupancy data in a three state, fifteen county Gary-Chicago-Milwaukee (GCM) corridor [16]. The Pantheon Gateway Testbed augments this data with data about weather, special events that may affect highway conditions, and related information.

Here is a question that can be posed using this data: On a Monday, around 7 am, that is not a holiday, and when it is beginning to rain lightly, what is the average speed and volume for traffic on Interstate - 290 near the Austin exit? What will the average speed and volume be around 8 am if the rain continues?

This is an important motivating question and suggests our approach. Rather than try to understand data and information quality problems for the system as a whole, our approach is to divide the data into relatively homogeneous segments or cells (such as traffic on Mondays around 7 am with light rain) and to establish appropriate baselines for each such segment. With this knowledge, understanding data and information quality problems becomes much easier.

### 4. OVERVIEW

Broadly speaking, our technical approach is as follows:

1. We assume that data consists of events, such as transactions or sensor readings. Events are first divided into segments or cells that are relatively homogeneous. An event can be associated with multiple segments. Of course, there are many different ways of doing this and a discussion of these is outside the scope of this paper.

2. For each segment, events are processed to update state or feature vectors containing persistent features associated with the events. This is described in more detail in the section below.

3. For each segment, appropriate baselines are established for collections of state or feature vectors. Baselines may be temporal, geospatial, logical, or some combination. Determining good break points for dimensions appears to be a difficult problem and is outside the scope of this paper.

4. Deviations from baselines are detected using simple threshold models or more complex change detection models [2]. Deviations are used to determine as quickly as possible whether something has changed.

5. Separately, casual analysis is used to determine whether conditions or combinations of conditions are likely to
effect outcome or impact variables. To begin n by m contingency tables are used as a starting point for this analysis [1]. This is supplemented as required by discriminant analysis, linear regression, and nonlinear regression techniques, such as classification and regression trees [13].

6. When important casual conditions are identified, formal models [7] are used to begin to improve the condition. The use of formal models for this purpose is also outside the scope of this paper.

## 5. EVENT BASED DATA PROCESSING

It is useful when developing baselines to distinguish between data and derived attributes following [5].

A data attribute is simply an attribute present in the data itself, while a derived attribute is an attribute derived from the data or aggregations of the data. For example, given a payments card transaction the raw amount of the transaction is in the data itself, while currency related attributes, interchange fees, the amount of transactions for an account holder during the past hour, the number of declined transactions that are e-commerce-related, etc. are all examples of derived attributes.

In this note, we follow an event based approach to analyze information [11]. We assume that we are given:

* A stream of events $\alpha_1, \alpha_2, \dots$ in $\mathbf{R}^m$. Attributes in the events are data attributes.

* A finite collection $\xi$ of feature vectors (also called state vectors)

$$ \xi = \{x_1, x_2, \dots, x_n \in \mathbf{R}^N\}. $$

* An update rule (denoted dot) specifying how an event $\alpha$ updates the collection of feature vectors

$$ \xi' = \alpha \cdot \xi. $$

Attributes in the feature or state vectors consist of derived attributes formed from the event data through transformations and aggregations.

* A function of the state space

$$ f: \mathbf{R}^N \to \mathbf{R}^1 $$

representing a statistical or data mining model producing scores or other outputs.

We illustrate this using our running example of payments card transactions. In this case, the events are payments card transactions, while the state vector represents information associated with a related entity, such as a payments card or issuing bank. For example, if the state vector represents a payments card transaction, the a component of the state vector might be the number of transactions during the previous 60 minutes. If the state vector represents an issuing bank, then a component of the state vector might be the number of declined transactions during a day. In both cases, the model might be a change detection model indicating that the observed feature is statistically different than a previously computed baseline level.

For another example, assume that events consist of sensor readings for a collection of sensors and that there is a

feature vector for each sensor that maintains the number of readings, the average of the readings, the min sensor reading, and the maximum sensor reading for each sixty minute period, for each of the 168 = 7 × 24 sixty minute periods during a seven day week. Here the update rule, updates the features corresponding to the appropriate sixty minute period.

## 6. BASELINE MODELS

In this section, we review a standard approach for detecting deviations from baselines [2]. In the methodology described here, this is applied to each segment or cell separately. We assume that one have mean and variances representing normal behavior and behavior that is not normal.

More explicitly, assume we have two Gaussian distributions with mean $\mu_i$ and variance $\sigma_i^2$, $i = 0, 1$.

$$ f_i(x) = \frac{1}{\sqrt{2\pi}\mu_i} \exp \frac{-(x - \mu_i)^2}{2\sigma_i^2} $$

The log odds ratio is then given by

$$ g(x) = \log \frac{f_1(x)}{f_0(x)}. $$

and can now define a CUSUM algorithm as follows [2]:

$$ Z_0 = 0. $$

$$ Z_n = \max\{0, Z_{n-1} + g(x_n)\}. $$

Streaming data is compared to existing baseline data and deviations are noted and flagged for investigations. Baseline models like these are used to determine whether something has changed, and, if so, when it changed.

Baseline models aggregate data along several dimensions (in the running example of payments card transactions, baseline models aggregate data by issuer, acquirer, region, temporal period, type of transaction, etc.) At too high a level of granularity, too much information is lost. At too fine a level of granularity, it is too difficult to discern what is important.

For example, it is important to know that the overall authorization rate is 93%, but this doesn't easily lead to actions that improve the authorization rate. On the other hand, knowing that the authorization rate for transactions with inconsistent point of sales data is 20% higher than the average provides some very important information. The challenge with baseline models is to choose the right of level of granularity so that the baselines are meaningful and can uncover opportunities for improvement. From this perspective, advanced baseline models can dive down into the data to uncover homogeneous pockets of data and establish appropriate baselines for each pocket.

The Predictive Model Markup Language or PMML is an XML based language to describe statistical and data mining models. As part of the work described here we have produced PMML models for baselines and to detect deviations from baselines. Using the terminology of [5], an application that produces baselines is a PMML producer and an application that monitors baselines is a PMML consumer.

## 7. ROOT CAUSE ANALYSIS

Different applications structure the root cause analysis differently. For example, when analyzing payment data the current approach consists of two steps:
1. In the first step, the relation between different conditions and different outcome or impact variables is examined using to generate alerts, together with confidence levels. The goal of this step is to provide an initial identification of conditions that are correlated with variables of business interest.

2. In the second step, an investigation is undertaken involving subject matter experts to explore the relationship and to determine whether the relation is casual, and, if so, to estimate its business impact.

We now briefly describe each of these steps in the running example of payments card transactions.

A simple way to analyze data is to use data and derived attributes to define conditions and then to examine the relation between the conditions and certain outcomes using contingency tables [1]. Recall that contingency tables capture the relation of two categorical variables. See the Table below for a simple example. In addition to contingency tables, we currently beginning to explore multivariate techniques, such as discriminant analysis or classification trees [13] to generate alerts.

Alert conditions are defined by specifying values or ranges of values for data or derived fields. Defining binary indicator variables is a very simple way of defining conditions. Here is a simple example. A transaction has a field indicating that it is e-commerce related. For example, an indicator attributed can be defined by defining a condition to be 1 if the transaction is e-commerce related in this sense and 0 otherwise. As another example, a payments card transaction also has a field indicating the type of merchant. An indicator variable can be defined if the type of merchant is a casino and 0 otherwise. More complex types of conditions can also be defined. For example, conditions with three, four or more different values can also be defined. Conditions defined in these ways are examples of statistical factors.

Outcome and impact attributes can be data attributes, but are generally derived attributes. Examples include a binary variable indicated whether a financial transaction is approved or not. As another example, a binary indicator variable indicating whether a transaction is cleared, or whether or not a transaction is associated with a charge back or not.

<table><caption>Table 1: A 2x2 contingency table that is sometimes a helpful step in the root cause analysis of alerts.</caption><thead><tr><th></th><th>Outcome - State 1</th><th>Outcome - State 2</th></tr></thead><tbody><tr><td>Alert Condition Present</td><td>n<sub>11</sub></td><td>n<sub>12</sub></td></tr><tr><td>Alert Condition Not Present</td><td>n<sub>21</sub></td><td>n<sub>22</sub></td></tr></tbody></table>

In addition to baseline models, our framework also uses more complex statistical to help determine what conditions and combination of conditions are likely to result in certain outcomes, such as a decrease in authorizations. In conjunction with this, our framework also employs an investigative process involving subject matter experts to help determine why an outcome variable (such as the approval rate or charge back rate) has changed and if so what the impact is? We call these casual models.

## 8. STATUS

To date, we have undertaken several projects using this methodology. Here we give a brief summary of the status of two of these.

**Payments card transactions.** We have begun to analyze data and information quality problems associated with declines for a large financial transaction processor. The status is as follows: some measures for incomplete, invalid, and inconsistent fields have been developed. Using this measures, we are currently developing baselines and identifying combinations of conditions capturing common data and information quality problems. We are also examining casual relations between these conditions and impact variables, such as the rate of declines. Finally, preliminary business and technical reference models for some of the more important fields have been developed [7].

**Highway traffic data.** The Gateway System collects near real time data from over 800 highway traffic sensors covering the three state, fifteen county Gary-Chicago-Milwaukee (GCM) corridor. This data is archived by the Pantheon Gateway Project [16] and overlaid with data about special events, such as concerts or sports events, and data about the weather. In addition, data about accidents is collected. Using this data, we have established preliminary baselines used a real time scoring engine employing PMML-based change detection models to detect statistically significant changes from these baselines. To date, CUSUM-based and threshold based change detection models [2] have been developed and deployed. Currently, casual models using tree-based classifiers are being developed to try determine semi-automatically whether deviations from baselines are due to chance, unusual weather, special events, or accidents.

Publicly available data and information about the first projects is rather limited due to its confidential nature. On the other hand, data for the third project is publicly available from the web site [16].

## 9. CONCLUSION

In this note, we have introduced a framework consisting of four steps that can help identify and ameliorate data and information quality problems for complex, distributed systems.

Our assumption is that the data is event based and heterogeneous. In a preliminary step, we divide the data into more homogeneous cells or segments and aggregate the data into feature or summary vectors attached to entities of interest.

1. The first component statistically analyzes each segment and produces a baseline.

2. The second component monitors the event stream in real time and compares computed quantities of each interest in each segment to historical baselines. Deviations result in request for an investigation (an alert). This component detects whether something has happened.

3. The third component is a root cause analysis which seeks to identify the root cause of each alert. This involves subject matter experts. This component determines why something has happened and, if so, what its impact is.
4. The fourth component employs formal models [7] to reduce the likelihood that similar problems will happen in the future.

This framework has been applied in several different domains. In this paper, we discussed two of these: understanding data and information quality problems for payments card transactions and for highway traffic data.

## 10. REFERENCES

[1] Alan Agresti, An Introduction to Categorical Data Analysis, John Wiley and Sons, Inc., New York, 1996.

[2] M. Basseville and I. V. Nikiforov. Detection of Abrupt Changes: Theory and Application. Prentice Hall, 1993

[3] Tamraparni Dasu and Theodore Johnson, Exploratory Data Mining and Data Cleaning, Wiley, 2003.

[4] W. Edwards Deming, Elementary Principles of the Statistical Control of Quality: A Series of Lectures, JUSE, Tokyo, 1952.

[5] Data Mining Group, The Predictive Model Markup Language, Version 3.0, retrieved from www.dmg.org on March 20, 2005.

[6] DOD Guidelines on Data Quality Management (Summary), retrieved from tricare.osd.mil/rm/documents/fa/DoDGuidelinesOnDataQualityManagement.pdf on March 20, 2004.

[7] David S. Frankel, Model Driven Architecture, Wiley Publishing Inc., Indianapolis, 2003.

[8] Glenn W. Goodman Jr., Taming the River of Data: New Software Tools Fuse Intelligence From Many Sources, Defense News, March 14, 2005.

[9] Robert L. Grossman, H. Bodek, D. Northcutt, and H. V. Poor, Data Mining and Tree-based Optimization, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, E. Simoudis, J. Han and U. Fayyad, editors, AAAI Press, Menlo Park, California, 1996, pp 323-326.

[10] Robert Grossman, Mark Hornick, and Gregor Meyer, Data Mining Standards Initiatives, Communications of the ACM, Volume 45, Number 8, 2002, pages 59-61

[11] Robert L. Grossman and R. G. Larson, An Algebraic Approach to Data Mining: Some Examples, Proceedings of the 2002 IEEE International Conference on Data Mining, IEEE Computer Society, Los Alamitos, California, 2002, pages 613-616.

[12] Robert L. Grossman, Alert Management Systems: A Quick Introduction, in Managing Cyber Threats: Issues, Approaches and Challenges, edited by Vipin Kumar, Jaideep Srivastava, Aleksandar Lazarevic, Kluwer Academic Publisher, 2004.

[13] Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, Springer, New York, 2001.

[14] Yang W. Lee, Diane M. Strong, Beverly K. Kahn, Richard Y. Wang, AIMQ: A Methodology for Information Quality Assessment, Information and Management, December 2002, Volume 40, Issue 2, pages 133-146.

[15] Ken Orr, Data Quality and Systems, Communications of the ACM, Volume 41, Number 2, 1998, pages 66-71.

[16] Pantheon Gateway Testbed, retrieved from highway.ncdm.uic.edu on March 20, 2005. (A SVG plug in for your browser is required to see the map.)

[17] Leo L. Pipino, Yang W. Lee and Richard Y. Wang, Data Quality Assessment, Communications of the ACM, Volume 45, Number 4, 2002, pages 211-218.

[18] Thomas C. Redman, Data Quality: The Field Guide, Digital Press, Boston, 2001.

[19] James J. Rooney and Lee N. Vanden Heuvel, Root Cause Analysis for Beginners, Quality Prgoress, 2004, pages 45-53.

[20] D. M. Strong, Y.W. Lee and R.Y. Wang, Data Quality in Context, Communications of the ACM, Volume 40, Number 5, 1997, pages 1030-110.

[21] Shawn Turner, Defining and Measuring Traffic Data Quality, Proceedings of the Traffic Data Quality Workshop, Washington, DC, December 31, 2002.
<figure><img src="image_28.png" /><figcaption>Figure 1: We have applied the framework described here to detect real time deviations from baselines from multi-modal highway data collected from over 800 highway traffic sensors in the greater Chicago region.</figcaption></figure>
# Exploiting relationships for object consolidation*

Zhaoqi Chen Dmitri V. Kalashnikov Sharad Mehrotra

Computer Science Department
University of California, Irvine

## ABSTRACT

Data mining practitioners frequently have to spend significant portion of their project time on data preprocessing before they can apply their algorithms on real-world datasets. Such a preprocessing is required because many real-world datasets are not perfect, but rather they contain missing, erroneous, duplicate data and other data cleaning problems. It is a well established fact that, in general, if such problems with data are not corrected, applying data mining algorithm can lead to wrong results. The latter is known as the “garbage in, garbage out” principle. Given the significance of the problem, numerous data cleaning techniques have been designed in the past to address the aforementioned problems with data.

In this paper, we address one of the data cleaning challenges, called *object consolidation*. This important challenge arises because objects in datasets are frequently represented via descriptions (a set of instantiated attributes), which alone might not always uniquely identify the object. The goal of *object consolidation* is to correctly consolidate (i.e., to group/determine) all the representations of the same object, for each object in the dataset. In contrast to traditional domain-independent data cleaning techniques, our approach analyzes not only object features, but also additional semantic information: *inter-objects relationships*, for the purpose of object consolidation. The approach views datasets as attributed relational graphs (ARGs) of object representations (nodes), connected via relationships (edges). The approach then applies graph partitioning techniques to accurately cluster object representations. Our empirical study over real datasets shows that analyzing relationships significantly improves the quality of the result.

## 1. INTRODUCTION

Nowadays data mining techniques are widely used to analyze data for scientific applications and business decision

*RelDC project (http://www.ics.uci.edu/~dvk/RelDC)

†This work was supported by NSF grants 0331707, 0331690

making. To build proper models and compute accurate results it is important that analyzed datasets are accurately represented and interpreted. Many real-world datasets however are not perfect, they frequently contain various data cleaning issues such as incomplete, erroneous and duplicate data, which need to be addressed before data mining techniques can be applied. As a result, data mining practitioners frequently spend significant effort on preprocessing of data to address cleaning issues that exist in their datasets, to ensure high quality of the results.

In this paper, we address one common data cleaning challenge known as *object consolidation* [7, 19, 21, 30]. It arises most frequently when the dataset being processed is constructed by merging various data sources into a single unified database, such as by crawling the web. In many real-world datasets objects/entities are not represented by unique identifiers, instead an object is represented by a *description* (a set of instantiated attributes), used in a certain *context*, which may lead to ambiguity. An object might have multiple different representations in the dataset and also an object representation, in general, might match the description of multiple objects instead of one. The goal of object consolidation is to correctly group all the representations that refer to the same object.

For example, consider a database that contains information about two people: 'John A. Smith' and 'John B. Smith'. Firstly, entity 'John A. Smith' might have multiple representations throughout the dataset: e.g., 'John Smith', 'J. Smith' 'John Smithx' (a misspelled representation). Secondly, representation 'J. Smith' can refer to both 'John A.' and 'John B.' Smith, so one representation matches the descriptions of multiple entities. Finally, the fact that there are only two 'John Smith''s in the dataset might not be known in general. Thus, for this example the goal is to determine that all 'John Smith' representations should be clustered into two groups and then assign them to groups such that all representations for 'John A. Smith' are in one group and for 'John B. Smith' in the other. Sometimes it is possible to infer more attributes/information from the *context* in which representations appear. For example, for 'J. Smith' used in a specific context, it might be known that the mentioned 'J. Smith' works at MIT. This context information can be potentially used to consolidate representations better.

Let us use an example to demonstrate the implication of applying data analysis techniques on datasets where the object consolidation problem is not resolved correctly. Consider the task of computing author impact in a citation network using a simple citation-count statistic. That is, the

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA

Copyright 2005 ACM 1-59593-160-0/05/06 ...$5.00.
task might be to compute the impact of ‘John A. Smith’ by
counting the number of citations of his publications. This
simple task might be more difficult than it seems due to the
problem with representations identified above. Notice, even
though the representations appear in some context, the in-
formation about the object available from the context might
be of a limited nature, which makes the object consolidation
task challenging. For instance, the only direct information
available about the authors, for some of the publications,
might be only their first initials and last names. Because
of such problems with representations, some of the papers
written by ‘John A. Smith’ might be wrongfully assigned
to other authors and some of the papers written by other
authors might be assigned to ‘John A. Smith’. Thus, the
impact of ‘John A. Smith’, computed on such a dataset, can
be very different from the real one.

While the object consolidation problem exists in differ-
ent domains, in this paper we will often use citation net-
works, like in the example above, to illustrate our domain-
independent approach.

The problem of object consolidation is related to the prob-
lem of record deduplication or record linkage [1, 10, 13, 19, 23]
that often arises when multiple tables (from different data
sources) are merged to create a single database. The causes
of record linkage are similar, i.e. differences in represen-
tation of objects across different datasets, entry errors, etc.
The difference between the two problems is that while record
linkage deals with records in a table, object consolidation
deals with entities/objects – a semantic concept of a higher
level. In record linkage it is often assumed that many at-
tributes are available in each record, which are very effec-
tively employed for deduplications. In object consolidation,
however, very few attributes can be available, thus making
the problem more challenging.

Another related problem is the problem of reference dis-
ambiguation [14, 18]. In the problem of reference disam-
biguation the goal is to match object representations with
the list of possible objects which is known in advance and
known to be clean. The requirement of having such a clean
list of objects limits the applicability of reference disam-
biguation. As a rule, each instance of the reference disam-
biguation problem can be formulated as an instance of the
object consolidation problem, while the reverse is not true.
That is, the object consolidation problem is more general.

Most of the traditional domain-independent data clean-
ing techniques belong to the class of feature-based similarity
(FBS) methods.<fnref n="1" /> To determine if two objects/records are
the same they employ a similarity function that compares
values of object/record attributes (features) for the purpose
of deduplication. The values of the attributes of an object
are typically derived from the object representation and the
context in which it is used. In this paper, we study a domain-
independent approach that utilizes not only features but also
additional semantic information present in datasets: inter-
object (chains of) relationships. For instance, ‘J. Smith’

might be used to refer to an author in the context of a par-
ticular publication. This publication might also have more
authors, which can be linked to their affiliated organizations
and so on, forming a web of entities inter-connected via rela-
tionships. The knowledge of relationships can be exploited
alongside attribute-based similarity resulting in improved
accuracy of object consolidation. Our approach is based on
the following hypothesis, which is referred to as the Context
Attraction Principle (CAP):

The CAP hypothesis:

* if two representations refer to the same entity, there is a high likelihood that they are strongly connected to each other through multiple relationships, implicit in the database;

* if two representations refer to different entities, the connection between them via relationships is weak, compared with that of the representations that refer to the same entity. ☐

Our approach views the underlying database as an at-
tributed relational graph (ARG), where nodes correspond
to object representations and edges correspond to relation-
ships. Our technique first uses feature-based similarity, to
determine if two representations can refer to the same ob-
jects. If, based on the FBS similarity, two representations
can refer to one object, then the relationships between those
representations are analyzed to measure the connection strength
between them. Graph partitioning techniques are then em-
ployed to consolidate the representations of objects based on
the FBS similarity and connection strength among them.

The **primary contributions** of this paper are:

* A novel object consolidation approach, which, unlike traditional techniques, employs not only attribute (feature) similarity, but also analyzes inter-object relationships to improve the quality of consolidation (Section 4).

* Novel metrics to analyze the quality of the outcome (Section 4.3).

* An empirical evaluation of the proposed technique, that establishes that analyzing relationships is important for object consolidation (Section 5).

Next, in Section 2, we present a motivational example and
then, in Section 3, we formalize the problem and introduce
the notation necessary to explain the approach.

## 2. MOTIVATING EXAMPLE

In this section we use an instance of the “author match-
ing” problem to illustrate that exploiting chains of relation-
ships, that exist among entities, can improve the quality of
object consolidation.

Consider a toy database consisting of the *author* and *pub-
lication* records shown in Figures 1 and 2. Assume that
the publications are represented in the database using the
attributes (id, title, authorRef1, ..., authorRefN), where
id is the paper identifier, title is the paper title, and
authorRef's are the names of the authors of the paper.
Suppose that the author information is stored in the form
(id, authorName, affiliation), where id is the author iden-
tifier, authorName and affiliation are the author's name
and affiliation.

<footnote n="1">¹For example, two strings ‘J. Smith’ and ‘John Smith’, while not identical, are sufficiently similar to suggest that one can be the other and FBS techniques can detect that. It can also be known from the context that the mentioned ‘J. Smith’ works at MIT and ‘John Smith’ works at MIT, then FBS approaches can use this additional attribute (affiliation) and suggest that they are now more confident that the two representations refer to the same person.</footnote>
<figure><img src="image_29.png" /><figcaption>Figure 1: Publication records</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>Figure 2: Author records</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Figure 3: Graph for toy database.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>Figure 4: Adding context info.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>Figure 5: Adding relshp analysis.</figcaption></figure>

We assume that in this database we are only uncertain about representations of *people*. For instance, we are uncertain to which author the representation ‘John Smith’ in the paper *P1* refers to: *A*₁, *A*₂, or *A*₃. For that matter, we are also uncertain, whether *A*₁, *A*₂, or *A*₃ are representations of different people, or they are just duplicate records. The latter can be the case, for instance, if ‘John Smith’ was a graduate student at MIT and then became a faculty at CMU, so *A*₁ and *A*₂ are duplicates in this scenario. However, under our assumptions, we are certain that the representation ‘MIT’ in *A*₁ is the same organization as the ‘MIT’ in *A*₂, because these two representations are of the type *affiliation*, and not of the type *people*.

**Traditional FBS techniques.** To solve this problem using traditional techniques one would first try to deduplicate *author* records. After that, those records would be assumed to uniquely represent each distinct author and the goal would be to match *authorRef*’s in *publication* records to the correct authors. For example, existing feature-based similarity techniques can be used to compare the description in each *authorRef* in *publication* records with the values of the *authorName* attribute in *authors* records. Using this technique we can accurately consolidate most of the representations for our toy database, except for the ‘John Smith’ representations. For example, the author represented as ‘Alan White’ in publications *P*1 and *P*2 will be mapped uniquely to the author record *A*4 for ‘Alan White’; ‘Mike Black’ in publications *P*2 and *P*3 will be correctly mapped to *A*5 and so on. The only difficulty will be with ‘John Smith’ and ‘J. Smith’ in *P*1, *P*3, and *P*4, since each of them can correspond to either *A*1, *A*2, or *A*3.

Let us note that we can visualize the resulting dataset as a graph. In this graph, each entity/object, as well as the not-yet-consolidated representations, become nodes. The relationships that exist among them are visualized as edges.

The graph for the toy database is illustrated in Figure 3. For instance, since author *A*₁ is affiliated with ‘MIT’, there is an edge between them, that corresponds to this relationship. Since, under our assumptions, ‘MIT’ uniquely identifies the corresponding entity, only one node is created for all ‘MIT’ representations. However, each ‘John Smith’ has a separate node in this figure.

**Employing context.** The most recent data cleaning

techniques, such as [7], are also capable of employing the *context* to improve the quality of cleaning. There might be additional context information (‘context attributes’) that such algorithms might be able to use.

For instance, if it is also known that the coauthor of *P*1, ‘Alan White’, is from ‘MIT’, then, given that *A*₁ is from ‘MIT’ as well, we may decide that ‘John Smith’ in *P*1 refers to *A*₁ and not to *A*₂ or *A*₃. As another example, if we already know that *A*₂ has papers with titles similar to that of *P*3, then we can infer that ‘J. Smith’ in *P*3 refers to *A*₂. The resulting dataset can be visualized as the graph illustrated in Figure 4, where *R*1, *A*₁, and *R*2, *A*₂ are shown to be merged into two nodes.

**Analyzing relationships.** Now we will show how additional semantic information, stored in the relationships that exist between entities, can help to improve the quality of cleaning even further.

*Observation 1: ('John Smith' in *P*1).* First, to handle author ‘John Smith’ in *P*1, we observe that his co-author ‘Alan White’ has also written a paper *P*2 with ‘Mike Black’, who in turn has a paper *P*3 with ‘J. Smith’. This gives us certain evidence that ‘John Smith’ in *P*1 is the same person as ‘J. Smith’ in *P*3. The intuition behind it is that people in the similar/related research areas tend to cooperate with each other and form co-authorship networks. Based on this evidence, we might decide that *P*1 and *P*3 are written by the same author, whose name is ‘John Smith’.

Recall, by using the context, we have determined above that ‘John Smith’ in *P*1 refers to *A*₁, and ‘J. Smith’ in *P*3 to *A*₂. Therefore, the evidence suggests that *A*₁ and *A*₂ are duplicate records for the same author – the fact that was not captured by the above feature-based similarity algorithm!

*Observation 2: ('John Smith' in *P*4).* Consider the task of deciding whether the representation ‘John Smith’ in *P*4 refers to *A*₁, *A*₂, or *A*₃. Observe that the coauthor of that paper, ‘Tom Grey’, has a paper *P*5 with ‘Kate Red’, who is at ‘Stanford’. The author *A*₃ is also at ‘Stanford’, and thus we are able to establish a connection between ‘John Smith’ in *P*4 and *A*₃. Given that there are no such connections to *A*₁ an *A*₂ that we can find, we might decide that ‘John Smith’ in *P*4 probably refers to *A*₃.

**Generic approach.** At first glance, the analysis in Observations 1 and 2 might seem to be domain-specific. How-
ever, a domain-independent approach emerges if we view the underlying database as a graph of object representations (modeled as nodes) linked to each other via relationships (modeled as edges). The analysis can be viewed as application of the CAP hypothesis to the toy database, represented as the graph in Figure 4.

The first observation we made, regarding R1 and R2 being two representations for the same author, was based on the presence of the path (we use ‘path’, ‘relationship chain’, and ‘connection’ interchangeably):

$$R1 \to P1 \to A4 \to P2 \to A5 \to P3 \to R2.$$

Via this path, we were able to ‘connect’ R1 and R2.

The second observation we made regarding disambiguation of ‘John Smith’ in P4 was based on the presence of the path

$$R3 \to P4 \to A6 \to P5 \to A7 \to \text{‘Stanford’} \to A3.$$

Via this path, we ‘connected’ R3 and A3.

Figure 5 shows the resulting graph, which reflects the outcome of the above analysis. In this figure, R1, R2, A1, and A2 are grouped together (forming the first group), since, those representations are likely to refer to the same person. Similarly, R3 and A3 are grouped as well, forming the second group. Let us observe that the graph in Figure 4 can be split into two connected subgraphs G1 and G2, such that G1 contains nodes of the first group and G2 of the second group.

In general, connections between representations can be more complex than those in this example. Therefore, a similar analysis may need to measure and compare the “strength” in the connections that exists between various entities.

Thus, the generic approach for object consolidation may consist of the following steps. First, the approach identifies the representations that can refer to the same entity. Then, it discovers connections between these representations and measures the connection strength between them to obtain the evidence to be used in the consolidation process. The algorithm then employs a graph partitioning algorithms to group the representations into clusters, such that the connections among the nodes in the same cluster are strong, and among the nodes across the clusters are weak, to satisfy the CAP principle.

Naturally, one should demonstrate that the CAP hypothesis holds over real datasets by designing a generic solution to exploiting relationships for object consolidation. We will develop one such general domain-independent strategy in Section 4. We perform an extensive study of the proposed approach over a real dataset, to establish that exploiting relationships can further improve the quality of object consolidation. Before we develop our solution, we first introduce the notation and concepts needed to explain the approach, in Section 3.

# 3. PROBLEM FORMULATION

## 3.1 Notation

Let $\mathcal{D}$ be the database being processed. We will use $O = \{o_1, o_2, \dots, o_{|O|}\}$ to denote the set of all entities (or, objects) in $\mathcal{D}$. ‘Entities’ here have the same meaning as in the E/R model. Various consolidation scenarios are possible w.r.t. $O$. In one scenario, the consolidation algorithm has some information about the objects in $O$ and about the

cardinality of $O$. A more complicated scenario is when no information about the number or the nature of the objects in $O$ is available.

Entities are referred in the database via representations. Let $X = \{x_1, x_2, \dots, x_{|X|}\}$ (where $|X| \ge |O|$) be the set of all representations in $\mathcal{D}$. A representation is a description of an entity, which may consist of one or more attributes. For instance, in the toy database in Section 2, authorRef representations consist of only one attribute (author name). If, besides author names, author affiliation were also stored in the publication records, then authorRef references would have consisted of two attributes – (author name, author affiliation).

Each representation $x_i$ semantically refers to a single specific entity in $O$, which we denote by $d[x_i]$, where $d[x_i]$, in general, is unknown to the consolidation algorithm. The goal is to group all the representations in $X$ into a set $C$ of $|O|$ non-empty clusters, $C = \{C_1, C_2, \dots, C_{|O|}\}$, such that all the representations in one cluster refer to the same entity, and no two representations from two different clusters refer to the same entity.<fnref n="2" /> That is, for any two representations $x$ and $y$ from the cluster $C_i$ it should follow that $d[x] = d[y]$. Similarly, for any two representations $x$ and $y$ from two distinct clusters $C_i$ and $C_j$, it should follow that $d[x] \neq d[y]$.

We will use $C[x_i]$ to denote the group set of $x_i$ – the set of all the representations from $X$ that refer to the same entity as $x_i$, and thus should be put into the same group with $x_i$: $C[x_i] = \{x_j \in X : d[x_j] = d[x_i]\}$. Similar to $d[x_i]$, the group set $C[x_i]$, in general, is unknown to the consolidation algorithm. Given this notation, the goal can be reformulated as determining $C[x_i]$ for each $x_i \in X$. Let $S[x_i]$ denote the consolidation set of $x_i$ – the set of all representations from $X$ such that $x_i$ and any representation from $S[x_i]$ can potentially refer to the same entity based on their feature-based similarity. That is, $S[x_i] = \{x_j : \text{sim}(x_j, x_i) > \tau\}$, where sim denote a feature-based similarity function and $\tau$ is some threshold. We assume that $C[x_i] \subseteq S[x_i]$.

To illustrate these concepts, consider the database in Table 1. It contains four representations of people: $x$, $x_A$, $x_B$, and $y$. Assume that those representation are not misspelled, and therefore $x_A$ and $x_B$ cannot refer to the same person, i.e. $d[x_A] \neq d[x_B]$. Suppose that $x$ and $x_A$ are representations of one person, $x_B$ is of another person, and $y$ is of a third person. Then the corresponding cluster sets and consolidation sets are shown in Table 1.

<figure><img src="image_34.png" /><figcaption>Figure 6: Similarity edges.</figcaption></figure>

Figure 6 graphically illustrate this example. In this figure, a node is created per representation and a similarity edge is created between two nodes only if the corresponding

<footnote n="2">²Notice, the goal is only to be able to accurately group representations, not to infer any information about the entities they represent, etc.</footnote>
<table><caption>Table 1: Example to illustrate the notation.</caption><thead><tr><th>Representations</th><th>C</th><th>S</th><th>S<sup>*</sup></th></tr></thead><tbody><tr><td>x = 'J. Smith'</td><td>C[x] = {x, x<sub>A</sub>}</td><td>S[x] = {x, x<sub>A</sub>, x<sub>B</sub>}</td><td>S<sup>*</sup>[x] = {x, x<sub>A</sub>, x<sub>B</sub>}</td></tr><tr><td>x<sub>A</sub> = 'J. A. Smith'</td><td>C[x<sub>A</sub>] = {x, x<sub>A</sub>}</td><td>S[x<sub>A</sub>] = {x, x<sub>A</sub>}</td><td>S<sup>*</sup>[x<sub>A</sub>] = {x, x<sub>A</sub>, x<sub>B</sub>}</td></tr><tr><td>x<sub>B</sub> = 'J. B. Smith'</td><td>C[x<sub>B</sub>] = {x<sub>B</sub>}</td><td>S[x<sub>B</sub>] = {x, x<sub>B</sub>}</td><td>S<sup>*</sup>[x<sub>B</sub>] = {x, x<sub>A</sub>, x<sub>B</sub>}</td></tr><tr><td>y = 'Alan White'</td><td>C[y] = {y}</td><td>S[y] = {y}</td><td>S<sup>*</sup>[y] = {y}</td></tr></tbody></table>

representations may refer to the same entity, as determined by their feature-based similarity.

In general, such a *virtual similarity graph* can be created for the set *X* of all the representations in *D*. Typically, this graph is composed of multiple *virtual connected subgraphs (VCS)*. To define the VCS for a representation *x*<sub>*i*</sub>, we first define the set of all the representations *S*<sup>*</sup>[*x*<sub>*i*</sub>] that belong to the same VCS as *x*<sub>*i*</sub>. The set *S*<sup>*</sup>[*x*<sub>*i*</sub>], consists of *x*<sub>*i*</sub> and each representation *y* ∈ *X*, such that there exist a path *x*<sub>*i*</sub> ~ *y*, consisting of only similarity edges. Notice that *C*[*x*<sub>*i*</sub>] ⊆ *S*[*x*<sub>*i*</sub>] ⊆ *S*<sup>*</sup>[*x*<sub>*i*</sub>], as illustrated in Table 1. For instance, the graph in Figure 6 consists of two VCS's: one with nodes {x, x<sub>A</sub>, x<sub>B</sub>} and the other one with node {y}.

The concept of a VCS is useful because the representations that belong to different VCS's cannot refer to the same entity. This allows us to cluster references in a “one VCS at a time” fashion.

## 3.2 The Attributed Relational Graph

Our consolidation approach views the database *D* as an undirected attributed relational graph (ARG) *G* = (*V*, *E*), where *V* is the set of nodes and *E* is the set of edges. ARGs are often utilized by various applications to represent the entities (nodes) in a dataset, connected via relationships (edges). The graph is called *attributed* because attributes can be associated with both the edges and nodes of such a graph. We use ARGs in a similar manner, as elaborated below.

**Nodes.** In real-world datasets all the representations can be divided into two categories: those for which consolidation is trivial and those for which this task requires extra processing. For instance, in the toy database all representations of *affiliations* can be trivially consolidated by applying feature-based similarity since this similarity was sufficient to uniquely identify each distinct entity. However, consolidation of certain *author* representations required an additional processing. For those cases where consolidation is trivial, the representations of the same entity are clustered, and a node is created per the resulting cluster of representations. For those cases where consolidation is not trivial, a node is created per representation. Figure 4 illustrates the resulting graph for the toy database from Section 2. Let us note that the way our approach creates nodes closely resembles the way they are typically created in ARGs – to represent distinct entities.

**Edges.** The approach handles two types of edges: *regular* and *similarity* edges. Regular edges connect representations of entities if they are related via relationships.<fnref n="3" /> For instance,

<figure><img src="image_35.png" /><figcaption>Figure 7: Virtual connected subgraph</figcaption></figure>

in the graph in Figure 3 in Section 2, edges connect all the representations of authors and the papers they have written. A *similarity* edge is created for each pair of representation that can refer to the same entity (based on feature-based similarity). Each similarity edge has a weight associated with it (a real number from [0,1] interval) which reflects the degree of similarity between the two representations based on their features. Similarity edges for the toy database are illustrated in Figure 7.

<figure><img src="image_36.png" /><figcaption>Figure 8: Graph Example</figcaption></figure>

**Representing nodes and edges graphically.** We will use solid lines to graphically represent regular edges and broken lines for similarity edges. Nodes that correspond to already consolidated clusters of representations will not have color; representations that are yet to be consolidated are represented as shaded nodes. So an ARG might look like the one illustrated in Figure 8. Notice how the similarity edges define the three distinct VCS's in this example.

## 3.3 Connection Strength

In Section 1, we discussed that the approach consolidates representations based on the CAP hypothesis. To achieve that, it utilizes the notion of *connection strength* between two representations *x* and *y*, denoted as *c*(*x*, *y*). This measure captures how strongly *x* and *y* are connected to each other via relationships. Many different models for computing *c*(*u*, *v*) have been proposed in the literature, and we will take up one of them in Section 4.1.

# 4. THE CONSOLIDATION ALGORITHM

We now have developed all the concepts and notation needed to explain our approach for object consolidation. The approach exploits both features and relationships for the purpose of consolidation, and outputs the resulting clus-

<footnote n="3">³We will concentrate primarily on binary relationships. Multiway relationships are rare and most of them can be converted to binary relationships [11]. Most of the design models/tools only deal with binary relationships, for instance ODL (Object Definition Language) supports only binary relationships.</footnote>
tering as the outcome. The approach consolidates representations using the following steps:

1. **Construct the ARG and identify all VCS's.** The first step is to construct the ARG for the dataset. We assume that feature-based similarity is used in constructing such a graph. This step has been explained in detail in Section 3.2.

2. **Choose a VCS and compute $c(u, v)$'s.** Pick a VCS in the ARG to be partitioned next. Then, compute the connection strength $c(u, v)$ for each pair of representations $u$ and $v$ in the VCS that are connected via a similarity edge.

3. **Partition the VCS.** Take, from Step 2, the VCS and the connection strength values. Use a graph partitioning algorithm to partition the VCS into clusters. The partitioning is carried out based on the connection strengths. After the VCS is partitioned, adjust the ARG accordingly. If the VCS was the last to be partitioned, then stop. Otherwise, go to Step 2.

We now discuss the above steps in more detail in the following subsections.

## 4.1 Computing Connection Strength

The connection strength measure $c(u, v)$ for two objects $u$ and $v$ computes how strongly they are connected to each other via relationships.

### 4.1.1 Existing models.

Recently, there has been a spike of interest by various research communities in the measures directly related to the $c(u, v)$ measure. Since the $c(u, v)$ measure is at the core of the proposed consolidation approach, we next analyze several principal existing models for computing $c(u, v)$.

**Diffusion Kernels.** The earliest work in this direction that we can trace is in the area of kernel-based pattern analysis [29]. The kernel methodology currently undergoes very active development, and shows a great promise for improving various pattern analysis tasks. In particular, this area studies 'diffusion kernels on graph nodes', which are of direct interest in our context and are defined as follows.

A base similarity graph $G = (S, E)$ for a dataset $S$ is considered. The vertices in the graph are the data items in $S$. The undirected edges in this graph are labeled with a 'base' similarity $\tau(\mathbf{x}, \mathbf{y})$ measure. That measure is also denoted as $\tau_1(\mathbf{x}, \mathbf{y})$, because only the direct links (of size 1) between nodes are utilized to derive this similarity. The base similarity matrix $\mathbf{B} = \mathbf{B}_1$ is then defined as the matrix whose elements $\mathbf{B}_{xy}$, indexed by data items, are computed as $\mathbf{B}_{xy} = \tau(\mathbf{x}, \mathbf{y}) = \tau_1(\mathbf{x}, \mathbf{y})$. Next the concept of base similarity is naturally extended to path of arbitrary length $k$. To define $\tau_k(\mathbf{x}, \mathbf{y})$, the set of all paths $P_{xy}^k$ of length $k$ between the data items $\mathbf{x}$ and $\mathbf{y}$ is considered. The similarity is defined as the sum over all these paths of the products of the base similarities of their edges:

$$ \tau_k(\mathbf{x}, \mathbf{y}) = \sum_{(\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_k) \in P_{\mathbf{xy}}^k} \prod_{i=1}^k \tau_1(\mathbf{x}_{i-1}, \mathbf{x}_i) $$

Given such $\tau_k(\mathbf{x}, \mathbf{y})$ measure, the corresponding similarity matrix $\mathbf{B}_k$ is defined. It can be shown that $\mathbf{B}_k = \mathbf{B}^k$. The

idea behind this process is to enhance the base similarity by those indirect similarities. For example, the base similarity $\mathbf{B}_1$ can be enhanced with similarity $\mathbf{B}_2$, e.g. by considering a combination of the two matrices: $\mathbf{B}_1 + \mathbf{B}_2$. The idea generalizes to more then two matrices. For instance, by observing that in practice the relevance of longer paths should decay, it was proposed to introduce a decay factor $\lambda$ and define what is known as the exponential diffusion kernel: $\mathbf{K} = \sum_{k=0}^{\infty} \frac{1}{k!} \lambda^k \mathbf{B}^k = \exp(\lambda \mathbf{B})$. The von Neumann diffusion kernel is defined similarly: $\mathbf{K} = \sum_{k=0}^{\infty} \lambda^k \mathbf{B}^k = (\mathbf{I} - \lambda \mathbf{B})^{-1}$. The diffusion kernels can be computed efficiently by performing eigen-decomposition of $\mathbf{B}$, that is $\mathbf{B} = \mathbf{V}'\mathbf{\Lambda}\mathbf{V}$, where the diagonal matrix $\mathbf{\Lambda}$ contains the eigenvalues of $\mathbf{B}$, and by making an observation that for any polynomial $p(x)$, the following holds $p(\mathbf{V}'\mathbf{\Lambda}\mathbf{V}) = \mathbf{V}'p(\mathbf{\Lambda})\mathbf{V}$. The elements of the matrix $\mathbf{K}$ exactly define what we refer to as the connection strength: $c(\mathbf{x}, \mathbf{y}) = \mathbf{K}_{\mathbf{xy}}$.

The solutions proposed for the diffusion kernels work well, if the goal is to compute $c(u, v)$ for all the elements in the dataset. They are also very useful for illustration purposes and similar in nature (though cannot be used “as is”) to the weight-based model we employ in our previous work [14, 17]. However, in data cleaning, the task is frequently to compute only some of $c(u, v)$'s, thus more efficient solutions are possible. Also, often after computing one $c(u, v)$, the graph is adjusted in some way, which affects the values of $c(u, v)$'s computed after that.

**Relevant importance in graphs.** White et al. in [33] consider the problem of computing 'relevant importance' of a set of nodes in a graph with respect to the set of 'root' nodes. The problem of computing $c(u, v)$ can be postulated as computing the relevant importance of node $u$ with respect to the root node $v$. In [33] several known techniques are evaluated for their goal. Basic techniques, such as the length of the shortest paths between $u$ and $v$, are compared against more involved ones, which are similar to the diffusion kernels. In the context of our problem, the work in [33] has an advantage over the work on kernels, because [33] focuses on efficient computation of one $c(u, v)$, whereas the kernel methods compute the whole similarity matrix $\mathbf{K}$.

**Electric circuit analogy.** Faloutsos et al. in [9] considers a model for computing $c(u, v)$. They view the graph as an electric circuit consisting of resistors, and compute $c(u, v)$ as the amount of electric current that goes from $u$ to $v$. One of the primary contributions of that paper is the optimizations that scale their approach to large graphs.

**Random walks in graphs.** Another common model used for computing $c(u, v)$ is to compute it as the probability to reach node $v$ from node $u$ via random walks in the graph. That model has been studied extensively, including in our previous work [14, 17].

**Problems with existing models.** In the context of data cleaning, the existing techniques have several disadvantages. One disadvantage is that the true 'base' similarity is rarely known in real-world datasets. Some existing techniques try to mitigate that by imposing a similarity model. However, the CAP principle implies its own similarity measure, and any imposed model, created for its own sake in isolation from the specific application, might have little to do with it. Ideally, the similarity measure should be derived directly from data for the specific application at hand that employs it. One step toward achieving this, is to consider parameterized models and then try to learn an optimal
combination of parameters directly from data. We have explored such an approach in [16] for the problem of reference disambiguation. Next we will present the $c(u, v)$ model we use in this paper for object consolidation. That model is parameterized, however in this paper we do not study how to learn the right parameters, but rather assume they are assigned by the domain analyst, as we will elaborate shortly. Let us note that our overall approach is independent from a particular $c(u, v)$ model, and a different model, e.g. [17], can be utilized for this purpose.

### 4.1.2 The connection strength model.

The $c(u, v)$ model we use is very similar to that of the diffusion kernels. To compute $c(u, v)$, the set of all L-short simple paths $\mathcal{P}_L(u, v)$ between u and v is analyzed, where a path is L-short if its length does not exceed L. The total connection strength between nodes u and v is computed as the sum of connection strengths of paths in $\mathcal{P}_L(u, v)$:

$$c(u, v) = \sum_{p \in \mathcal{P}_L(u, v)} c(p). \qquad (1)$$

The connection strength $c(p)$ of each individual path $p$ is computed the same way as in the kernel formulae: as a product of base similarities of edges.

The differences between the proposed model $\mathcal{M}$ and that of the kernels $\mathcal{M}_K$ are as follows. The model $\mathcal{M}_K$ employs the decay factor $\lambda$, whereas $\mathcal{M}$ does not. In $\mathcal{M}_K$, we have $L = \infty$, in $\mathcal{M}$ the parameter $L$ is finite, e.g. $L = 5$. In $\mathcal{M}_K$ all base similarities $\tau(u, v)$ are known, in $\mathcal{M}$ we will derive them in a particular way: the ultimate goal (not considered in this paper) is to eventually to be able to learn them directly from data.

The procedure for computation $c(u, v)$ consists of two logical phases. The first phase discovers connections/paths between u and v. The second phase computes/measures the strength in connections discovered by the first phase.

**The connection discovery phase.** In general there can be many connections between nodes u and v. Intuitively, many of those (e.g., very long ones) are not very important. To capture most important connections while still being efficient, the algorithm computes the set of all L-short simple paths $\mathcal{P}_L(u, v)$ between nodes u and v in graph G. This algorithm is the bottleneck of the overall approach. Several optimizations of this algorithms has been studied in [14,17], which achieve orders of magnitude in improvement. In this paper we employ the same optimizations.

The second phase computes the strength in the discovered connections using Equation (1). We are yet to specify how we compute the connection strength $c(p)$ of each individual path $p$ from $\mathcal{P}_L(u, v)$ in Equation (1). Let us address this issue.

**Motivating $c(p)$ formula.** Which factors should be taken into account when computing the connection strength $c(p)$ of each individual path $p$? Figure 9 illustrates two different paths (or connections) between nodes u and v: $p_a = u \to a \to v$ and $p_b = u \to b \to v$. Let us understand which connection is better.

Both connections have the same length of two. One connection is going via node a and the other via node b. The intent of Figure 9 is to show that node b “connects” many nodes, not just u and v, whereas node a “connects” only u and v. For instance, in the context of the author matching problem u and v can be two authors, a can be a publication

<figure><img src="image_37.png" /><figcaption>Figure 9: Motivating $c(p)$.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>Figure 10: $c(p)$.</figcaption></figure>

<caption>Figure 11: Experiments</caption>

and b a university, as illustrated in Figure 10. We argue the connection between u and v via b is much weaker than the connection between u and v via a: since b connects many nodes, it is not surprising we can connect u and v via b as well. Notice, measures such as path length, network flow do not capture the fact that $c(p_a) > c(p_b)$.

We compute $c(p)$ as follows. Let us assume first that path $p$ consists of only regular edges, and no similarity edges. All edges in the ARG can be classified into a finite set of types $T = \{T_1, T_2, \dots, T_m\}$. For example, for the author matching problem, type $T_1$ can be the edges that connect authors and publications, type $T_2$ can be the edges that connect authors and their affiliated organizations. So path $p_a$ in Figure 10 can be viewed as a $\langle T_1, T_2 \rangle$ path and path $p_b$ as a $\langle T_2, T_3 \rangle$ path. Each edge type $T_i$ has a weight $w_i$ (a real number from [0,1] interval) associated with it. The connection strength of path $p$ is computed as the product of weights associated with its edge types. For example, if path $p$ contains $n_1$ edges of type $T_1$, $n_2$ edges of type $T_2$ and so on, then $c(p)$ is computed as

$$c(p) = w_1^{n_1} w_2^{n_2} \times \dots \times w_m^{n_m}. \qquad (2)$$

**Assigning weights.** An important question is how those $w_i$ weights are determined. There are several methods to accomplish that, we will briefly discuss only two methods:

1. The weights are assigned by the domain analyst.

2. The weights are learned from data using a supervised learning algorithm.

The first case is straightforward: the domain analyst, who is well-familiar with the dataset and the nature of this algorithm, picks the appropriate weights. However, it is often desirable to minimize the participation of the analyst. Thus, in our ongoing work, e.g. [16], we address the second case, where the challenge is to learn the weights automatically, directly from training data, by employing a supervised learning algorithm. Ideally, that solution should lead to a self-tunable algorithm, which achieves the best quality of consolidation.

**Example.** Without loss of generality, let us assume the weights are assigned by a domain analyst. Then, in the context of our motivating example, taking into account the fact that connections via publications are more unique than those via universities, the analyst might decide that the following combination of weights is reasonable: $w_1 = \frac{1}{2}$ and $w_2 = \frac{1}{10}$. So $c(p_a) = w_1^2 = \frac{1}{4}$, $c(p_b) = w_2^2 = \frac{1}{100}$, and $c(p_a) > c(p_b)$.

**Paths with similarity edges.** Let us consider paths that can contain similarity edges. Recall that a similarity edge between nodes for two representation x and y denote the fact that there is a chance that x and y can refer to the same
<figure><img src="image_39.png" /><figcaption>Figure 12: Paths with/without similarity edges.</figcaption></figure>

entity. This edge has a weight $w_F$ associated with it, which reflects the degree of similarity between $x$ and $y$ based on their features: $w_F = sim(x, y)$. We will refer to this weight as the FBS weight.

Let us note that a path containing a similarity edge might not even exist in reality. For instance, in Figure 12(a) the path consists of only regular edges and we are confident it exists. However, the existence of the path in Figures 12(b) depends on whether R3 and A1 refer to the same entity or not. The same applies to R3 and A3 in Figure 12(c).

The simplest solution is not to consider paths that contain similarity edges at all. Another (heuristic) solution we use is to associate the same very small base weight $w_ε$ for all similarity edges. Then, compute the total weight $v_i$ of a similarity edge as a product of its FBS weight $w_F$ and the base weight $w_ε$: $v_i = w_F \times w_ε$. So, if path $p$ has $n_i$ edges of type $T_i$ ($i = 1, 2, ..., m$) and $k$ similarity edges with total weights $v_1, v_2, ..., v_k$, then $c(p)$ is computed as

$$c(p) = w_1^{n_1} w_2^{n_2} \times \dots \times w_m^{n_m} v_1 v_2 \times \dots \times v_k. \quad (3)$$

## 4.2 Consolidating objects by partitioning VCS's

To consolidate objects we need to partition the representations in each VCS. Each VCS contains representations of at least one object. If a representation of an object is contained in a VCS, then, by construction of VCSs, the rest of the representations of the same objects are contained in the same VCS. Two scenarios are possible. In one scenario, the knowledge of the number of objects contained in each VCS is available. In the other scenario, no such knowledge is available.

Assume we know that a given VCS contains the representations of exactly $k$ objects. Then, the VCS must be partitioned into exactly $k$ clusters. We need to consider all possible partitions of the VCS into $k$ clusters, which are feasible according to the similarity edges in the VCS. There might be several such partitions and we should choose the one that best satisfies the CAP principle. We try to achieve that by employing a min-cut algorithm proposed in [30]. The standard min-cut problem is defined as follows. Given a weighted graph $G = (V, E)$, the goal is to partition $V$ into two non-empty disjoint subsets $V_1$ and $V_2$, such that the total weight of the edges connecting the two parts, called the cut (i.e., the weight of $\{(u, v) \in E : u \in V_1; v \in V_2\}$), is minimized.

In our case, we partition $V$ into not 2, but $k$ subsets. The min-cut algorithm we employ [30] has two useful properties: (a) it utilizes a 'normalized' (to [0, 2] interval) cut; and (b) it achieves the goal of minimizing connections across clusters and maximizing connections inside clusters at the same time. The former property will later allow us to specify a single threshold per all VCS's, while the latter property is important to better satisfy the CAP principle.

**Defining weights for partitioning.** A min-cut algorithm uses weights $w(u, v)$ between nodes for partitioning.

The weights are defined as follows: if there is a similarity edge between $u$ and $v$ then $w(u, v) = c(u, v)$, otherwise $w(u, v) = 0$. Let us note that the formula for $w(u, v)$ can also include the feature-based similarity $sim(u, v)$, e.g. as a weighted sum: $w(u, v) = \alpha \times c(u, v) + (1 - \alpha) \times sim(u, v)$, $0 \le \alpha \le 1$. But we do not study this approach in this paper.

**Further partitioning.** Consider now the second scenario, where we do not know the number of objects in a given VCS. The algorithms handle this case by first partitioning VCS into two parts. Then, the algorithm decides whether to actually split the nodes into two clusters, or not. It achieves that by comparing the value of the resulting normalized cut $c$ against predefined threshold $\tau$. Currently, the value of $\tau$ is not yet learned from data, but rather is set by the domain analyst. If $c > \tau$, the two parts are still well inter-connected and the algorithm does not divide VCS further into two clusters. That means the algorithm assumes that all the representations in this VCS refer to a single real-world entity, and hence they should be grouped together in one cluster. On the other hand, if $c < \tau$, the algorithm repeatedly partition the resulting subgraphs until $c > \tau$. The resulting clustering of representations is returned as the final result of the algorithm.

## 4.3 Measuring the quality of outcome

The goal of object consolidation algorithms is to accurately group the representations of entities. However, consolidation algorithms can make mistakes, and thus the quality of the outcome should be quantified. Measures known as dispersion and diversity has been proposed before for this purpose [2].

**Dispersion.** We want the representations of the same entity to be clustered together in one cluster. The dispersion of a given entity captures the number of distinct clusters into which its representations are clustered. Therefore, the lesser the dispersion the better and the ideal dispersion is 1 for a given entity.

**Diversity.** We also want each cluster to contain representations of just one entity. The diversity of a given cluster captures the number of distinct entities whose representations are in this cluster. Similarly, the lesser the diversity the better and the ideal diversity is 1 for a given cluster.

**Problems with dispersion and diversity.** The dispersion and diversity do not always accurately reflect the quality of the outcome of object consolidation, although they are simple and easy to understand. Consider the following example. Assume a VCS to be partitioned is composed of $2n$ representations $a_1, a_2, ..., a_{2n}$ of entity $E_A$ and of $2n$ representations $b_1, b_2, ..., b_{2n}$ of entity $E_B$. The goal is to group them correctly and therefore the ideal result is the two clusters:

$$C_1 = \{a_1, a_2, ..., a_{2n}\},$$

$$C_2 = \{b_1, b_2, ..., b_{2n}\}.$$

The algorithm however can make mistakes and the resulting two clusters might be:

$$C_1 = \{a_1, a_2, ..., a_n, b_1, b_2, ..., b_n\},$$

$$C_2 = \{a_{n+1}, a_{n+2}, ..., a_{2n}, b_{n+1}, b_{n+2}, ..., b_{2n}\},$$

that is, half of the representations are misassigned. In another situation, the two clusters might be:

$$C_1 = \{a_1, a_2, ..., a_{2n-1}, b_{2n}\},$$
$$C_2 = \{b_1, b_2, \dots, b_{2n-1}, a_{2n}\},$$

that is, just one is misassigned for each cluster.

Obviously, the latter answer is better than the previous one. However, in both situations, since the representations of both $E_A$ and $E_B$ are scattered across two clusters, the dispersion of each of the two entities, $E_A$ and $E_B$, is 2. The diversity of each of the two clusters $C_1$ and $C_2$ is 2, since each cluster contains the representations of both $E_A$ and $E_B$. Therefore, the dispersion and diversity measures cannot distinguish the two situations in this case.

**Entropy-based quality measures.** We argue that the metrics known as entropy can be utilized to better capture the above situations. Entropy was first proposed by Shannon in his famous work [28] on the mathematical theory of communication.

The entropy of a discrete random variable $X$ reflects the degree of uncertainty associated with possible values of $X$. Let variable $X$ take values from set $\{x_1, x_2, \dots, x_n\}$ with the respective probabilities $p(x_1), p(x_2), \dots, p(x_n)$, where $p(x_i) \neq 0$ and $p(x_1) + p(x_2) + \dots + p(x_n) = 1$. Then the entropy of $X$, denoted $H(X)$, is defined as:

$$H(X) = \sum_{i=1}^{n} p(x_i) \log_2 \frac{1}{p(x_i)}$$

Entropy $H(X)$ attains its minimum value $H(X) = 0$, when there exists some $i$ such that $p(x_i) = 1$. In that situation there is no uncertainty associated with $X$: the value of $X$ is always $x_i$. On the other hand, $H(X)$ attains its maximum value in the most uncertain scenario: when all the values $x_1, x_2, \dots, x_n$ are equally likely, in which case $H(X) = \log_2 n$. Thus, $H(X) \in [0, \log_2 n]$.

**Entity entropy.** Assume that a certain entity $E$ has $m$ representations in the database, which are assigned to $n$ clusters $C_1, C_2, \dots, C_n$ by the algorithm. The assignment is such that $m_1$ representations are assigned to the cluster $C_1, m_2$ to $C_2$ and so on, such that $m_i \neq 0$ and $m_1 + m_2 + \dots + m_n = m$. To measure the spread of representations of $E$ over the clusters, we consider the fractions of all representations of $E$ assigned to each cluster $C_i$ ($i = 1, 2, \dots, n$): $p_i = \frac{m_i}{m}$. Then, using those fractions, we utilize entropy to quantify the spread of the entity's representations: $H(E) = \sum_{i=1}^{n} p_i \log_2 \frac{1}{p_i}$. Let us note that the dispersion for this case is always $n$. The lower the value of $H(E)$, the better. The ideal value is 0.

**Cluster entropy.** Similarly, we can define the cluster entropy. Assume that the algorithm assigns to a cluster $C$ exactly $m$ representations, that correspond to $n$ entities. Suppose that $m_1$ of them are representations of entity $E_1, m_2$ of $E_2, \dots, m_n$ of $E_n$, where $m_i \neq 0$ and $m_1 + m_2 + \dots + m_n = m$. Like in the case above, we consider fractions $p_i = \frac{m_i}{m}$ and then use them in entropy to quantify the spread of the cluster's representations: $H(C) = \sum_{i=1}^{n} p_i \log_2 \frac{1}{p_i}$. Let us observe that the diversity in this case is always $n$. The lower the value of $H(C)$ the better, the ideal value is 0.

**Example.** Consider the example above with the two clusters $C_1$ and $C_2$, and assume that $n = 10$. In the first situation, the entity entropy is:

$$H(E_A) = \frac{n}{2n} \log_2 \frac{1}{n/2n} + \frac{n}{2n} \log_2 \frac{1}{n/2n} = 1,$$

$$H(E_B) = 1,$$

$$\text{avg} = \frac{H(E_A) + H(E_B)}{2} = 1.$$

The cluster entropy is:

$$H(C_1) = \frac{n}{2n} \log_2 \frac{1}{n/2n} + \frac{n}{2n} \log_2 \frac{1}{n/2n} = 1,$$

$$H(C_2) = 1,$$

$$\text{avg} = \frac{H(C_1) + H(C_2)}{2} = 1.$$

In the second situation, the entity entropy is:

$$H(E_A) = \frac{2n-1}{2n} \log_2 \frac{1}{(2n-1)/2n} + \frac{1}{2n} \log_2 \frac{1}{1/2n} = 0.0703,$$

$$H(E_B) = 0.0703,$$

$$\text{avg} = \frac{H(E_A) + H(E_B)}{2} = 0.0703.$$

The cluster entropy is:

$$H(C_1) = \frac{2n-1}{2n} \log_2 \frac{1}{(2n-1)/2n} + \frac{1}{2n} \log_2 \frac{1}{1/2n} = 0.0703,$$

$$H(C_2) = 0.0703,$$

$$\text{avg} = \frac{H(C_1) + H(C_2)}{2} = 0.0703.$$

Let us observe that in contrast to the diversity and dispersion, the entropy-based measures do capture that the second partitioning is better than the first one, since $0.0703 < 1.0$.

# 5. EXPERIMENTAL EVALUATION

In this section, we experimentally study the proposed approach on a real dataset. We conducted the experiments on a 2GHz Pentium 4 machine with 1GB RAM. In the rest of this section, we first describe the dataset we use and then present the experiments that test the quality and the efficiency of the proposed technique.

## 5.1 RealMov Dataset

One of the dataset used in data cleaning research is the movies dataset, available from [34]. It is a real public-domain dataset. In this paper we refer to a processed version of it as 'RealMov'. RealMov contains entities of three types: movies (11,453 entities), studios (992 entities), and people (22,121 entities), which are stored in movies, studios and people tables respectively. The movies table contains multiple attributes, such as the title of a movie, the director, the producer, the studio producing the movie, the studio distributing the movie, etc. The studios table has attributes such as studio name, the founder of the studio, the year of foundation, etc. The people table contains attributes like a person's name, the date of birth, gender, etc. There is also a cast table storing all the actors of each movie.

This dataset contains five types of (regular) relationships: movie_
actor, movie_director, movie_producer, producingStu-
dio, and distributingStudio, which map movies to their ac-
tors, directors, producers, producing studios and distribut-
ing studios respectively. Figure 13 presents a sample graph
for RealMov dataset. Relationships movie_
actor, movie_director,
and movie_producer connect entities of type movies to enti-
ties of type people. Relationships producingStudio and dis-
tributingStudio connect entities of types movies and studios.

A clean version of this dataset is available, in which all en-
tities and relationships among them are accurately captured.
This will allow us to test the quality of various consolidation
techniques: by comparing their output against the true situ-
ation. Figure 13 shows a sample ARG for RealMov dataset.
Each entity is represented as a node, and each relationship
as an edge.

## 5.2 Quality experiments

Typically, two aspects of data cleaning algorithm are evaluated empirically: the quality of their outcome and their
<figure><img src="image_40.png" /><figcaption>Figure 13: Graph example for movie dataset</figcaption></figure>

efficiency. In this section, we study the quality of our approach on consolidating the representations of *director* entities. Let us note that the true mapping between the movies and their directors is available. Having this knowledge is the advantage of this dataset, since it will allow to compute the quality of various consolidation techniques.

**Constructing experiment data.** To test our approach, we will use a standard technique, commonly employed by data cleaning practitioners, e.g. in [4]: we introduce uncertainty/errors (in director representations) manually. The uncertainty will be introduced differently in different experiments, as explained next.

Assume that RealMov stores information about $d_1, d_2, ..., d_n$ director entities. We first choose randomly a fraction $\rho$ of those directors: all their representations will be made uncertain. Based on the typical degree of uncertainty in real-world dataset [17], we set $\rho$ to either 1%, 5%, 10%, 15%. Suppose that, say, the directors $d_1, d_2, ..., d_{10}$ were chosen. We will make uncertain all the representations that refer to them, whereas for the rest of the directors $d_{11}, d_{12}, ..., d_n$, all their representations will still uniquely identify the right director.

To achieve that, we group the “uncertain” directors $d_1, d_2, ..., d_{10}$ in some fashion, say in groups of two, e.g. $\{d_1, d_2\}, \{d_3, d_4\}, ..., \{d_9, d_{10}\}$. Then, we simulate the desired FBS uncertainty by changing all the representations of directors that belong to one group, such that each representation can refer to all directors in this group – if only the FBS similarity is utilized. For instance, assume that the dataset contains a representation $r_1$, which could only represent $d_1$. We modify $r_1$ such that it will fit the description of both, $d_1$ and $d_2$, – but will not fit the description of any other director. Such a constructed dataset is characterized by two types of parameters: $\rho$ and the sizes of those groups.

**Baseline methods.** To reflect how our approach would compare against FBS techniques, we construct two baseline methods: *Baseline 1* and *Baseline 2*. Recall that our algorithm is applied only to ‘tough’ cases – after the existing FBS methods have already been used to successfully consolidate many of the representations (e.g., those “certain” representations). We now only test the quality of consolidating those ‘tough’ cases, which cannot be disambiguated by FBS methods.

Given that FBS cannot be used further to distinguish between the representations, whereas we would like to compare our algorithm against at least simple solutions, we construct our baseline methods as follows.

* *Baseline 1 method* creates one cluster per each VCS and then assigns all the VCS's representations to this one cluster. That is, that method does not partition the VCS's further. This naïve method always achieves the ideal dispersion and entity entropy, because entities end up in just one cluster, as they should. However, if the VCS contains the representation of *m* objects, then the diversity of the cluster will be *m*, whereas the ideal diversity is 1.

* *Baseline 2 method* knows the statistics of how many director groups there are of size 2, of size 3, and so on. Based on this statistics, for a given VCS, it first selects the number of partitions to split this VCS into. It then creates that many clusters, and randomly assigns representations from the VCS to each cluster.

**Experiment 1.** In this experiment, we set $\rho = 1\%$ and the size of each group of directors to be 2. The results for $\rho = 5\%, 10\%$ and $15\%$ closely resemble those for $\rho = 1\%$ and thus omitted. For this experiment we also make our algorithm (and Baseline 2) aware that each resulting VCS must be partitioned into exactly two clusters.

Figure 14(c) and 14(d) show the average diversity and dispersion as we vary parameter $L$. Recall that we consider only $L$-short paths, or paths of length no greater than $L$. The results show that additional semantic information, stored in inter-object relationship, improves the quality of object consolidation. They also show that longer paths help improve the quality of the outcome.

Since Baseline 1 does not partition VCS's at all, each resulting cluster always contains representations of 2 entities, and thus the diversity is always 2. Also, since the nodes of the same entity are always grouped into the same cluster, the entity dispersion is always 1 (the ideal dispersion).

Compared to the diversity and dispersion, the entropy should more properly capture the composition of groups. Figures 14(a) and 14(b) show the average cluster- and entity-entropy, achieved by the consolidation approaches. Recall that the lower the entropy, the better, and that the ideal entropy is zero. The figures look similar to the figures for the diversity and dispersion.

**Experiment 2.** In this experiment, the size of each director group is not 2 as in the previous experiment, but chosen randomly as 2, 3, or 4 with equal probability. Also our approach now is not aware into how many clusters each VCS should be clustered but rather utilizes threshold $\tau$ to decide that, as discussed in Section 4.2.

Figure 15 studies the effects of $\tau$ on the quality of the output. When $\tau$ is small, the normalized cut of most partitions is greater than $\tau$, so the further partitioning is not carried out. Therefore, representations in each VCS are likely to be grouped into a small number of clusters and that is why the results closely resemble those of Baseline 1. On the other hand, large $\tau$ leads to creating many clusters for each VCS. This improves the cluster entropy, but the entity entropy becomes worse. So, there is a natural trade-off between the cluster entropy and entity entropy.

Figure 15(c) plots the cluster and entity entropy in one figure. Such a figure is useful for the analysts to pick the right value of $\tau$, such that the desired compromise between the values of cluster- and entity-entropies is achieved. Figures 15(d), 15(e), 15(f) are similar to Figures 15(a), 15(b), 15(c), but for the diversity and dispersion.
<figure><img src="image_41.png" /><figcaption>Figure 14: Experiments with various lengths of paths</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>Figure 15: Experiments with various thresholds</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>Figure 16: Execution time vs. database size.</figcaption></figure>

## 5.3 Efficiency

**Experiment 3.** This experiment tests the efficiency of the proposed approach. Figure 16 shows the execution time of RelCluster as a function of the fraction of movies from RealMov dataset, e.g. 1.0 corresponds to the whole RealMov dataset. The bottleneck of our approach is the algorithm for discovering all L-short simple paths. In [14] we study several optimizations of that algorithm, which improve the performance by 1–2 orders of magnitude. We employ the same optimizations in our implementation of RelCluster.

# 6. RELATED WORK

Many research challenges have been explored in the context of data cleaning: dealing with missing data, handling erroneous data, record linkage, and so on. The closest to the problem of object consolidation addressed in this paper is the problem of record linkage. The importance of record linkage is underscored by the large number of companies, such as Trillium, Vality, FirstLogic, DataFlux, which have developed domain-specific record linkage solutions.

Researchers have also explored domain-independent techniques, e.g. [1, 10, 13, 19, 23]. Their work can be viewed as addressing two challenges: (1) improving similarity function, as in [3]; and (2) improving efficiency of linkage, as in [4]. Typically, two-level similarity functions are employed to compare two records. First, such a function computes attribute-level similarities by comparing values in the same attributes of two records. Next, the function combines the attribute-level similarity measures to compute the overall similarity of two records. A recent trend has been to employ machine learning techniques, e.g. SVM, to learn the best similarity function for a given domain [3]. Many techniques have been proposed to address the efficiency challenge
as well: e.g. using specialized indexes [4], sortings, etc.

Those domain-independent techniques deal only with attributes. Only one existing approach [17] analyzes relationships in a fashion similar to that proposed in this paper. That approach, and the one proposed in this paper, are part of the Relationship-based Data Cleaning (RelDC) project [15] at UCI. However, [17] solves a different data cleaning challenge, called reference disambiguation. That problem is known to be a subproblem of the problem of object consolidation and the approach proposed in [17], in general, cannot be used to solve the problem addressed in this paper. That approach converts the cleaning task to solving a nonlinear programming problem whereas we employ partitioning techniques for data cleaning. Other researchers have also proposed using relationships for cleaning, but in a different fashion. In [1] Ananthakrishna et al. employ similarity of directly linked entities, for the case of hierarchical relationships, to solve the record deduplication challenge. In [18] Lee et al. develop an association-rules mining based method to disambiguate references using similarity of the context attributes: the proposed technique is still an FBS method, but [18] also discusses “concept hierarchies” which are related to relationships. Getoor et al. in [2] use similarity of attributes of directly linked objects, like in [1], for the purpose of object consolidation. However, applying that technique in practice on real-world datasets was identified as future work in that paper. In contrast to the above described techniques, our approach and [17] utilize the CAP hypothesis to automatically discover and analyze relationship chains, thereby establishing a framework that employs systematic relationship analysis for the purpose of cleaning.

# 7. CONCLUSION

In this paper, we have shown that analysis of inter-object relationships is important for object consolidation and have demonstrated one approach that utilizes relationships for this purpose. Our ongoing work [16] addresses the challenge of automatically adapting the proposed data cleaning techniques to datasets at hand, by learning how to weigh different connections directly from data, in an automated fashion. Solving this challenge, in general, not only makes the approach a plug-and-play solution, but also improves both the accuracy and efficiency of the approach as discussed in [16].

# 8. REFERENCES

[1] R. Ananthakrishna, S. Chaudhuri, and V. Ganti. Eliminating fuzzy duplicates in data warehouses. In VLDB, 2002.

[2] I. Bhattacharya and L. Getoor. Iterative record linkage for cleaning and integration. In DMKD Workshop, 2004.

[3] M. Bilenko and R. Mooney. Adaptive duplicate detection using learnable string similarity measures. In SIGKDD'03.

[4] S. Chaudhuri, K. Ganjam, V. Ganti, and R. Motwani. Robust and efficient fuzzy match for online data cleaning. In SIGMOD Conf., 2003.

[5] P. Christen, T. Churches, and J. X. Zhu. Probabilistic name and address cleaning and standardisation. The Australasian Data Mining Wshp, 2002.

[6] W. W. Cohen and J. Richman. Learning to match and cluster large high-dimensional data sets for data integration. In SIGKDD, 2002.

[7] X. Dong, A. Halevy, and J. Madhavan. Reference reconciliation in complex information spaces. In SIGMOD, 2005.

[8] M. G. Elfeky and V. S. Verykios. On search enhancement of the record linkage process. In KDD-2003 Wshp on Data Cleaning, Record Linkage, and Object Consolidation, 2003.

[9] C. Faloutsos, K. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In SIGKDD, 2004.

[10] I. Fellegi and A. Sunter. A theory for record linkage. Journal of the American Statistical Association, 64(328):1183-1210, 1969.

[11] H. Garcia-Molina, J. Ullman, and J. Widom. Database systems: the complete book. Prentice Hall, 2002.

[12] L. Gravano, P. Ipeirotis, H. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In VLDB01.

[13] M. Hernandez and S. Stolfo. The merge/purge problem for large databases. In SIGMOD, 1995.

[14] D. Kalashnikov and S. Mehrotra. Exploiting relationships for domain-independent data cleaning. SIAM SDM, 2005. ext. ver., http://www.ics.uci.edu/~dvk/pub/sdm05.pdf.

[15] D. V. Kalashnikov and S. Mehrotra. RelDC project. http://www.ics.uci.edu/~dvk/RelDC/.

[16] D. V. Kalashnikov and S. Mehrotra. Learning importance of relationships for reference disambiguation. UCI Technical Report RESCUE-04-23, Dec. 2004. http://www.ics.uci.edu/~dvk/RelDC/TR/TR-RESCUE-04-23.pdf.

[17] D. V. Kalashnikov, S. Mehrotra, and Z. Chen. Exploiting relationships for domain-independent data cleaning. In SIAM International Conference on Data Mining (SIAM SDM 2005), Newport Beach, CA, USA, April 21-23 2005.

[18] M. Lee, W. Hsu, and V. Kothari. Cleaning the spurious links in data. IEEE Intelligent Systems, Mar-Apr 2004.

[19] A. K. McCallum, K. Nigam, and L. Ungar. Efficient clustering of high-dimensional data sets with application to reference matching. In SIGKDD, 2000.

[20] M. Michalowski, S. Thakkar, and C. Knoblock. Exploiting secondary sources for automatic object consolidation. In KDD-2003 Wshp on Data Cleaning, Record Linkage, and Object Consolidation, 2003.

[21] A. E. Monge and C. P. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In SIGMOD Wshp on Research Issues on Data Mining and Knowledge Discovery, 1997.

[22] M. Neiling and S. Jurk. The object identification framework. In KDD-2003 Wshp on Data Cleaning, Record Linkage, and Object Consolidation, 2003.

[23] H. B. Newcombe, J. M. Kennedy, S. J. Axford, and A. P. James. Automatic linkage of vital records. Science, 130:954-959, 1959.

[24] H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity uncertainty and citation matching. In Advances in Neural Processing Systems 15. Vancouver, British Columbia:MIT Press, 2002.

[25] D. Quass and P. Starkey. Record linkage for genealogical databases. In KDD-2003 Wshp on Data Cleaning, 2003.

[26] L. D. Raedt and et al. Three companions for data mining in first order logic. In Relational Data Mining. Springer-Verlag, 2001.

[27] S. Sarawagi and A. Bhamidipaty. Interactive deduplication using active learning. In SIGKDD, 2002.

[28] C. E. Shannon. The Mathematical Theory of Communication. University of Illinois Press, 1949.

[29] J. Shawe-Taylor and N. Cristianni. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.

[30] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 2000.

[31] S. Tejada, C. A. Knoblock, and S. Minton. Learning domain-independent string transformation weights for high accuracy object identification. In SIGKDD, 2002.

[32] V. Verykios, G.V.Moustakides, and M. Elfeky. A bayesian decision model for cost optimal record matching. The VLDB Journal, 12:28-40, 2003.

[33] S. White and P. Smyth. Algorithms for estimating relative importance in networks. In SIGKDD, 2003.

[34] G. Wiederhold. www-db.stanford.edu/pub/movies/.
Blocking-Aware Private Record Linkage

Ali Al-Lawati

Penn State / CSE

allawati@cse.psu.edu

Dongwon Lee

Penn State / IST

dongwon@psu.edu

Patrick McDaniel

Penn State / CSE

mcdaniel@cse.psu.edu

ABSTRACT

In this paper, the problem of quickly matching records (i.e., record linkage problem) from two autonomous sources without revealing privacy to the other parties is considered. In particular, our focus is to devise *secure blocking* scheme to improve the performance of record linkage significantly while being secure. Although there have been works on private record linkage, none has considered adopting the blocking framework. Therefore, our proposed blocking-aware private record linkage can perform large-scale record linkage without revealing privacy. Preliminary experimental results showing the potential of the proposal are reported.

1. INTRODUCTION

The task of integrating similar databases populated at separate locations to improve data qualities and enable accurate data analysis is often restricted by heterogeneity in the data. Specifications of how data is represented differ across databases of different parties. For example, “penn state university” can appear as simply “penn state”, or as “The Pennsylvania State University”. The goal of *record linkage* [16] is to identify similar records with precision, thereby facilitating accurate pattern and data analysis. In record linkage, all data to be matched appears in its original form in the matching process. This is acceptable when the data is of little value or when participants are mutually trusting. However, it is inappropriate to reveal privacy of autonomous sources. The goal of *private record linkage* [7] is, thus, to identify similar records without revealing privacy to others [1]. Applications that demand such a private record linkage include the medical field where patient records must be shared among hospitals and institutions while the identity of the patients are sealed.

Given two data sources, X and Y, the most naive form
of record linkage is to perform pair-wise comparison – each
record x from X and y from Y are compared one by one,
having a quadratic time complexity of O(|X||Y|). Further-
more, each record x and y are typically examined by some

distance metrics – if *dist*(x, y) exceeds some threshold then the pair is “matched”. One of the popular techniques to improve the performance of record linkage methods is to use *blocking* – by clustering records into pre-determined blocks so that expensive distance measures are performed to only records within each block. Typical blocking works as follows: Suppose one pre-groups records in *Y* into *Y*/*b* blocks (i.e., each block has *b* records on average). Then, each record *x* from *X* is compared to only records from one block and the matching record is determined. That is, the time complexity is reduced to *O*(|*X*||*b*|). Since *b* ≪ |*X*|, this blocking in general improves the performance.

As the data size grows and more expensive distance metrics are employed, the importance of blocking increases as well. However, in the case of private record linkage, to our best knowledge, no previous approaches attempt to combine the “blocking” with the “private record linkage.” Therefore, in this paper, we study a *blocking-aware private record linkage* protocol and propose several blocking schemes for enhanced performance. A key observation is the preprocessing of records into blocks, using “secure blocking” schemes.

**Example 1 (Motivation).** To illustrate the benefits of blocking-aware private record linkage, consider two credit card companies that wish to identify fraudulent customer list common to both companies. However, using the regular record linkage is inappropriate because of the private nature of credit card information (i.e., two companies do not want to share their customer-related information with the other party). Assume company A holds 2 million records and company B holds 3 million records. Moreover, suppose an average of 50 records are assigned to each block. In the absence of blocking, every record pair has to be compared, resulting in 2 million × 3 million = 6 trillion comparisons! However, blocking reduces the number of comparisons to 2 million × 50 = 100 million. □

2. RELATED WORK

By and large, three categories of previous work are closely
related to ours: secure data sharing, record linkage, and
private record linkage.

**Secure data sharing.** Private record linkage applies when the underlying data is of sensitive nature. Such privacy aware protocols are categorized under the emergent field of privacy preserving data mining: a topic of wide recent interest. Most work in the area is either in data perturbation, or secure data sharing. Data perturbation algorithms [17, 14] distort individual fields of a database for pri-

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA.

Copyright 2005 ACM 1-59593-160-0/05/06 ...$5.00.
vacy, but preserve the overall structure of a database. This
enables the extraction of aggregate data or patterns without
disclosing raw data. On the other hand, secure data sharing
considers sharing or querying of selected data while securing
all other. Unlike secure data sharing, private record linkage
applies when data is heterogeneous.

Many protocols for secure data sharing have been de-
scribed in the literature. Yao et al [26] describe the first two-
party sharing protocol; more protocols and cryptographic
constructions that support multiparty sharing are presented
in [15]. Secure data sharing protocols assume a semi-honest
or honest-but-curious [3] behavior from the participating
parties. This means parties follow the protocol without
cheating, but may try to find as much information about
one another's databases. Other work by Evfimievski et al
[8, 9] investigates the secure mining of association rules, eval-
uation of breeches, and quantification of privacy.

The work of Agrawal et al [1] defines minimal information
sharing in the context of secure data sharing protocols as
the set of additional categories of information inferred by
parties. The protocols they describe, however, are not useful
for matching of heterogeneous data.

**Record Linkage.** Record linkage is a problem that has received wide attention from different communities. The statistical field is interested in probabilistic approaches to evaluating the similarity of records [24, 10, 13]. In the AI field, training data is fed to distance metrics in order to enhance their ability to recover duplicate records [22]. The information retrieval and database fields are mainly concerned with merging heterogeneous databases and optimizing queries using constructions such as inverted indexes.

To improve the performance of record linkage for large
datasets, blocking (sampling) schemes are described in the
literature. The essence of blocking is similar to indexing:
in the database field, indexing increases the performance of
query processing by maintaining tables of related records.
Parallel to indexing, several distinctions arise in blocking
such as manual vs. automatic, or controlled vs. uncontrolled
vocabulary [21]. For generality, it is important that blocking
is automated and accommodates any vocabulary.

Blocking schemes reduce the set of candidate record pairs for which more expensive distance metrics, such as TFIDF [21] or Jaro [2], are computed. Baxtor et al [2] analyze several different blocking schemes and compare them for accuracy and reduction ratio. An effective sampling algorithm is described in [12, 11] based on records’ textual attributes. Experimentation shows that even a simple blocking scheme can result in significant performance gains, with minimal impact on precision.

**Private Record Linkage.** Much of the work in private record linkage has been pioneered in the medical field. Of mention is the work of Quantin et al [19, 18], inspired by the confidentiality needs of medical information. In them, Quantin et al describe a keyed hashing transformation protocol for representing epidemiological data as per the requirement of European privacy laws for irreversible transformations of such data. Matching of similar data is computed on the transformed set. More recent trends with privacy needs include cooperation among government agencies, selective sharing of intellectual property, and outsourcing [1]. Churches et al [4] analyze security of their protocols as a function of the number of mediating parties. They refer to

<figure><img src="image_44.png" /><figcaption>Figure 1: A general third-party matching protocol.</figcaption></figure>

their techniques as “blindfolded” record linkage.

More recent is the work of Ravikumar et al [6] which proposes a secure, stochastic private record linkage protocol that implements all distance metrics where records are representable in a weight vector, such as TFIDF and Soft-TFIDF [5]. Calculation of vectors’ similarity relies on a secure intersection algorithm to compare tokens with probability proportional to their weight. Precision asymptotically converges to the true value as the number of record samples increases. Nonetheless, this protocol’s use of a secure intersection algorithm translates into expensive computation. Such algorithms rely on commutative hashing based on expensive public key encryptions. Furthermore, the protocol requires multiple occurrences of each record to accurately observe the probabilistic model (i.e., training set). Overall, this work is a valuable contribution that paves the way for two-party private record linkage, however, the constructions upon which it is based lack practical maturity.

# 3. PRIVATE RECORD LINKAGE

## 3.1 Overview

Suppose two autonomous parties wish to compute the private record linkage problem on their databases. The task is to design a blocking-compatible private record linkage protocol for enhanced performance. The protocol computes the matching set of records securely, minimizing any information leakage.

We adopt a third party approach to solve this problem. Figure 1 illustrates the communication steps needed. To secure the contents of databases A and B, Alice and Bob must negotiate a secret key and use it to achieve data confidentiality. In this Section, we define our protocol and show how we use *hash signatures* to achieve confidentiality and compactness. Later, we describe several blocking schemes and experimentally verify the performance gains achieved.

## 3.2 Threat Model and Evaluation

Participants in a private record linkage problem are characterized by *semi-honest*, or *honest-but-curious* behavior [3]. Semi-honest behavior presumes a party will attempt to infer any information possible from the data supplied by other parties. This includes carrying out frequency analysis and known-text attacks of data. We adopt a conservative approach to security based on the premise that an adversary has access to a pool of all known text.

Nonetheless, semi-honest behavior forbids participants from other forms of cheating. Participants do not misrepresent their inputs by supplying false data (spoofing attack) or in-
tentionally hiding parts of their data (hiding attack) [25]. No form of collusion between any party and a third party occurs. Semi-honest behavior is a common requirement for participants in secure data sharing problems in the literature.

In minimal information sharing, security is determined by the additional categories of information divulged in the process of solving a problem. For example, depending on the distance metric used, the third party is given access to information (e.g. weight information) that facilitates matching of records. However, there exist other important categories of information with more tunable levels of exposure. The following categories of information are considered in our analysis of information leakage:

* Database size ($DB_{size}$).

* Vocabulary size of a database ($Vocab_{size}$).

* Lengths of database records ($Rec_{len}$).

* Frequency of all tokens in a database ($Tok_{freq}$), not to be confused with TFIDF's token frequency (TF).

For each category above, we define three levels of exposure:

* Yes (divulged, revealed, determined, exposed): the category is accurately measured by a curious party.

* inf: (1) an upper bound is computed on the whole category, or (2) an accurate measure is calculated on a subset of a category.

* No: the category is not divulged, neither is an upper bound divulged.

Determining a level of exposure on the defined categories is a loose characterization of a protocol's privacy. In Section 4, we employ this characterization to analyze the performance of our protocol with respect to blocking scheme alternatives.

## 3.3 Protocol

Several participants interact in a private record linkage problem. We first define the participants as follows: There are three semi-honest participants: Alice, Bob, and Carol. Alice holds private database A that contains a set of records with a finite number of fields. Bob holds another database B that contains a similar but separate set of records. Alice and Bob are the collaborating parties who wish to find the common records in their databases A and B. Carol is the third party chosen by Alice and Bob to execute the distance metric.

Figure 1 illustrates a general third party matching protocol. The protocol assumes all communication between parties is carried over a secure channel, e.g., via cryptography. A general overview of the steps of our private record linkage protocol that incorporates blocking is as follows:

1. Alice and Bob negotiate a secret key, $k$, unknown to Carol.

2. Alice and Bob each use a blocking method to generate blocks and assign records of databases A and B to the blocks. Next, Alice and Bob transmit the blocks to Carol.

3. Carol computes a distance on the reduced set of candidate pairs and forwards the results to Alice and Bob.

Third party requirement is common among private record linkage protocols because techniques used in two party protocols fail to correctly represent and match heterogeneous data. Two party protocols rely on double encryptions of data, the output of which are matched. Double encryptions do not preserve properties of heterogeneous data. In [4], the authors further expand on the number of third parties and analyze security as a function of the number of compromised third parties. In [6], the authors describe a third party free protocol for private record linkage, but it achieves poor performance as we mentioned previously.

Third party protocols use keyed transformations of records, e.g keyed hashing, to prevent security breaches due to curious behavior from the third party. Otherwise, the third party can analyze collaborating parties' databases with similar transformations performed on a pool of all known text (i.e brute force).

## 3.4 Secure Hashing

We introduce the hash signature transformation construct as a compact and secure way to represent TFIDF weight vectors. TFIDF is a proven distance metric based on the tokens (words) in a record. Hash signatures use keyed hashing of individual tokens of a record using a pre-negotiated key $k$. For brevity, $k$ is omitted but implied in the computation of a hash signature. Before presenting further details, it is useful to first introduce TFIDF.

**TFIDF.** The TFIDF [21] (Token Frequency / Inverse Document Frequency) distance metric is widely used for matching of similar information. TFIDF is based on the intuition that tokens which appear frequently in a given record should be assigned higher weights in that record (TF weight), while tokens which appear frequently in the database as a whole should be generally assigned low weights (IDF weight). For example, consider a database of universities. TFIDF would assign higher weights to tokens such as “PSU” and “Stanford”, and lower weights to tokens such as “university” and “college”. Records are matched according to a normalization of the linear combination of the TF and IDF weights of similar tokens. Two records $A_x$ and $B_y$ are considered similar if their TFIDF score exceeds some threshold. The TFIDF score is given by:

$$TFIDF(A_x, B_y) = \frac{weight_x \cdot weight_y}{|weight_x| \times |weight_y|} \quad (1)$$

To compute $weight_x$, for each $w_i \in A_x$,

$$weight(x, w_i) = \log(TF_{w_i} + 1) \times \log(IDF_i) \quad (2)$$

It follows,

$$weight_x = \bigcup_i weight(x, w_i) \quad (3)$$

Alternatively, Eq 1 can be represented as a dot-product of two vectors $V_x$ and $V_y$ [6].

$$V_x = \frac{weight_x}{|weight_x|} \quad (4)$$

Hence, Alice and Bob can independently compute $V_x$ and $V_y$. The vector lengths are dependent upon the size of the vocabulary set of the two databases.
<table><caption>Table 1: Databases A and B</caption><thead><tr><th colspan="2">Database A</th><th colspan="2">Database B</th></tr><tr><th>id</th><th>record</th><th>id</th><th>record</th></tr></thead><tbody><tr><td>a1</td><td>{'a', 'b'}</td><td>b1</td><td>{'b'}</td></tr><tr><td>a2</td><td>{'c'}</td><td>b2</td><td>{'a', 'b'}</td></tr></tbody></table>

<table><caption>Table 2: Example hash signatures</caption><thead><tr><th></th><th>F[0]</th><th>F[1]</th><th>F[2]</th><th>F[3]</th></tr></thead><tbody><tr><td>HS(a1)</td><td>weight(a1,'b')</td><td>0</td><td>0</td><td>weight(a1,'a')</td></tr><tr><td>HS(a2)</td><td>0</td><td>0</td><td>weight(a2,'c')</td><td>0</td></tr><tr><td>HS(b1)</td><td>weight(b1,'b')</td><td>0</td><td>0</td><td>0</td></tr><tr><td>HS(b2)</td><td>weight(b2,'b')</td><td>0</td><td>0</td><td>weight(b2,'a')</td></tr></tbody></table>

TFIDF specifies measuring the TF weight of tokens on a record granularity, but measures the IDF weight, i.e. $IDF_i$, on a common vocabulary of $A \cup B$. For Alice to correctly represent $V_x$, token information is required from database B, and vice versa. Note that it may be insecure to divulge the IDF weights of the vocabulary of either database. However, it is conceivable to assume that databases A and B are similar, e.g., if database A consists of citation data, database B will also consist of citation data. Hence, separate IDF measurements appear to be good estimates for a common vocabulary.

**Hash Signature.** As mentioned above, hash signatures are compact and secure representations of TFIDF weight vectors, namely, $V_x$ and $V_y$. The size of vectors $V_x$ and $V_y$ is not fixed and is based on the data residing in databases A and B. This results in long vectors and requires insecure pre-agreement on vocabulary ordering. A hash signature transformation of $A_x$ denoted as $HS(A_x)$ is a compact, vocabulary-independent representation of the TFIDF weight vector based on a simple hashing function with a small output $t$, e.g., 10 bits. The hash function is evaluated on each token, and the hash output is an index to a $2^t$ floating point array where the weight is stored. As with $V_x$ and $V_y$, the TFIDF score of a pair of records is a dot-product of the hash signatures.

For example, let $A_x = \{w_1, ..., w_n\}$, $F$ be an array of floating point values initialized to 0, and $h^t$ be a hash function with $t$ bit output.

$$ 
\begin{aligned}
F[i_1] &= weight(x, w_1) \\
F[i_2] &= weight(x, w_2) \\
&\vdots \\
F[i_n] &= weight(x, w_n) \\
i_l &= h^t(w_l), l \in \{1...n\}^1
\end{aligned}
$$

$$HS(A_x) = F \qquad (5)$$

**Example 2.** Assume Alice's database A contains 2 records and Bob's database B also contains 2 records as in Table 1. To illustrate how a hash signature is computed, let the hash function $h^t$ output be $t = 2$. As mentioned previously, the hash function performs keyed hashing with an omitted key $k$: $h^t('a') = 3$, $h^t('b') = 0$, and $h^t('c') = 2$. Each hash

signature is composed of a floating point array of weights, as shown in Table 2. The array position where a weight of a particular token is stored depends on the hash output of the token. For example, weight(a1,'b') is stored in the entry with index 0, because $h^t('b') = 0$. ☐

## 3.5 Analysis

Notice that since the hash output size, $t$, is relatively small, there is a high probability of collisions. This means distinct tokens of a record may map to the same hash signature entry. Likewise, dissimilar tokens of a record pair may map to the same entry. This can result in inaccurate TFIDF scoring. In our implementation, if multiple tokens of a record map to the same entry, only the smallest weight is stored to minimize the effect on TFIDF scoring. Assuming that every collision incident results in incorrect matching:

**Lemma 1.** The worst case performance of our protocol using hash signatures is $\frac{2^{t_1}}{(2^{t-n})! \times 2^{nt}}$, where $n$ is the number of different tokens in $A_x \cup B_y$. ■

**PROOF.** Assume a worst case performance such that every collision occurrence results in a mismatch. We want to show the worst case performance of TFIDF using hash signatures is $\frac{2^{t_1}}{(2^{t-n})! \times 2^{nt}}$ of the performance of TFIDF. But, given $HS(A_x)$, and $HS(B_y)$, the number of permutations such that two different tokens in the pair map to the same array entry = $\binom{2^t}{n} \times n!$. By dividing the total number of

$$ \text{possibilities, we have } \frac{\binom{2^t}{n} \times n!}{2^{nt}} = \frac{2^{t_1}}{(2^{t-n})! \times 2^{nt}}. \quad (\text{q.e.d}) $$

Hence, for $n \ll 2^t$, the worst case achieves performance above 95% of performance of TFIDF. Note, $t$ is a design parameter that can be adjusted to satisfy $n \ll 2^t$.

A further modification geared at conserving disk space is possible with hash signatures. Since $n \ll 2^t$, hash signatures are sparse weight arrays. It follows that the set of database records is an instance of a sparse matrix. There are many ways to compactly represent sparse matrices, including smaller arrays of positions and corresponding values or a linked list of position/value pairs. However, we consider a technique known as run-length encoding, which lists each weight followed by the number of zeros suppressed. Run-length encoding is suitable to our scheme because it is easy to implement and features a small overhead, yet has been found to achieve up to 70% compression [21].

## 4. BLOCKING SCHEMES

Among many variations, in our implementation, we use token blocking [5] – every pair of records becomes a candidate pair if they share at least one token. A separate block is associated with every token, containing records in which the token appears.

**Phase 2 Blocking.** The structure of our hash signatures enables augmenting the blocking process with a second phase executed on records of the same block to further reduce the set of candidate pairs. We find that the well-known Jaccard [5] metric is readily compatible. Jaccard is computed on a binary representation of a record's hash signature, such that non-zero weights are treated as a binary 1

<footnote n="1">¹Actually, $h^t(w_i||k)$ is computed, but $k$ is omitted for brevity. The symbol '$||$' denotes string concatenation.</footnote>
and zero weights as a binary 0. Let $D_A$ and $D_B$ be the binary representations of $A_x$ and $B_y$, respectively, the Jaccard metric is given by,

$$ Jaccard(D_A, D_B) = \frac{|D_A \cap D_B|}{|D_A \cup D_B|} \quad (6) $$

The use of Jaccard for blocking appears to further increase performance, because it is computed very efficiently. The details are investigated in our experiments.

**Information Leakage.** The level of information leakage is evaluated for our protocol with respect to each blocking scheme introduced. It is important to note, however, there are subtle differences between the levels of sharing defined. To better illustrate this, consider a database of records mapped to hash signatures. It is easy to see that $DB_{size}$ is divulged as it equals the number of hash signature entries. However, only $inf Rec_{len}$ is divulged because a hash signature may incur collisions. Furthermore, $inf Vocab_{size}$ is revealed because the number of different entries in the set of hash signatures necessarily means different tokens. However, $Tok_{frq}$ is not revealed because collisions do not preserve an accurate measure of the frequency of tokens.

On the other hand, if a subset of the hash signatures is available, only $inf DB_{size}$ is divulged. However, $Rec_{len}$ is not divulged, because it is an inaccurate measure (due to collisions) that is revealed on a subset of all records. Lastly, $Vocab_{size}$ is also not revealed for the same reason.

**Assumptions.** We partially base our analysis of security on several assumptions. Records are non-empty and do not solely consist of stop list tokens – very commonly occurring tokens in a database. We further assume that stop list tokens are not interesting: a measure of a category is considered accurate, even if it fails to represent stop list tokens.

In addition, if two hash signatures possess a similar set of weights stored, this does not necessarily imply that the hash signatures are the same. They are only considered the same if the weights reside in the same array entries. The reason for this will become more apparent in the following subsections.

## 4.1 Baseline Approach

Assume two parties Alice and Bob wish to compute the matching problem on their databases A and B, respectively. A is a set of records $A_1, ..., A_n$ and B is a set of records $B_1, ..., B_m$. Alice and Bob share a secret key $k$ that is tacitly used in the computation of hash signatures. Carol is the mediating third party. In the “baseline” scheme, the matching problem is computed without the use of any blocking. The interest of this scheme is purely experimental. Alice and Bob transmit sequences of the hash signatures of databases A and B to Carol. Carol computes the matching problem on all pairs of A and B, and identifies matching records to Alice and Bob. This scheme proceeds as follows:

1. For each $A_x \in A$, Alice computes $HS(A_x)$. Likewise, for each $B_y \in B$, Bob computes $HS(B_y)$.

2. Let $A_{hs}$ denote all $HS(A_x)$ that Alice transmits to Carol. Let $B_{hs}$ denote all $HS(B_y)$ which Bob transmits to Carol.

3. For each $D_A \in A_{hs}$, $D_A$ is paired with every $D_B \in B_{hs}$ for computing of the distance metric.

<figure><img src="image_45.png" /><figcaption>Figure 2: Phase 1 blocking in Simple blocking</figcaption></figure>

This scheme does not employ any blocking, resulting in $O(nm)$ load. The additional categories of information revealed to Carol, $I_0$, in this scheme include: $DB_{size}$, $inf Vocab_{size}$, and $inf Rec_{len}$ of databases A and B, because of the possibility of collisions in hash signatures. $Tok_{frq}$ is not revealed.

## 4.2 Simple Blocking

In the Simple blocking scheme, token blocking is used to enhance the performance of the baseline scheme. The collaborating parties arrange records in blocks and transmit the blocks to Carol. The protocol steps are as follows:

1. For each $w_i \in A_x$, Alice computes $HS_{w_i}(A_x)$ and stores it in $R_{w_i}$, the block of $w_i$. Similarly, for each $w_j \in B_y$, Bob computes $HS_{w_j}(B_y)$ and stores it in $S_{w_j}$, Bob's block of $w_j$.

2. Let $Key_A \to Block_A$ denote all mappings $h(w_i) \to R_{w_i}$ that Alice transmits to Carol. Let $Key_B \to Block_B$ denote all mappings $h(w_j) \to S_{w_j}$, which Bob transmits to Carol.

3. For each $w \in Key_A$, if $w \in Key_B$, compute the Jaccard metric on every pair $D_A \in Block_A$ and $D_B \in Block_B$.

4. If $Jaccard(D_A, D_B) > threshold$, $D_A$ and $D_B$ are paired for computing of the distance metric.

In step 2 of this scheme, $h$ is a keyed hashing function that provides confidentiality to the block identifier, i.e. the token; the key is concatenated analogous to hash signatures. Any secure hashing algorithm may be used. In our case, we implement SHA-1.

$I_1$, the additional categories of information divulged to Carol in Simple blocking include: $Vocab_{size}$ because token blocking generates a separate block for each token in a record, and $inf DB_{size}$ of databases A and B. Further, since Carol has no way of knowing whether hash signatures appearing in different blocks with permuted weights represent the same original record, only $inf DB_{size}$ is determined by Carol. For the same reason and because of hash signature collisions, only $inf Rec_{len}$ is divulged.

Finally, $Tok_{frq}$ of databases A and B is divulged to Carol. Each block contains a list of hash signatures where the token appears, thereby an accurate measure of frequency of a token is revealed. This may prove to be a vulnerability to statistical attacks, such as Zipf [21] distribution. A technique to thwart such attacks is considered in Section 6.
<table><caption>Figure 3: Phase 1 blocking in Record-aware blocking</caption><thead><tr><th>Key<sub>A</sub></th><th colspan="5">Block<sub>A</sub></th></tr></thead><tbody><tr><td>h(w)</td><td>x</td><td>HS<sub>w<sub>i</sub></sub>(A<sub>y</sub>)</td><td>x'</td><td>HS<sub>w<sub>i</sub></sub>(A<sub>x</sub>)</td><td>x''</td><td>HS<sub>w<sub>i</sub></sub>(A<sub>x'</sub>)</td><td>...</td></tr><tr><td>h(w<sub>i+1</sub>)</td><td>y</td><td>HS<sub>w<sub>i+1</sub></sub>(A<sub>y</sub>)</td><td>y'</td><td>HS<sub>w<sub>i+1</sub></sub>(A<sub>y</sub>)</td><td>y''</td><td>HS<sub>w<sub>i+1</sub></sub>(A<sub>y'</sub>)</td><td>...</td></tr><tr><td>h(w<sub>i+2</sub>)</td><td>z</td><td>HS<sub>w<sub>i+2</sub></sub>(A<sub>z</sub>)</td><td>z'</td><td>HS<sub>w<sub>i+2</sub></sub>(A<sub>z</sub>)</td><td>z''</td><td>HS<sub>w<sub>i+2</sub></sub>(A<sub>z'</sub>)</td><td>...</td></tr></tbody></table>

## 4.3 Record-aware Blocking

In Simple blocking, the assignment of hash signatures to blocks equivocates a record across blocks where it is placed. The reason is that in step 1 of Simple blocking, the hash signature is computed with respect to the block ($HS_{w_i}$). Hence, the same record is indistinguishable to the third party when placed in multiple blocks. This means Simple blocking will compute duplicate distance metrics on the same pair of records proportional to the number of common blocks in which they appear. A relatively high ratio of common blocks per record pair can render the blocking scheme extremely inefficient. Record-aware resolves this by coupling an id with the hash signature of each record. The ids of every pairing made are maintained to ensure uniqueness of a pair. The blocking steps of Record-aware are as follows:

1. For each $w_i \in A_x$, Alice computes $HS_{w_i}(A_x)$ and stores the pair $[x, HS_{w_i}(A_x)]$ in $R_{w_i}$, the block of $w_i$. Similarly, for each $w_j \in B_y$, Bob computes $HS_{w_j}(B_y)$ and stores the pair $[y, HS_{w_j}(B_y)]$ in $S_{w_j}$, Bob's block of $w_j$.

2. Let $Key_A \to [ID_A, Block_A]$ denote all mappings $h(w_i) \to R_{w_i}$ that Alice transmits to Carol. Let $Key_B \to [ID_B, Block_B]$ denote all mappings $h(w_j) \to S_{w_j}$, which Bob transmits to Carol.

3. For each $w \in Key_A$, if $w \in Key_B$, Carol computes the Jaccard metric on every pair $D_A \in Block_A$ and $D_B \in Block_B$, such that $(ID_A, ID_B) \notin Paired$. Paired is used to ensure that duplicate distance metrics on the same pair are not computed.

4. If $(ID_{D_A}, ID_{D_B}) \notin Paired$ and Jaccard($D_A, D_B$) > threshold, $D_A$ and $D_B$ are paired for computing of the distance metric. Update $Paired = Paired \cup \{(ID_{D_A}, ID_{D_B})\}$

The increase in efficiency in this scheme is attained at the expense of additional data leakage in comparison to Simple blocking. This scheme divulges all designated categories of information to Carol. Unlike Simple blocking, Carol determines $DB_{size}$ of databases A and B, because an id is coupled with each hash signature that uniquely identifies the record which it represents. $Rec_{len}$ are also divulged for the same reasons. As in Simple blocking, $Vocab_{size}$ and $Tok_{frq}$ are revealed. This scheme provides the greatest exposure in terms of information leaked to Carol.

## 4.4 Frugal Third Party Blocking

In the previous two schemes, Alice and Bob transmit all of their blocks to Carol, even if only a fraction of the blocks are similar. Alternatively, Alice and Bob may find what blocks

<table><caption>Table 3: Summary of information leakage</caption><thead><tr><th rowspan="2">Scheme</th><th colspan="4">Information Categories</th></tr><tr><th>DB<sub>size</sub></th><th>Vocab<sub>size</sub></th><th>Rec<sub>len</sub></th><th>Tok<sub>frq</sub></th></tr></thead><tbody><tr><td>Baseline</td><td>Yes</td><td>inf</td><td>inf</td><td>No</td></tr><tr><td>Simple</td><td>inf</td><td>Yes</td><td>inf</td><td>Yes</td></tr><tr><td>Record-aware</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><td>Frugal Third Party</td><td>inf</td><td>inf</td><td>No</td><td>inf</td></tr></tbody></table>

they have in common and only transmit those blocks. This arrangement has the advantage of minimizing communication size between participants. Further, the amount of data storage maintained by Carol for the matching problem is reduced, and Carol is relieved from the task of finding intersection between the blocks, resulting in less blocking and matching time. Moreover, from a monetary cost standpoint, any computation performed by Carol is associated with a much greater price than computations performed by Alice or Bob. Carol is merely a mediating party which may charge a significant fee for facilitating matching between collaborating parties. It follows that it may be more cost-effective for Alice and Bob to perform as much computation as possible, even if such computation is orders of magnitudes greater than a logically equivalent computation performed by Carol.

Frugal Third Party blocking employs a secure intersection algorithm [23, 6] to compute the intersection set size using commutative one-way hash functions. In our implementations, we use RSA private keys with a common modulus. The scheme steps are as follows:

1. For each $w_i \in A_x$, Alice computes $HS_{w_i}(A_x)$ and stores the pair $[x, HS_{w_i}(A_x)]$ in $R_{w_i}$, the block of $w_i$. Similarly, for each $w_j \in B_y$, Bob computes $HS_{w_j}(B_y)$ and stores the pair $[y, HS_{w_j}(B_y)]$ in $S_{w_j}$, Bob's block of $w_j$.

2. Let $Key_A \to [ID_A, Block_A]$ denote all mappings $h(w_i) \to R_{w_i}$. Let $Key_B \to [ID_B, Block_B]$ denote all mappings $h(w_j) \to S_{w_j}$. Using the secure intersection algorithm, find $Key_A \cap Key_B$. Alice transmits to Carol all $w \to [ID_A, Block_A]$ and Bob transmit all $w \to [ID_B, Block_B]$, such that $w \in Key_A \cap Key_B$.

3. For each $w \in Key_A \cap Key_B$, Carol computes the Jaccard metric on every pair $D_A \in Block_A$ and $D_B \in Block_B$, such that $(ID_A, ID_B) \notin Paired$. As in Record-aware, Paired is used to ensure that duplicate distance metrics on the same pair are not computed

4. Finally, if $(ID_{D_A}, ID_{D_B}) \notin Paired$ and Jaccard($D_A, D_B$) > threshold, $D_A$ and $D_B$ are paired for computing of the distance metric. Update $Paired = Paired \cup \{(ID_{D_A}, ID_{D_B})\}$

In this scheme, some additional categories of information are revealed only to Alice and Bob, while others only to Carol. Let $I_{3AB}$ denote the additional categories revealed to Alice and Bob and $I_{3C}$ denote categories revealed to Carol.

Alice and Bob predetermine the blocks which are shared by them. Hence, $I_{3AB}$ contains $Vocab_{size}$, meaning Alice learns the vocabulary size of database B and Bob learns the vocabulary size of Alice. Since Carol does not receive all blocks, $I_{3C}$ includes $inf DB_{size}$ and $inf Vocab_{size}$ because an accurate measure is determined on a subset of the categories. Further, Carol only determines an accurate $Tok_{frq}$
<figure><img src="image_46.png" /><figcaption>(a) Blocks of Simple blocking</figcaption></figure>

<figure><img src="image_47.png" /><figcaption>(b) Blocks of Record-aware and Frugal Third Party</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>Figure 5: Hash signature contents</figcaption></figure>

of a subset of all tokens because she only receives a subset of all blocks, hence **inf** *Tok*<sub>*frq*</sub>. However, Carol does not determine *Rec*<sub>*len*</sub> because an inaccurate measure is possible on merely a subset of records. The security of this scheme introduces a level of uncertainty to the categories divulged to Carol at the cost of increased computational cost and exposure of some categories to Alice and Bob. From an information leakage standpoint, Frugal Third Party is more useful when security with respect to the third party is of prime concern.

**Example 3.** Here, we present an example that illustrates the working of Simple, Record-aware, and Frugal Third Party blocking schemes. We consider databases A and B as defined in Table 1.

1. **Step 1.** Figure 4(a) illustrates how a record's hash signature is arranged in blocks that correspond to the tokens contained in the record. For example, record a1 contains tokens 'a' and 'b'; hence, it appears in the block corresponding to a as *HS*<sub>a</sub> and the block corresponding to b as *HS*<sub>b</sub>. Notice that a hash signature representation appears differently depending on the block where it is stored. This is accomplished by a

<figure><img src="image_49.png" /><figcaption>Figure 6: Binary representations of hash signatures</figcaption></figure>

concatenation of the block's token to the hash function used to generate the hash signature (note a key is also concatenated).

The blocks of Record-aware and Frugal Third Party blocking schemes appear a little differently, as illustrated in Figure 4(b). As mentioned above, an id is coupled with each hash signature, so identical pairs are not matched for similarity multiple times. Assuming *t* is 2-bits, and $h^t('a'||a) = 3$, $h^t('b'||a) = 0$, $h^t('c'||c) = 2$, $h^t('a'||b) = 2$, $h^t('b'||b) = 1$, The hash signatures are computed as shown in Figure 5.

2. **Step 2.** In Simple and Record-aware blocking, Alice and Bob readily transmit their blocks of hash signatures computed in the last step to Carol. Alice transmits 3 blocks to Carol, while Bob transmits 2 blocks to Carol. However, in Frugal Third Party, Alice and Bob first determine the matching block names using a secure intersection algorithm. It is determined that only two blocks match, corresponding to *a* and *b*. Hence, Alice and Bob both transmit 2 blocks to Carol.

3. **Step 3.** Carol computes the distance metric on hash signatures which appear in common blocks. In Simple blocking, all records of the parties which appear in similar blocks are considered. This results in the following pairings: (*HS*<sub>a</sub>(*a*1), *HS*<sub>a</sub>(*b*2)), (*HS*<sub>b</sub>(*a*1), *HS*<sub>b</sub>(*b*2)), and (*HS*<sub>b</sub>(*a*1), *HS*<sub>b</sub>(*b*1)). On the other hand, Record-aware and Frugal Third Party only pair a1 and b2 once, instead of twice. Hence, only two pairings are made: (*HS*<sub>a</sub>(*a*1), *HS*<sub>a</sub>(*b*2)) and (*HS*<sub>b</sub>(*a*1), *HS*<sub>b</sub>(*b*1)).

4. **Step 4.** The Jaccard metric is computed on a binary equivalent of each hash signature. Figure 6 illustrates binary equivalents of the hash signatures. It follows:

* Jaccard(*HS*<sub>a</sub>(*a*1), *HS*<sub>a</sub>(*b*2)) = 1

* Jaccard(*HS*<sub>b</sub>(*a*1), *HS*<sub>b</sub>(*b*2)) = 1

* Jaccard(*HS*<sub>b</sub>(*a*1), *HS*<sub>b</sub>(*b*1)) = .5

In the absence of blocking, 4 distance metrics are calculated. If Jaccard *threshold* > .5, then 2 distance metric are calculated in Simple blocking, resulting in 50% reduction ratio. Only 1 metric is calculated in the Record-aware and Frugal Third Party schemes resulting in a reduction ratio of 25%. □

5. EXPERIMENTAL VALIDATION

We have implemented our schemes based on the Second-String package [5], and have tested it using a range of datasets
<table><caption>Table 4: Experimental Datasets 1</caption><thead><tr><th>Dataset</th><th>Domain</th><th>A size</th><th>B size</th><th>A ∩ B size</th><th># of tokens per record (avg)</th></tr></thead><tbody><tr><td>BioMed</td><td>Medicine</td><td>5000</td><td>5000</td><td>2000</td><td>25.44</td></tr><tr><td>DBLP</td><td>CompSci</td><td>5000</td><td>5000</td><td>2000</td><td>14.68</td></tr><tr><td>EconPapers</td><td>Economics</td><td>5000</td><td>5000</td><td>4000</td><td>21.23</td></tr><tr><td>e-Print</td><td>Physics</td><td>5000</td><td>5000</td><td>2000</td><td>13.83</td></tr></tbody></table>

<figure><img src="image_50.png" /><figcaption>Figure 7: Comparison of blocking + matching time of four implementations</figcaption></figure>

consisting of citation data. Each citation is parsed as a set of fields and only a random permuted subset of the fields are stored to achieve a level of heterogeneity. The choice of citation data was influenced by Ravikumar et al [6]. As an evaluation metric, *precision* is defined as the fraction of pairs matched by the distance metric that are correct, and *reduction ratio* as the ratio between candidate pair count from blocking and pair count from a pair-wise comparison.

## 5.1 Blocking

Figure 7(a) proves our claims of increased performance due to blocking, by comparing the blocking schemes against the baseline scheme and record linkage TFIDF that doesn't use blocking. Note, computation time due to the secure intersection algorithm in the Frugal Third Party scheme has been factored out. Table 4 lists the datasets used in this experiment and their characteristics. For all cases, the blocking techniques require a fraction of the time to solve the same problem, often at a negligible cost of precision. Figure 7(b) illustrates the precision observed for each dataset. The precision observed for the e-Print dataset deviates from other datasets. However, even in the non-private protocol, low precision is observed. Nonetheless, this is magnified in the private record linkage protocols.

Moreover, it is observed that representing records as hash signatures increases performance. We attribute this to the way hash signatures are represented, which is more compact than weight vectors in record linkage.

## 5.2 Blocking Schemes

To verify the properties of the proposed blocking scheme, several experiments were conducted using DBLP citations as in Table 5.

In Figure 8(a), the total time expended by the third party is measured as a function of dataset used. Simple blocking is the least efficient for the reason that every pair of records may be measured for similarity more than once. The total time expended for Simple and Record-aware blocking does not follow any specified pattern because of additional factors that come into play, such as the total number of blocks in each database, or the number of shared blocks. On the other hand, in Frugal Third Party, as the number of shared records increases, total third party time also increases because only common blocks are transmitted over to the third party. Clearly, the number of common blocks is likely to increase relative to the number of shared blocks. When A and B have the same records, no third party gains are observed by Frugal Third Party over Record-aware, resulting in transmission of almost all blocks, congruent to Simple and Record-aware.

Frugal Third Party reduction of third party time and restriction on privacy divulged to third party comes at an overwhelming cost of collaborating party blocking. Figure 8(b) illustrates the average blocking time of Frugal Third Party, Simple, and Record-aware schemes. It eludes to 4 orders of magnitude difference in blocking time.

The reduction ratio observed by two phase blocking is dependent on characteristics of the dataset, such as Vocabsize and Tokfrq. Nonetheless, reduction ratio is directly responsible for the matching time needed to solve the problem. Figure 9 illustrates the linear relationship between reduction ratio and matching time.

## 5.3 Two-phase Blocking

The second phase of blocking, Jaccard metric, depends on basic set operations to further reduce candidate pairs that undergo TFIDF scoring. The threshold used for Jaccard

<table><caption>Table 5: Experimental Datasets 2</caption><thead><tr><th>Dataset</th><th>A size</th><th>B size</th><th>A ∩ B size</th></tr></thead><tbody><tr><td>1</td><td>2500</td><td>2500</td><td>0</td></tr><tr><td>2</td><td>2500</td><td>2500</td><td>100</td></tr><tr><td>3</td><td>2500</td><td>2500</td><td>250</td></tr><tr><td>4</td><td>2500</td><td>2500</td><td>500</td></tr><tr><td>5</td><td>2500</td><td>2500</td><td>1000</td></tr><tr><td>6</td><td>2500</td><td>2500</td><td>2500</td></tr></tbody></table>
<figure><img src="image_51.png" /><figcaption>(a) Total third party time</figcaption></figure>

<figure><img src="image_52.png" /><figcaption>(b) Blocking time of collaborating parties</figcaption></figure>

<figure><img src="image_53.png" /><figcaption>Figure 9: Relationship between reduction ratio and matching time</figcaption></figure>

blocking is tunable for enhanced control over the level of blocking achieved. In Figure 7(a), the gains resultant from predominantly phase 1 blocking are observed. In practice, using phase 2 Jaccard, we are able to control the gains by adjusting the *threshold*. Figure 10 illustrates the performance increase when the Jaccard *threshold* is increased to .25. Experiments of the previous subsection all used *threshold* = .1.

<figure><img src="image_54.png" /><figcaption>Figure 10: Relationship between reduction ratio and matching time for Dataset 1-6</figcaption></figure>

## 6. OTHER ISSUES

The privacy of our protocol can be further increased by using techniques such as *chaffing* and *winnowing* [20]. Chaffing refers to the act of augmenting data with additional dummy data, indiscernible from other data, i.e. noise. Winnowing is the reverse process that eliminates dummy from real data. Chaffing is performed by the collaborating parties prior to transmitting data to the third party. After the

results are computed and returned to the collaborating parties, all dummy data is winnowed appropriately.

Chaffing and winnowing techniques address the problem introduced by a Zipf [21] analysis of data blocks that we identified earlier. The problem is solved by fixing the content size of each block to make them appear indifferent, through the addition of noise. Nevertheless, this comes at the expense of increased cost and memory requirements. Our current implementations do not consider chaffing and winnowing.

## 7. CONCLUSION

In this paper, we described a secure protocol for record linkage and several schemes that achieve secure blocking. In the protocol, the collaborating parties use TFIDF to independently calculate and generate weight vectors, represented as hash signatures. This protocol requires a key to be negotiated by the collaborating parties, unknown to the third party.

The blocking schemes described are characterized by varying privacy as per minimum information sharing at the expense of performance. We define a loose characterization of information leakage to analyze the privacy of our protocols as a function of blocking scheme. Simple blocking arranges hash signatures in blocks, but a pair may be computed for similarity more than once if they are located in more than one common block. Record-aware solves this issue by coupling an identifier with every hash signature. Frugal Third Party provides the highest level of privacy with respect to information divulged to the third party, but requires the use of public-key dependent secure intersection algorithm, resulting in heavy computational costs on the collaborating parties. The performance of our blocking schemes was further enhanced by introducing a second phase of blocking: Jaccard.

Overall, parallel to record linkage, the use of blocking in private record linkage to enhance performance is verified using analytic and empirical validations. In some cases, blocking increases the security en lieu of performance of the protocol.

**Future Work.** It is interesting to investigate how other distance metrics and blocking schemes can be ported to the secure matching arena. In [6], the authors address other distance metrics and how they may be ported into secure record linkage. Clearly, similar techniques as described in this paper may also apply to those metrics.
8. REFERENCES

[1] Rakesh Agrawal, Alexandre Evfimievski, and Ramakrishnan Srikant. Information sharing across private databases. In *Proceedings of ACM SIGMOD*, pages 86–97, 2003.

[2] Rohan Baxter, Peter Christen, and Tim Churches. A comparison of fast blocking methods for record linkage. In *Proceedings of 9th ACM SIGKDD Workshop on Data Cleaning, Record Linkage and Object Consolidation*, 2003.

[3] R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation. In *STOC 96*, pages 639–648, 1996.

[4] Tim Churches and Peter Christen. Some methods for blindfolded record linkage. *BMC Medical Informatics and Decision Making*, 4(9), 2004.

[5] W. Cohen, P. Ravikumar, and S. Fienberg. A comparison of string distance metrics for matching names and records. In *KDD Workshop on Data Cleaning, Record Linkage, and Object Consolidation*, 2003.

[6] William Cohen, Pradeep Ravikumar, and Stephen E. Fienberg. A secure protocol for computing string distance metrics. In *Proceedings of ICDM Workshop on Privacy and Security Aspects of Data Mining*, 2004.

[7] W. Du and M. Atallah. Potocols for secure remote database access with approximate matching. In *1st Workshop on Security and Privacy in E-Commerce*, 2000.

[8] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In *Proceedings of SIGMOD*, 2003.

[9] Alexandre Evfimievski, Ramakrishnan Srikant, Rakesh Agrawal, and Johannes Gehrke. Privacy preserving mining of association rules. In *Proceedings of 8th ACM SIGKDD*, pages 217–228, 2002.

[10] I. P. Fellegi and A. B. Sunter. A theory for record linkage. *Journal of the American Statistical Association*, 64(328):1183–1210, 1969.

[11] Luis Gravano, Panagiotis G. Ipeirotis, Jagadish Jagadish, Nick Koudas, S. Muthukrishnan, and Divesh Srivastava. Approximate string joins in a database (almost) for free. In *Proceedings of 27th VLDB*, pages 491–500, 2001.

[12] Luis Gravano, Panagiotis G. Ipeirotis, Koudas Koudas, and Divesh Srivastava. Text joins in an rdbms for web data integration. In *Proceedings of 12th WWW*, January 01 2003.

[13] Mauricio A. Hernández and Salvatore J. Stolfo. The merge/purge problem for large databases. In *Proceedings of ACM SIGMOD*, pages 127–138, 1995.

[14] H. Kargupta, S. Datta, Q. Wang, and K. Sivakumar. Random data perturbation techniques and privacy preserving data mining. In *Proceedings of ICDM*, pages 160–164, 2003.

[15] Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. Fairplay — a secure two-party computation system. In *Proceedings of 11th USENIX Security Symposium*, August 2004.

[16] H. Newcombe, J. Kennedy, S. Axford, and A. James. Automatic linkage of vital records. *Science*,

130:954–959, 1959.

[17] Huseyin Polat and Wenliang Du. Privacy-preserving collaborative filtering using randomized perturbation techniques. In *Proceedings of ICDM*, 2003.

[18] Catherine Quantin, H. Bouzelat, F. Allaert, A. Benhamiche, J. Faivre, and L. Dusserre. How to ensure data security of an epidemiological follow-up: quality assessment of an anonymous record linkage procedure. *International Journal of Medical Informatics*, 49(1):117–122, 1998.

[19] Catherine Quantin, H. Bouzelat, and L. Dusserre. A computerized record hash coding and linkage procedure to warrant epidemiological follow-up data security. *Studies in Health Technology and Informatics*, 43:339–342, 1997.

[20] Ronald Rivest. Chaffing and winnowing: Confidentiality without encryption. *MIT, Internal Paper*, 1998.

[21] Gerard Salton, editor. *Automatic Text Processing*. Addison Welsley, 1989.

[22] Sheila Tejada, Craig A. Knoblock, and Steven Minton. Learning object identification rules for information integration. *Information Systems*, 26(8):607–633, 2001.

[23] Jaideep Vaidya and Chris Clifton. Secure set intersection cardinality with application to associate rule mining. *Journal of Computer Security*, 2004. To Appear.

[24] W. E. Winkler. Matching and record linkage. *Business Survey Methods*, pages 355–384, 1995.

[25] L. Xiong, S. Chitti, and L. Liu. Topk queries across multiple private databases. In *25th ICDCS. To appear*, 2005.

[26] Andrew C. Yao. Protocols for secure computations. In *Proceedings of the 23rd Symposium on FOCS*, pages 160–164, 1982.
# Effective and Scalable Solutions for Mixed and Split Citation Problems in Digital Libraries

Dongwon Lee*

Penn State / USA

dongwon@psu.edu

Byung-Won On

Penn State / USA

on@cse.psu.edu

Jaewoo Kang

NCSU / USA

kang@csc.ncsu.edu

Sanghyun Park

Yonsei Univ. / Korea

sanghyun@cs.yonsei.ac.kr

## ABSTRACT

In this paper, we consider two important problems that commonly occur in bibliographic digital libraries, which seriously degrade their data qualities: *Mixed Citation (MC)* problem (i.e., citations of different scholars with their names being homonyms are mixed together) and *Split Citation (SC)* problem (i.e., citations of the same author appear under different name variants). In particular, we investigate an effective yet scalable solution since citations in such digital libraries tend to be large-scale. After formally defining the problems and accompanying challenges, we present an effective solution that is based on the state-of-the-art sampling-based approximate join algorithm. Our claim is verified through preliminary experimental results.

## 1. INTRODUCTION

Bibliographic Digital Libraries (DLs), such as DBLP, CiteSeer or e-Print arXiv, contain a large number of citation<fnref n="1" /> records. Such DLs have been an important resource for academic communities since scholars often try to search for relevant works from DLs. Researchers also use the citation records in order to measure the publication's impact in the research community. In addition, citations are often used when users search for articles of interest. Therefore, it is important to keep the citations of DLs consistent and up-to-date. However, due to data entry errors, imperfect citation gathering software or common author names, DLs often have many errors in their citation collections. In particular, we focus on two problems that commonly occur in many existing DLs as follows.

First, when two scholars have the same name spellings, their citation data are mistakenly merged into a single collection, leading to an incorrect citation analysis results. We call this as **Mixed Citation (MC)** problem. For instance,

Dongwon Lee

List of publications from the DBLP Bibliography Server - FAQ

Coauthor Index - Ask others: ACM DL - ACM Guide - CiteSeer - CSB - Google

<figure><img src="image_55.png" /><figcaption>Figure 1: Mixed citations of “Dongwon Lee” in DBLP. Boxed ones are by another “Dongwon Lee.”</figcaption></figure>

Figure 1 illustrates a collection of citation data by one of the authors, “Dongwon Lee”, in DBLP. Note that two citations by “another” scholar with the same name spelling are listed (boxed ones). The reason of this mixture is that there exist two scholars with the name “Dongwon Lee” – a computer scientist at Penn State and an MIS scholar at U. Minnesota – with somewhat overlapping domains of interests.

Second, due to various reasons, DLs tend to keep the citations of single author under various *name variants*<fnref n="2" />. We call this as **Split Citation (SC)** problem. For instance, imagine a scholar “John Doe” has published 100 articles. However, a DL keeps two separate name variants, “John Doe” and “J. D. Doe”, each of which contains 50 citations. In such a case, users searching for all the articles of “John Doe” will get only 50 of them. Similarly, any bibliometrical study would underestimate the impact of the author “John Doe”, splitting his fare share into “John Doe” and “J. D. Doe” incorrectly. Such a problem of ambiguous author names exists in many of existing DLs, as illustrated in Figure 2, where a renowned computer scientist “Jeffrey D. Ullman” appear under 10 different name variants in ACM Portal’s DL.

In essence, both MC and SC problems cannot be completely avoided unless each person carries a universal ID. Note that these problems would still occur even if digital

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA.

Copyright 2005 ACM 1-59593-160-0/05/06 ...$5.00.

<footnote>*The author is partially supported by IBM Eclipse Innovation Award (2004) and Microsoft SciData Award (2005).</footnote>

<footnote n="1">¹A *citation* or *reference* is a bibliographic entity that consists of various fields (e.g., author, title, venue or year).</footnote>

<footnote n="2">²In this paper, the *name variants* refer to the different spellings of author names that are in fact referring to the same person.</footnote>
<figure><img src="image_56.png" /><figcaption>Figure 2: Split citations of “Jeffrey D. Ullman” in ACM Portal.</figcaption></figure>

object identifier (DOI)<fnref n="3" /> system is fully adopted, since it usu-
ally does not govern the identity of a person or her name.
In this paper, therefore, we investigate efficient solutions for
these problems.

## 2. BACKGROUND

**Related Work.** In [14], we investigated issues related to system support for both problems, and in [20], we explored the split citation problem. Han et al. [12] proposed two supervised learning-based approaches for a related problem. Their problem can be viewed as a kind of the SC problem in our jargon although they do not explicitly define the problem. Furthermore, their approach is not scalable to handle large-scale DLs. On the other hand, we investigate both the MC and SC problems, and present scalable solutions. Nevertheless, we also tested their ideas of supervised learning methods in the step 2 of the name disambiguation algorithm (Section 4.2). The goal of our study is not to compare supervised methods against unsupervised ones, but to explore the combinations of alternatives that give good scalability/accuracy trade-offs in the two-step approaches. We recently learned that [2] introduces a clustering-based solution to a problem similar to our MC problem, and the performance comparison is currently underway. ALIAS system in [22] proposes a framework to detect duplicate entities such as citations or addresses, but its focus is on the learning aspect.

Since the core technique of our proposals in this paper is
to match two related citations (i.e., citation matching), our
work is closely related to more general class of problems,
known as various names – record linkage (e.g., [10, 3]), ci-
tation matching (e.g., [19]), identity uncertainty (e.g., [21]),
merge-purge (e.g., [13]), object matching (e.g., [5]), dupli-
cate detection (e.g., [22, 1]), approximate string join (e.g., [11])
etc.

String similarity measures used in our work were proposed

by Jaro [16] and Winkler [25]. Bilenko et al. have stud-
ied name matching for information integration [3] using
string-based and token-based methods. Cohen et al. have
also compared the efficacy of string-distance metrics, like
JaroWinkler, for the name matching task [6]. In DLs, this
problem is called citation matching. In the citation match-
ing domain, [18] experimented with various distance-based
algorithms with a conclusion that word based matching per-
forms well. We have implemented all these methods in the
second step of your algorithm and compared their efficacy
to other methods.

Before we can process citations, we assume that field seg-
mentation and identification has been completed using some
methods like one in [4]. Blocking was first proposed by Kel-
ley et al. [17] in the record linkage literature. Our sampling
idea can be viewed as a blocking scheme and is also simi-
lar in flavor to the two-step citation matching schemes pro-
posed in [15, 19] where initial rough but fast clustering (or
“Canopy”) is followed by more exhaustive citation matching
step.

Another stream of works that are relevant to our work is name/entity disambiguation and authority controls in NLP community. For instance, works done in [24] aim at detecting name variants automatically using data mining or heuristics techniques, but do not consider the issue of scalability nor in the context of digital libraries. Similarly, [9] introduces a method to find matching variants of named entity in a given text such as project name (e.g., DBLP vs. Data Base and Logic Programming). [23] discusses an effort to standardize author names using a unique number, called INSAN, and [8] is a recent implementation for name authority control, called HoPEc. On the contrary, we focus more on two specific problems relevant to citations of digital libraries.

**Preliminaries.** In this Section, we introduce a technique that our solutions exploit. One of the state-of-the-art sampling techniques that satisfy both criteria (i.e., being fast and accurate) is the *sampling-based join approximation* method recently proposed by [11]. We adopt it to our context as follows: Their main idea is that if, for each string $n_i$, one is able to extract a small sample $S$ that contains mostly strings suspected to be highly similar to $n_i$, then this sample $S$ serves as a candidate set, and the remaining strings can be quickly ignored (i.e., pre-filtering). To get the “good” sample $S$, imagine each token from all strings has an associated weight using the TFIDF metric in IR (i.e., common tokens in strings have lower weights while rare ones have higher weights). Then, each string $t$ is associated with its token weight vector $v_t$. Suppose that, for each string $t_q$ in a string set $R_1$, we want to draw a sample of size $S$ from another string set $R_2$ such that the frequency $C_i$ of string $t_i \in R_2$ can be used to approximate $sim(v_{t_q}, v_{t_i}) = \sigma_i$. That is, $\sigma_i$ can be approximated by $\frac{C_i}{S}T_V(t_q)$, where $T_V(t_q) = \sum_{i=1}^{|R_2|} \sigma_i$. Then, put $t_i$ into a candidate set only if $\frac{C_i}{S}T_V(t_q) \ge \theta$, where $\theta$ is a pre-determined threshold<fnref n="4" />. This strategy assures that all pairs of strings with similarity of at least $\theta$ survive the pre-filtering stage and put into the candidate set with a desired probability, as long as the proper sample size $S$ is given.

<footnote n="4">⁴In experimentation, we used the more optimized version of the sampling-based join approximation with a single scan from [11].</footnote>

<footnote n="3">³http://www.doi.org/</footnote>
<figure><img src="image_57.png" /><figcaption>Figure 3: Overview of our solution to MC problem.</figcaption></figure>

# 3. THE MIXED CITATION PROBLEM

## 3.1 Problem Definition & Solution Overview

**Problem Definition.** We formally define the *Mixed Citation* problem as follows:

Given a collection of citations, C, by an author, $a_i$, can we quickly and accurately identify false citations by another author $a_j$, when $a_i$ and $a_j$ have the identical name spellings?

The challenge here is that since two different authors, $a_i$ and $a_j$, have the “same” name spellings, one cannot easily distinguish the two by using distance between their names (e.g., Edit distance). To overcome this difficulty, we propose to exploit author’s associated information. That is, given an author $a_i$, we may use additional information such as her coauthor list, common keywords that she often use in the titles of articles, or common publication outlets, etc.

**Solution Overview.** Consider a citation $c_i$ with a set of coauthors $A = \{a_1, ..., a_n\}$, a set of keywords from the title $T = \{t_1, ..., t_m\}$, and a venue name $V$. Then, after removing the i-th coauthor $a_i$ ($\in A$), can we correctly label $c_i$ to $a_i$? That is, when $a_i$ is removed from the citation $c_i$, can we guess back the removed author using associated information? Let us call this method as *Citation Labeling* algorithm. If we assume that there is a “good” citation labeling function $f_{cl}: c_i \to a_j$. Then, using the $f_{cl}$, the original MC problem can be solved as follows. Given citations $C$ by an author $a_1$:

for each citation $c_i$ ($\in C$)

remove $a_1$ (i.e., original name) from coauthor list of $c_i$; $f_{cl}$ is applied to get $a_2$ (i.e., guessed name);

if $a_1 \neq a_2$, then $c_i$ is a false citation;

remove $c_i$ from $C$;

At the end, $C$ has only correct citations by $a_1$. Therefore, if one can find a good citation labeling function $f_{cl}$, then one can solve the MC problem.

## 3.2 Citation Labeling Algorithm

Let us examine $f_{cl}$ more closely. Suppose one wants to “label” a collection of citations, $C$, against a set of possible authors $A$. A naive algorithm, then, is (let $\phi$ be a similarity measure between a citation $c_i$ and an author $a_j$):

for each citation $c_i$ ($\in C$)

examine all names $a_j(\in A)$;

return $a_j(\in A)$ with $\max \phi$;

This baseline approach presents two technical challenges: (1) Since $c_i$ and $a_j$ are two different entities to compare in real world, the choice of good similarity measure is critical; and (2) When a DL has a large number of citations and authors in the collection, the baseline approach with a time complexity $O(|C||A|$) is prohibitively expensive to run (e.g., the DBLP has about 0.56 million authors). In order to address these challenges, we propose two solutions as follows.

**Similarity between Citation and Author.** In [12], authors reported a promising result by representing a citation as 3-tuple of coauthors, titles, and venues. Although proposed for a different problem, the idea of 3-tuple representation of citations can be adapted to our context as follows: the similarity between a citation $c$ and an author $a$ (hereafter, $sim(c, a)$) can be estimated as the similarity between a 3-tuple representation of $c$ and that of $a$:

$$sim(c, a) = \alpha sim(\vec{c}_c, \vec{a}_c) + \beta sim(\vec{c}_t, \vec{a}_t) + \gamma sim(\vec{c}_v, \vec{a}_v)$$

where $\alpha + \beta + \gamma = 1$ (i.e., weighting factors), $\vec{c}_c$, $\vec{c}_t$, and $\vec{c}_v$ are token vectors of coauthors, paper titles, and venues, respectively, of the citation $c$, and $\vec{a}_c$, $\vec{a}_t$, and $\vec{a}_v$ are token vectors of coauthors, paper titles, and venues from “all” citations of the author $a$, respectively. In turn, each similarity measure between two token vectors can be estimated using the standard IR techniques such as the cosine similarity, $\cos(\theta) = \frac{\vec{v} \cdot \vec{w}}{\|\vec{v}\| \cdot \|\vec{w}\|}$, along with TFIDF.

For instance, a citation $c$ “E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387 (1970)” is represented as: $\vec{c}_c = [\text{"E.F. Codd"}]$, $\vec{c}_t = [\text{"Relational"}, \text{"Model"}, \text{"Data"}, \text{"Large"}, \text{"Shared"}, \text{"Data"}, \text{"Banks"}], and $\vec{c}_v = [\text{"Commun."}, \text{"ACM"}]$.$^5$. Similarly, an author “John Doe” with two citations (“John Doe, John Smith: Data Quality Algorithm, IQIS, 2005”, and “Dongwon Lee, John Doe, Jaewoo Kang: Data Cleaning for XML, ACM/IEEE Joint C. on Digital Libraries, 2005”) is represented as: $\vec{c}_c=[\text{"John Doe"}, \text{"John Smith"}, \text{"Dongwon Lee"}, \text{"Jaewoo Kang"}]$, $\vec{a}_t=[\text{"Data"}, \text{"Quality"}, \text{"Algorithm"}, \text{"Cleaning"}, \text{"XML"}]$, and $\vec{a}_v=[\text{"IQIS"}, \text{"ACM/IEEE"}, \text{"Joint"}, \text{"C."}, \text{"Digital"}, \text{"Libraries"}]. In Section 5, we study the variance of handling duplicate tokens (in set and bag models). Then, the similarity of the citation $c$ and an author “John Doe” is equivalent to: $sim(c, a)$. That is, if $sim(c, a)$ is beyond some threshold, we “guess” that $c$ is a false citation and should have been labeled under “John Doe”, not “E. F. Codd” (false positive case). When there are many such authors, we label $c$ as the author with the maximum $sim(c, a)$.

**Speed-up through Sampling.** In general, the baseline approach has a quadratic time complexity which is too expensive for large-size DLs. However, note that for a citation $c$, one does not need to check if $c$ can be labeled as an author $a$ for all authors. If one can quickly determine candidate author set from all authors (i.e., pre-filtering), then $c$ better be tested against only the authors in candidate set. We use the Gravano et al.’s approximate join algorithm introduced in Section 2 for the pre-filtering. That is,

for each citation $c_i$ ($\in C$)

<footnote>$^5$We pre-prune all stopwords from the title.</footnote>
<figure><img src="image_58.png" /><figcaption>Figure 4: Overview of our solution to SC problem.</figcaption></figure>

draw a sample set $S(\subseteq A)$;
examine all names $s_j(\in S)$;
return $s_j(\in S)$ with MAX $\phi$;

Note that the complexity is reduced to $O(|A| + |C||S|)$, that is typically more scalable than $O(|C||A|)$ since $|S| \ll |A|$.

# 4. THE SPLIT CITATION PROBLEM

## 4.1 Problem Definition & Solution Overview

We formally define the *Split Citation* problem as follows:

Given two lists of author names, X and Y, for each author name x ($\in X$), find name variants of x: $y_1, y_2, \dots, y_n$ ($\in Y$).

The baseline approach to solve the problem is to treat each author name as a “string”, and perform all pair-wise string distance using some distance function, $dist(x, y)$:

for each name $x$ ($\in X$)
for each name $y$ ($\in Y$)
if $dist(x, y) < \phi$, $x$ and $y$ are name variants;

This baseline approach has the limitations similar to the baseline approach of the MC problem in Section 3. Since the baseline approach is prohibitively expensive to run for large DLs (because of its quadratic time complexity, $O(|X||Y|)$), there is a need for more *scalable* algorithms. Furthermore, many authors from similar cultural or national background shares similar spellings in their name, those algorithms should not be too much dependent on the syntactic similarities of author-name strings.

**Solution Overview.** Figure 4 illustrates our name disambiguation algorithm: (1) Instead of syntactically comparing two name spellings alone, we use information associated with the author-name strings like coauthor list, authors' paper titles, and venue list. For instance, to identify if “Dongwon Lee” is the name variant of “D. Lee”, instead of computing the string edit distance of two names, we may test if there is any correlation between the coauthor lists of “Dongwon Lee” and “D. Lee.” In the remainder of the paper, we only focus on exploiting coauthor information as the only associated information of an author. Exploiting other associated information (or even hybrid of them as in [12]) is an inter-

<table><caption>Table 1: Solution space of name disambiguation algorithm.</caption><thead><tr><th>Method</th><th>Step 1</th><th>Step 2</th></tr></thead><tbody><tr><td>naive</td><td>1-N</td><td>-</td></tr><tr><td>two-step name-name</td><td>2-NN</td><td>name</td></tr><tr><td>two-step name-coauthor</td><td>2-NC</td><td>name</td></tr><tr><td>two-step name-hybrid</td><td>2-NH</td><td>name</td></tr></tbody></table>

esting direction for future work; (2) To make the algorithm scalable, we again borrow the sampling idea.

## 4.2 Name Disambiguation Algorithm

The name disambiguation algorithm is as follows:

/* let $C_a$ be coauthor information of author a; */
for each name $x$ ($\in X$) draw a sample set $S_x(\in S)$;
for each name $y$ ($\in Y$) /* Step 1 */
  assign $y$ to all relevant samples $S_i(\in S)$;
  for each sample $S_x(\in S)$ /* Step 2 */
    for each name $z$ ($\in S_x$)
      if $dist(C_x, C_z) < \phi$, $x$ and $z$ are name variants;

Note that the time complexity after sampling becomes $O(|X| + |Y| + |C||S|)$, where $C$ is the average number of names per sample. In general $|C||S| \ll |X||Y|$.

Depending on the choices in both Step 1 and 2, four variations of the name disambiguation algorithm are feasible, as summarized in Table 1: (1) 1-N is a single-step pair-wise name matching scheme without using sampling or coauthor information (i.e., it uses plain pair-wise author name comparison); (2) 2-NN uses the two-step approach, but do not exploit “coauthor” information; (3) 2-NC is the main proposal of ours using the sampling and exploiting “coauthor” information instead of author names; and (4) 2-NH is the modification of 2-NC in that in step 2, it combines both author and coauthor information together with proper weights (e.g., we used 1/4 and 3/4 for author and coauthor, respectively).

Although using the sampling speeds up the whole processing significantly, another important issue is to find out the right distance metric to use in Step 2. Since each author is represented as a potentially very long coauthor list, different distance metrics tend to show different accuracy/performance trade-off. To examine this issue, we have considered two supervised methods (i.e., Naive Bayes Model and Support Vector Machine) and five unsupervised methods (i.e., cosine, TFIDF, Jaccard, Jaro and JaroWinkler). In what follows, we briefly describe each method.

**Naive Bayes Model (NBM).** In this method, we use Bayes' Theorem to measure the similarity between two author names. For instance, to calculate the similarity between “Dongwon Lee” and “Lee, D.”, we estimate the probability per coauthor of “Dongwon Lee” in terms of the Bayes rule in training, and then calculate the posterior probability of “Lee, D.” with the coauthors' probability values of “Dongwon Lee” in testing. As shown in Figure 4, given a block corresponding to an author name $x$ in $X$ with the associated author names $y_i$ in $Y$ ($i \in [1, k]$, where $k$ is the total number of author names from $\hat{Y}$), we calculate the probability of each pair of $x$ and $y_i$ and find the pair with the maximal posterior probability as follows:

For training, a collection of coauthor names of $x$ are randomly split, and only the half is used for training. We estimate each coauthor's conditional probability $P(A_m|x)$
<table><caption>Table 2: Terms.</caption><thead><tr><th>Name</th><th>Description</th></tr></thead><tbody><tr><td>x, y</td><td>coauthor names</td></tr><tr><td>T<sub>x</sub></td><td>all tokens of the coauthor x</td></tr><tr><td>C<sub>x</sub></td><td>all characters of x</td></tr><tr><td>CC<sub>x,y</sub></td><td>all characters in x common with y</td></tr><tr><td>X<sub>x,y</sub></td><td># of transpositions of char. in x relative to y</td></tr></tbody></table>

conditioned on the event of $x$ from the training data set, $A_i \in \{A_1, ..., A_j, ..., A_m\}$ and $A_j$ is the $j$-th coauthor of $x$:

$$P(A_j|x) = P(A_j|\text{Frequent}, \text{Coauthor}, x) \times P(\text{Frequent}|\text{Coauthor}, x) \times P(\text{Coauthor}|x) + P(A_j|\text{Infrequent}, \text{Coauthor}, x) \times P(\text{Infrequent}|\text{Coauthor}, x) \times P(\text{Alone}|x)$$

where $P(\text{Alone}|x)$ is the probability of $x$ writing a paper alone. $P(\text{Coauthor}|x)$ is the probability of $x$ working for a paper with coauthors in future, $P(\text{Frequent}|\text{Coauthor}, x)$ is the probability of $x$ working for a paper with the coauthors, who worked with $x$ at least twice in the training data, conditioned on the event of $x$'s past coauthors, and $P(A_j|\text{Frequent}, \text{Coauthor}, x)$ is the probability of $x$ working for a paper with a particular coauthor $A_j$.

For testing, we use the following target function: $V_{NBM} = \text{MAX}_{y_i \in N}\{P(y_i)\prod_k P(A_k|y_i)\}$, where $N$ denotes the total number of author names from $Y$ in the block and $A_k$ is the $k$-th coauthor in $y_i$, being the same coauthor as in $x$.

**Support Vector Machines (SVM)** is one of the popular supervised classification methods. In our context, it works as follows: First, all coauthor information of an author in a block is transformed into vector-space representation. Author names in a block are randomly split, and 50% is used for training, and the other 50% is used for testing. Given training examples of author names labeled either YES (e.g., “J. Ullman” and “Jeffrey D. Ullman”) or NO (e.g., “J. Ullman”, “James Ullmann”), the SVM creates a maximum-margin hyperplane that splits the YES and NO training examples. In testing, given the SVM classifies vectors by mapping them via kernel trick to a high dimensional space where the two classes of equivalent pairs and different ones are separated by a hyperplane, and the corresponding similarity is obtained. For the SVM prediction, we use the Radial Basis Function (RBF) kernel [7], $K(x_i, y_i) = e^{-\gamma||x_i-y_i||^2}$, ($\gamma > 0$), among alternatives (e.g., linear, polynomial, sigmoid kernels).

**String-based Distance Metrics.** In this scheme, the distance between two author names are measured by the distance between their coauthor lists (thus no training is needed). That is, to measure the distance between “Dongwon Lee” and “Lee, D.”, instead of computing *dist* (“Dongwon Lee”, “Lee, D.”), we compute *dist*(*coauthor-list* (“Dongwon Lee”), *coauthor-list* (“Lee, D.”)). Among many possible distance measures, we used two token-based string distances (e.g., *Jaro* and *TFIDF*), and two edit-distance-based ones (e.g., *Jaro* and *JaroWinkler*) that were reported to give a good performance for the general name matching problem in [6]. We briefly describe the metrics below. For details of each metric, refer to [6].

Using the terms of Table 2, the four metrics can be defined as follows: (1) **Jaccard**($\mathbf{x}, \mathbf{y}$) = $\frac{|T_x \cap T_y|}{|T_x \cup T_y|}$; (2) **TFIDF**($\mathbf{x}, \mathbf{y}$) = $\sum_{w \in T_x \cap T_y} V(w, T_x) \times V(w, T_y)$, where $V(w, T_x) = \log(TF_{w, T_y} +$

$1) \times \frac{\log(\text{IDF}_w)}{\sqrt{\sum_{w'} (\log(\text{TF}_{w, T_y} + 1) \times \log(\text{IDF}_w))}}$ (symmetrical for $V(w, T_y)$), where $\text{TF}_{w, T_x}$ is the frequency of $w$ in $T_x$, and $\text{IDF}_w$ is the inverse of the fraction of names in a corpus containing $w$; (3) $\text{Jaro}(\mathbf{x}, \mathbf{y}) = \frac{1}{3} \times (\frac{|CC_{x,y}|}{|C_x|} + \frac{|CC_{y,x}|}{|C_y|} + \frac{|CC_{x,y} - X_{CC_{x,y}}|}{2|CC_{x,y}|})$; (4) $\text{JaroWinkler}(\mathbf{x}, \mathbf{y}) = \text{Jaro}(x, y) + \frac{\max(|L|, 4)}{10} \times (1 - \text{Jaro}(x, y))$, where $L$ is the longest common prefix of $x$ and $y$.

**Vector-based Cosine Distance.** In this approach, instead of using string distances, we use vector distances to measure the similarity of the coauthor lists. We model the coauthor lists as vectors in the vector space, each dimension of which corresponds to a unique author name appearing in the citations. To measure the distance between two vectors, $v$ and $w$, we use the simple cosine distance, an angle between two vectors, defined as: $\cos \theta = \frac{v \cdot w}{\|v\| \cdot \|w\|}$.

# 5. EXPERIMENTAL VALIDATION

## 5.1 Data Sets and Platform

We have gathered real citation data from four different domains, as summarized in Table 3. Compared to previous work, all of the four data sets are substantially “large-scale” (e.g., DBLP has 360K authors and 560K citations in it). Different disciplines appear to have slightly different citation policies and conventions. For instance, Physics and Medical communities seem to have more number of coauthors per article than Economics community. Furthermore, the conventions of citation also vary. For instance, citations in e-Print use the first name of authors as only initial, while ones in DBLP use full names. All four data sets are pre-segmented (i.e., each field of coauthors, title, and venue are already known to us).

For the sampling technique, we used the implementation of [11] with a sample $S = 64$ and a threshold $\theta = 0.1$. For the supervised learning methods, citations per author are randomly split, with half of them used for training, and the other half for testing. For the implementation of Support Vector Machines, LIBSVM<fnref n="6" /> was used. For the string-based distance functions of the unsupervised learning methods, we used the implementations of TFIDF, Jaccard, Jaro, and JaroWinkler from SecondString<fnref n="7" />. Other remaining methods were implemented by us in Java. All experimentation was done using Microsoft SQL Server 2000 on Pentium III 3GHz/512MB.

## 5.2 Results for MC Problem

**Configuration.** For this MC problem, we used two DLs out of four (due to time constraint) as test-beds: DBLP and EconPapers. For DBLP (which authors know well), we collected real examples with the MC problem: e.g., Dongwon Lee, Chen Li, Wei Liu, Prasenjit Mitra, and Wei Wang, etc, and for EconPapers (which authors do not know well), we injected an artificial “false citations” into each author’s citation collection. For both data sets, we tested how to find the “false citations” from an author’s citations (that is, we had a solution set for both cases). In constructing token vectors, we used two models, *Set* and *Bag*, depending on

<footnote n="6">⁶http://www.csie.ntu.edu.tw/~cjlin/libsvm/</footnote>

<footnote n="7">⁷http://secondstring.sourceforge.net/</footnote>
<table><caption>Table 3: Summary of data sets.</caption><thead><tr><th>Data set</th><th>Domain</th><th># of authors/<br># of citations</th><th># of coauthors per author<br>(avg/med/std-dev)</th><th># of tokens in coauthors per author<br>(avg/med/std-dev)</th></tr></thead><tbody><tr><td>DBLP</td><td>CompSci</td><td>364,377/562,978</td><td>4.9/2/7.8</td><td>11.5/6/18</td></tr><tr><td>e-Print</td><td>Physics</td><td>94,172/156,627</td><td>12.9/4/33.9</td><td>33.4/12/98.3</td></tr><tr><td>BioMed</td><td>Medical</td><td>24,098/6,169</td><td>6.1/4/4.8</td><td>13.7/12/11.0</td></tr><tr><td>EconPapers</td><td>Economics</td><td>18,399/20,486</td><td>1.5/1/1.6</td><td>3.7/3/4.1</td></tr></tbody></table>

<figure><img src="image_59.png" /><figcaption>Figure 5: Scalability (EconPapers).</figcaption></figure>

the preservation of the multiple occurrences of the same token. For testing, we used the weights, $\alpha = 0.5$, $\beta = 0.3$, and $\gamma = 0.2$. As evaluation metrics, we used *time* for scalability, and *percentage/rank* ratio for accuracy (i.e., A false citation $c_f$ must be ranked low in $sim(c_f, a)$). Thus, we measured how much percentage of false citations were ranked in the bottom 10%, 20%, etc).

**Results.** First, Figure 5 clearly shows the superior scalability of the sampling-based approach over the baseline one (about 3-4 times faster), regardless of set or bag models. Since the time complexity of the sampling-based approach is bounded by $S$, which was set to 64, for a large $C$ such as DBLP, the scalability gap between two approaches further widens. Second, Figure 6(a) illustrates the accuracy of both approaches for EconPapers. For instance, when there is a single false citation $c_f$ hidden in the 100 citations, the sampling approach with the bag model can identify $c_f$ with over 60% accuracy (i.e., rank=0.1/%=64). Furthermore, when it can return upto 2 citations as answers, its accuracy improves to over 80% (i.e., rank=0.2/%=82). Since many tokens in citations tend to co-occur (e.g., same authors tend to use the same keywords in titles), the bag model that preserves this property performs better. Finally, Figure 6(b) shows results on DBLP using only the bag model. Note that some collection has a mixture of “2” authors’ citations while others have that of “over 3” authors (e.g., there exists more than 3 authors with the same spellings of “Wei Liu”). Intuitively, collections with more number of authors’ citations mixed are more difficult to handle. For instance, when 2 authors’ citations are mixed, 100% of false citations are always ranked in the lower 30% (i.e., rank=0.3) using the sampling approach. However, when more than 3 authors’ citations are mixed, the percentages drop to mere 35% – it is very difficult to decipher a false citation when it is hidden in a collection that contains a variety of citations from many authors. We leave a solution to remedy this problem as a future work.

## 5.3 Results for SC Problem

**Configuration.** Ideally, it would be desirable to apply our

<figure><img src="image_60.png" /><figcaption>Figure 6: Accuracy (EconPapers and DBLP).</figcaption></figure>

framework to existing DLs to find all real name variants. However, given a large number of citations that we aim at, it is not possible nor practical to find a “real” solution set. For instance, to determine if “A” is indeed a name variant of “B”, human experts have to trace it carefully. Therefore, here, we use synthetic solution sets. Nevertheless, in practice, we envision that our framework be used as a tool to assist human experts to narrow down candidate name variants significantly.

To make solution sets, for each data set, we prepare two initially-empty lists, $X$ and $Y$. Then, we pick 100 authors with substantial number of citations (so that supervised methods can be trained), and put them into $X$. For each of 100 original names, $x_n$, in addition, we create an artificial name variant, $y_n$. Furthermore, citations of each $x_n$ are randomly split into two sets, and assigned to $x_n$ and $y_n$, respectively (i.e., each name carries half of the original citations). Finally, to make the disambiguation more challenging, we dump the entire author names into $Y$. For instance, for DBLP test case, there are 100 and 364,377 names in $X$ and $Y$, respectively. Then, through the proposed two-step name disambiguation algorithm, for each name in $X$, we test if the algorithm is able to find the corresponding “artificial” name variant in $Y$ (that we generated and thus know what it is).
<figure><img src="image_61.png" /><figcaption>Figure 7: Accuracy (DBLP).</figcaption></figure>

Note that the way we generate artificial name variants may affect the performance of sampling. In general, it is difficult to precisely capture the right percentages of different error types in author name variants. For the original name “Ji-Woo K. Li”, for instance, some of possible error types are name abbreviation (“J. K. Li”), name alternation (“Li, Ji-Woo K.”), typo (“Ji-Woo K. Lee” or “Jee-Woo K. Lee”), contraction (“Jiwoo K. Li”), omission (“Ji-Woo Li”), or combinations of these. To quantify the effect of error types on the accuracy of name disambiguation algorithms, we first compared two cases: (1) mixed error types of abbreviation (30%), alternation (30%), typo (12% each in first/last name), contraction (2%), omission (4%), and combination (10%); and (2) abbreviation of the first name (85%) and typo (15%). The accuracy of the former case is shown in Figure 7, and that of the latter case is in Figure 10(a). Note that regardless of the error types or their percentages, both cases show reasonably similar accuracies for all seven distance metrics (i.e., 0.8–0.9 accuracy). Therefore, all subsequent experimentations are done using the latter case (85%/15%).

**Evaluation metrics.** To measure how effectively name variants can be found, we measured the “accuracy” of top-k as follows. For a name in X, our algorithm finds top-k candidate name variants in Y. If the top-k candidates indeed contain the solution, then it’s *match*. Otherwise, it is a *mis-match*. This is repeated for all 100 names in X. Then, overall accuracy is defined as: $Accuracy = \frac{\# \text{ of matches}}{100}$. The accuracy was measured for different k values (i.e., k = 1, 5, 10). For instance, with k = 5 in the DBLP data set, for each author in X, methods return the top-5 candidate name variants out of 364,377 authors, and if one of these 5 candidates is the artificial name variant that we created, then it is a match. We repeated all of the subsequent experiments for three window sizes of 1, 5, and 10, and found that accuracies with larger window size (k = 10) are about only 10% higher than those with smaller window size (k = 1). Since the different is small, in what follows, we present the results using k = 5.

**Results.** Figure 8 summarizes the experimental results of four alternatives using three representative metrics – TFIDF, Jaccard, and Jaro. In terms of the processing time, 1-N is the slowest for TFIDF and Jaccard, as expected, due to its quadratic time complexity (i.e., $100 \times 364,377$ times of pair-wise name comparisons). The other three show similar performance thanks to the sampling. In terms of accuracy, both 2-NC and 2-NH shows about 20%-30% improvement, compared to 1-N and 2-NN, validating the assumption that

<figure><img src="image_62.png" /><figcaption>(a) Scalability</figcaption></figure>

<figure><img src="image_63.png" /><figcaption>(b) Accuracy</figcaption></figure>

<figure><img src="image_64.png" /><figcaption>Figure 9: Processing time for Step 2.</figcaption></figure>

exploiting additional information (i.e., coauthor) than the simple name spelling is beneficial. Since 2-NH shows no noticeable improvements over 2-NC, in the remaining experiments, we use 2-NC as a default scheme.

Next, we measured the processing time for step 2 alone (distance measure stage) as shown in Figure 9. In general, token-based distance metrics (e.g., TFIDF, Jaccard) outperforms edit distance based metrics (e.g., Jaro, JaroWinkler). This becomes clearly noticeable for DBLP, but not for Econ-Papers for its small size. In addition, SVM tends to take more time than the others since the hyperplane needs to be split in succession due to SVM’s binary-classifiers.

Figure 10 summarizes the accuracies of our proposal for all four data sets (with $k = 5$). In general, the distance metrics such as the SVM, cosine, TFIDF and Jaccard perform much better than the others. For DBLP data set, most distance metrics achieved upto 0.93 accuracy, finding most of 100 name variants out of 364,377 candidates. For e-Print data set, the accuracy drops down, except the SVM, and for BioMed data set, it gets worse (especially for Jaro and JaroWinkler).

The accuracies of DBLP and e-Print data sets are better than that of BioMed data set. The poor performance of BioMed case is mainly due to the small number of citations
<figure><img src="image_65.png" /><figcaption>Figure 10: Accuracy ($k = 5$).</figcaption></figure>

per authors in data set. Since 2-NC scheme is exploiting coauthor information of the author in question to find name variants, the existence of “common” coauthor names is a must. However, in the BioMed data set, each author has only a small number of citations, 1.18, on average, and only small number of coauthors, 6.1, on average, making a total number of coauthors as $7.19 = 1.18 \times 6.1$ (assuming all coauthors are distinct). Therefore, for two arbitrary author names $x$ and $y$, the probability of having “common” coauthors in BioMed data set is not high. On the other hand, for the e-Print data set, the average number of citations (resp. coauthors) per author is higher, 4.27 (resp. 12.94), making a total number of coauthors as $55.25 = 4.27 \times 12.94$ – roughly 8 times of the BioMed data set.

In general, Jaro or JaroWinkler method in step 2 gave poorer accuracy than the others. Since they are edit-distance based methods that are heavily affected by the number of transpositions, as the length of string to compare increases (in 2-NC, it is a long coauthor string to compare), its error rate increases as well. In the e-Print data set, the accuracies are lower, compared to those of DBLP. This is because most of citations in e-Print data set use abbreviation for the first name of authors. Since the sampling technique uses TFIDF for weighting tokens, common tokens like abbreviated first name (e.g., “E.” or “P.”) would have lower weight via IDF, negatively affecting matching process.

## 6. CONCLUSION

Two interesting and practical problems – *Mixed Citation* and *Split Citation* – are formally introduced and their solutions are explored. Since both problems commonly occur in many of the existing bibliographic digital libraries, it is important to devise effective and efficient solutions to them. By utilizing one of the state-of-the-art sampling-based approximate join techniques, our solutions are scalable yet highly effective. Furthermore, our proposals exploit associated information of author names (e.g., coauthors, titles, or venues) than names themselves, achieving 90-93% accuracy overall.

As to future direction, in addition to comparing ours against others (e.g., [2, 22]), we plan to apply our framework to other domains (e.g., address, movie) to test its generality.

## 7. REFERENCES

[1] R. Ananthakrishna, S. Chaudhuri, and V. Ganti. “Eliminating Fuzzy Duplicates in Data Warehouses”. In VLDB, 2002.

[2] I. Bhattacharya and L. Getoor. “Iterative Record Linkage for Cleaning and Integration”. In ACM SIGMOD

Workshop on Research Issues in Data Mining and Knowledge Discovery, 2004.

[3] M. Bilenko, R. Mooney, W. Cohen, P. Ravikumar, and S. Fienberg. “Adaptive Name-Matching in Information Integration”. *IEEE Intelligent System*, 18(5):16–23, 2003.

[4] V. R. Borkar, K. Deshmukh, and S. Sarawagi. “Automatic Segmentation of Text into Structured Records”. In *ACM SIGMOD*, 2001.

[5] S. Chaudhuri, K. Ganjam, V. Ganti, and R. Motwani. “Robust and Efficient Fuzzy Match for Online Data Cleaning”. In *ACM SIGMOD*, 2003.

[6] W. Cohen, P. Ravikumar, and S. Fienberg. “A Comparison of String Distance Metrics for Name-matching tasks”. In *IIWeb Workshop held in conjunction with IJCAI*, 2003.

[7] N. Cristianini and J. Shawe-Taylor. “*An Introduction to Support Vector Machines*”. Cambridge U. Press, 2000.

[8] J. M. B. Cruz, N. J. R. Klink, and T. Krichel. “Personal Data in a Large Digital Library”. In *ECDL*, 2000.

[9] P. T. Davis, D. K. Elson, and J. L. Klavans. “Methods for Precise Named Entity Matching in Digital Collection”. In *ACM/IEEE JCDL*, 2003.

[10] I. P. Fellegi and A. B. Sunter. “A Theory for Record Linkage”. *J. of the American Statistical Society*, 64:1183–1210, 1969.

[11] L. Gravano, P. G. Ipeirotis, N. Koudas, and D. Srivastava. “Text Joins in an RDBMS for Web Data Integration”. In *WWW*, 2003.

[12] H. Han, C. L. Giles, H. Zha, C. Li, and K. Tsioutsiouliklis. “Two Supervised Learning Approaches for Name Disambiguation in Author Citations”. In *ACM/IEEE JCDL*, Jun. 2004.

[13] M. A. Hernandez and S. J. Stolfo. “The Merge/Purge Problem for Large Databases”. In *ACM SIGMOD*, 1995.

[14] Y. Hong, B.-W. On, and D. Lee. “System Support for Name Authority Control Problem in Digital Libraries: OpenDBLP Approach”. In *ECDL*, 2004.

[15] J. A. Hylton. “*Identifying and Merging Related Bibliographic Records*”. PhD thesis, Dept. of EECS, MIT, 1996. LCS Technical Report MIT/LCS/TR-678.

[16] M. A. Jaro. “Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida”. *J. of the American Statistical Association*, 84(406), 1989.

[17] R. P. Kelley. “Blocking Considerations for Record Linkage Under Conditions of Uncertainty”. In *Proc. of Social Statistics Section*, pages 602–605, 1984.

[18] S. Lawrence, C. L. Giles, and K. Bollacker. “Digital Libraries and Autonomous Citation Indexing”. *IEEE Computer*, 32(6):67–71, 1999.

[19] A. McCallum et al. “Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching”. In *ACM KDD*, 2000.

[20] B.-W. On, D. Lee, J. Kang, and P. Mitra. “Comparative Study of Name Disambiguation Problem using a Scalable Blocking-based Framework”. In *ACM/IEEE JCDL*, 2005.

[21] H. Pasula et al. “Identity Uncertainty and Citation Matching”. In *Advances in Neural Information Processing Systems*. MIT Press, 2003.

[22] S. Sarawagi and A. Bhamidipaty. “Interactive Deduplication using Active Learning”. In *ACM KDD*, 2002.

[23] M. M. M. Synman and M. Rensburg. “Revolutionizing Name Authority Control”. In *ACM DL*, 2000.

[24] J. W. Warnner and E. W. Brown. “Automated Name Authority Control”. In *ACM/IEEE JCDL*, 2001.

[25] W. E. Winkler and Y. Thibaudeau. “An Application of the Fellegi-Sunter Model of Record Linkage to the 1990 U.S. Decennial Census”. Technical report, US Bureau of the Census, 1991.