Ayat Naser

Reza Akbarinia

Hamideh Afsarmanesh
email: 2h.afsarmanesh@uva.nl

Patrick Valduriez

Naser Ayat
email: s.n.ayat@uva.nl

Hamideh Afsarmanesh #

Entity Resolution for Probabilistic Data

Keywords:

INTRODUCTION

In recent years, we have been witnessing much interest in uncertain data management in many application areas such as data integration [START_REF] Magnani | Uncertainty in data integration: current approaches and open problems[END_REF][START_REF] Ayat | An uncertain data integration system[END_REF], sensor networks [START_REF] Deshpande | Model-driven data acquisition in sensor networks[END_REF], information extraction [START_REF] Jayram | Avatar information extraction system[END_REF], etc. Much research effort has been devoted to several aspects of uncertain data management, including data modeling [START_REF] Sarma | Working models for uncertain data[END_REF][START_REF] Benjelloun | Uldbs: Databases with uncertainty and lineage[END_REF], skyline queries [START_REF] Atallah | Computing all skyline probabilities for uncertain data[END_REF], top-k queries [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Soliman | Top-k query processing in uncertain databases[END_REF][START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF][START_REF] Re | Efficient top-k query evaluation on probabilistic data[END_REF], nearest neighbor search [START_REF] Yuen | Superseding nearest neighbor search on uncertain spatial databases[END_REF], XML documents [START_REF] Abiteboul | On the expressiveness of probabilistic xml models[END_REF], etc. Untrusted sources, imprecise measuring instruments, and uncertain methods, are some reasons that cause uncertainty in data. The main difference between a traditional certain database and an uncertain database is that an uncertain database represents a set of possible database instances, rather than a single one. Recent uncertain data models tend to represent data uncertainty with probabilistic events [START_REF] Antova | Fast and simple relational processing of uncertain data[END_REF][START_REF] Sarma | Working models for uncertain data[END_REF][START_REF] Benjelloun | Uldbs: Databases with uncertainty and lineage[END_REF].

An important problem that arises in many applications such as information integration is that of Entity Resolution (ER) [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. ER is the process of identifying tuples that represent the same real-world entity. For instance, consider the two tuples ("Thomas Michaelis", "45, Main street") and ("T. Michaelis", "45, Main st.") on the schema S(name, address) that represent the same person with different conventions. An ER solution is expected to detect that both tuples represent the same entity. The problem of ER is challenging since the same entity can be encoded in different ways due to a variety of reasons such as different formatting conventions, abbreviations, and typographic errors. It has been well studied in the literature for certain data (refer to [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF] for a survey), but it has not been deeply investigated for probabilistic data. Before discussing existing solutions, let us first motivate the need for ER in probabilistic data (which we call ERPD), with two examples from scientific data management and anti-criminal domains.

Example 1: Finding astronomical objects in astrophysics data. In astrophysics, as well as in other scientific disciplines, the correlation and integration of observational data is the key for gaining new scientific insights. Astronomical observatories produce data about sky surveys, most of which is probabilistic [START_REF] Peng | Optimizing probabilistic query processing on continuous uncertain data[END_REF]. In its simplified form, an observatory maintains a single probabilistic relation Objects that contains data about the observed astronomical objects in the sky surveys. Each object is represented using a number of alternative tuples each with a membership probability showing its degree of certainty which is computed using some rules. The alternatives are disjoint, meaning that at most one of them can be true. The uncertainty model, which is used in this example, has been widely used in the database literature for representing probabilistic data, e.g. [START_REF] Sarma | Working models for uncertain data[END_REF][START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF][START_REF] Benjelloun | Uldbs: Databases with uncertainty and lineage[END_REF][START_REF] Cheng | Cleaning uncertain data with quality guarantees[END_REF], and also for representing astrophysics data [START_REF] Suciu | Embracing uncertainty in large-scale computational astrophysics[END_REF]. The astrophysics researchers who want to track a particular astronomical object, which has been represented by an uncertain entity e, are very interested in queries like the following: among astronomical objects observed in a sky region, find the object which is most probably the same object as e.

Example 2: Suspect detection in anti-criminal police database. The anti-criminal police is faced with many crimes every year. It spends a lot of time and money gathering data about every crime from different sources such as witnesses, interrogations, and police's informants. Some of the gathered data are not certain, for some reasons, e.g. the police cannot completely trust informants and witnesses. To represent this uncertainty, probability values can be attached to the data to show their likelihood of truth according to the confidence on the sources. These probabilistic data are used to find possible suspects, and can greatly speed up the investigation process. In a very simplified form, the police maintains a single relation Suspects that contains data about suspects. In this relation, each individual suspect is represented using an entity consisting of a number of alternative tuples each associated with a probability value showing its likelihood of truth. When a crime occurs, detectives gather data about the perpetrator, and the gathered data can be represented in the form of an uncertain entity, say e. To get more information about the perpetrator represented by e, detectives are interested in the following query: find in the uncertain database the person who is most probably the same person as e. Notice that if there is more than one perpetrator, the police can represent each one using an uncertain entity and repeat the process for each entity.

Existing proposals for the ER problem are not applicable to the above examples since they ignore probability values completely and return the most similar tuples as the solution. To the best of our knowledge, the works presented in [START_REF] Menestrina | Generic entity resolution with data confidences[END_REF] and [START_REF] Panse | Duplicate detection in probabilistic data[END_REF] are the only proposals for dealing with the ERPD problem. The proposal in [START_REF] Menestrina | Generic entity resolution with data confidences[END_REF] ignores the probability values and the proposal in [START_REF] Panse | Duplicate detection in probabilistic data[END_REF] uses the probability values only for normalizing the similarity of the uncertain entities. These proposals do not define the ERPD problem based on both similarity and probability of tuples. Consequently, they are not appropriate for answering the queries issued in the above examples.

Inspired by the literature on uncertain data management, in this paper we adopt the well-known possible worlds semantics for defining the semantics for the ERPD problem and propose efficient algorithms for computing it. However, developing an efficient solution for the ERPD problem is challenging, particularly due to the following reasons. First, we must take into account two parameters for matching the entities: the similarity and the probability values. Second, due to the uncertainty in the entity e, there may be different similarity values between e and the tuples of D. Third, in the case of context-sensitive similarity functions (see the definition in Section 3), the similarity of two entities may be different in different possible worlds, i.e. in different instances of the database. A naïve solution for ERPD involves enumerating all possible worlds of the uncertain entity and the database. However, this solution is exponential in the number of tuples of D.

In this paper, we address the ERPD problem and propose a complete solution for it. Our contributions are summarized as follows:

-We adapt the possible worlds semantics of probabilistic data to define the problem of ERPD based on both similarity and probability of tuples. -We propose a PTIME algorithm for the ERPD problem. This algorithm is applicable to a large class of the similarity functions, i. We conducted an extensive experimental study to evaluate our approach for ERPD over both real and synthetic datasets. The results show the effectiveness of our algorithms. To the best of our knowledge, this is the first study of the ERPD problem that adopts the possible world semantics and develops efficient algorithms for it.

The rest of the paper is organized as follows. In Section 2, we present our probabilistic data model, and define the problem we address. In Section 3, we propose our solution for the ERPD problem for context-free similarity functions. In section 4, we propose our solution for dealing with the ERPD problem when the similarity function is context-sensitive. In section 5, we report the performance evaluation of our techniques over synthesis and real data sets. Section 6 discusses related work. Section 7 concludes.

World w P(w) {t 1,1 } 0.6 × (1 -0.4) = 0.36 {t 1,2 } 0.4 × (1 -0.4) = 0.24 {t 1,1 , t 2,1 } 0.6 × 0.4 = 0.24 {t 1,2 , t 2,1 } 0.4 × 0.4 = 0.16 (c)

PROBLEM DEFINITION

In this section, we first give our assumptions regarding the probabilistic data model. Then, we define the problem which we address.

probabilistic Data Model

For representing an uncertain entity, we use the x-tuple data model [START_REF] Agrawal | Trio: A system for data, uncertainty, and lineage[END_REF], and represent each entity as an x-tuple. In each x-tuple there are several possible tuples, called alternatives. Each alternative is associated with a probability value showing its likelihood of truth. The alternatives are mutually exclusive, meaning that at most one of them can be true, and the sum of the confidence values of the alternatives is less than or equal to one. As an example of x-tuple, consider the entity e in Figure 1(a). Notice that either t e,1 or t e,2 is true. The uncertain database D (called also x-relation) consists of a set of pairwise disjoint x-tuples that are subject of independent probabilistic events. Formally,

D = {e 1 , . . . , e N }, e i = {t i,1 , . . . , t i,|e i | }, e i ∅, e i ∩ e j = ∅, i, j ∈ [1..N].
We use D to denote the set of all tuples in D. Figure 1(b) shows an example of x-relation, named Suspects. In the Suspects relation, t 1,1 and t 1,2 together form one x-tuple, and t 2,1 , by itself, form another x-tuple.

An uncertain database D can be interpreted as the set of all possible certain database instances, called possible worlds and denoted by PW(D), each with a probability of occurrence. Figure 1(c) shows the possible worlds set of the uncertain database Suspects and the probability of each member of this set.

We define the possible worlds set of an uncertain entity e and an uncertain database D, denoted by PW(e, D), as follows:

PW(e, D)

= {w | w = {t} × v, t ∈ e, v ∈ PW(D)} .
Notice that in each possible world w ∈ PW(e, D) only one alternative of the uncertain entity e is valid. As an example, Figure 2(b) shows all eight members of PW(e, Suspects) together with their probability of occurrence. Notice that the members of each possible world w ∈ PW(e, D) are tuple pairs in the from of (t, t ), where t ∈ e and t ∈ D.

Problem Statement

In a certain database, the problem of entity resolution is defined as follows [START_REF] Chaudhuri | Robust and efficient fuzzy match for online data cleaning[END_REF]: given an entity (e.g. tuple) e and a database D, find t max ∈ D such that t max has the maximum similarity to e. While the problem of finding t max is semantically clear in certain data, its semantics is not clear in probabilistic data since we have to consider two parameters: similarity and probability. In this section, we use the possible worlds semantics for defining the semantics of the ERPD problem.

Let us first consider the case where the entity e has a single alternative. In this case, the probability that a tuple t ∈ D be the most similar to e, say P MSP (t), is equal to the cumulative probability of the possible worlds where t is t max , i.e. the most similar tuple to e. We denote the tuple with maximum P MSP as the most-probable match tuple for entity e.

In the case where the entity e has multiple alternatives, the most-probable match tuple needs to be extended by the alternative of e with which it is the most-probable match tuple, say pair (t, t ), t ∈ e, t ∈ D. We refer to this pair as most-probable match pair and we use the first element of the pair for tuples in entity e and the second element for tuples in D. In addition to the most-probable match pair concept, uncertain data enables us to define another new and their probability to be MSP (P MSP ); d) entities and their P MSP concept, which does not make sense in certain data: most-probable match entity. The most-probable match entity e is an entity in D that has the highest probability of being most similar to e. Also to avoid repetition, we refer to the two concepts of the most-probable match pair and the most-probable match entity as most-probable matches. Let us intuitively explain these concepts using an example. Example 3. Consider the entity e and the Suspects database in the Figures 1(a) and 1(b) respectively. Let F be a similarity function that ranks all possible tuple pairs of e and S uspects as they appear in Figure 2(a). Figure 2(b) shows the eight possible worlds of PW(e, S uspects), the probability of each world, and the most similar pair (MSP) in each world. The result of computing P MSP for all pairs is shown in Figure 2(c). For instance, pair (t e,1 , t 2,1 ) is MSP in w 3 and w 4 , thus, the cumulative probability that (t e,1 , t 2,1 ) is the most similar pair (denoted as P MSP ), is the sum of the probabilities of w 3 and w 4 . We observe that pair (t e,2 , t 2,1 ) is the most-probable match pair since it has the maximum P MSP among all other pairs. Figure 2(c) shows the result of computing P MSP for all entities in the Suspects database. This figure shows that e 1 is the most-probable match entity for entity e since it has the maximum P MSP among all entities in the database.

We now formally define the concept of most-probable matches.

Definition 1. Most-probable matches:

Let D be an uncertain database on schema S D . Let e be an uncertain entity on schema S e and S e ⊆ S D . Let w ∈ PW(e, D) be a possible world and P(w) be the probability that w occurs. Let F be a similarity function for computing the similarity between tuples. Let the most similar pair of a world w, denoted as MSP(w), be the pair that has the maximum similarity value among the pairs in w according to similarity function F. Let ρ be an tuple pair in e × D. Let P MSP (ρ) be the aggregated probability that pair ρ is the most similar pair in PW(e, D), i.e. As mentioned earlier, we refer to these concepts as most-probable matches.

The entity resolution approach strongly depends on the given similarity function. The similarity functions in the literature can be categorized into two classes: context-free and context-sensitive. In a context-free similarity function, the similarity value of two tuples only depends on their attribute values. Jaro-Winkler [START_REF] Winkler | An Application Of The Fellegi-Sunter Model Of Record Linkage To The[END_REF], Monge-Elkan [START_REF] Monge | The field matching problem: Algorithms and applications[END_REF][START_REF] Monge | An efficient domain-independent algorithm for detecting approximately duplicate database records[END_REF] and Levenshtein [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF] are examples of context-free similarity functions. On the other hand, in a context-sensitive similarity function, the similarity value of two tuples depends on the attribute values of the two tuples and also on the relation to which they belong. This means that the similarity of two tuples may change when the other tuples of the relation change. TFIDF [START_REF] Cohen | Integration of heterogeneous databases without common domains using queries based on textual similarity[END_REF] and Ranked-List-Merging [START_REF] Guha | Merging the results of approximate match operations[END_REF] are examples of context-sensitive similarity functions.

Given uncertain entity e, uncertain database D, and similarity function F, our goal is to efficiently find the mostprobable matches. In Sections 3 and 4, we present our approach for finding the most-probable matches, respectively, for the context-free and context-sensitive similarity functions.

Context-free Entity Resolution

In this section, we consider a context free similarity function for the ERPD problem, and propose an efficient algorithm for dealing with this problem. Then, we present two improved versions of our algorithm.

The straightforward approach for computing the most-probable matches is to enumerate PW(e, D). This approach does not scale well due to the exponential number of members of set PW(e, D).

In the case of context-free similarity function, the similarity score of a tuple pair remains constant in all possible worlds where the tuple pair appears. We rely on this fact to efficiently compute the most-probable matches without enumerating the possible worlds set PW(e, D).

Let S be the set of all tuple pairs, i.e. S = e × D. Let ρ = (t, t i ) be a tuple pair in set S . Since alternative tuples of e are mutually exclusive, there is no possible world in PW(e, D) containing pair ρ together with pair ρ = (t , t j ), where ρ ∈ S , and t t . Thus, to compute P MSP (ρ), we just have to consider the subset of tuple pairs in S which have t as their first elements, i.e. set {t} × D. We use this fact to compute P MSP (ρ).

Let L = {t 1 , . . . , t n } be the list of D tuples sorted based on their similarity with t ∈ e in descending order. Let (t, t i ) be a tuple pair where t i is the tuple which lies in the ith index of the sorted list L. We can calculate P MSP (t, t i ) as the intersection of two independent events: t occurs; and among tuples t 1 to t i , only t i occurs. Considering x-tuple correlations in calculating the probability of the latter event, we can calculate P MSP (t, t i ) as

P MSP (t, t i ) = P(t) × P(t i ) × x∈X i (1 -P(x)) (1)
where P is the occurrence probability of a tuple or x-tuple, and X i is the set of x-tuples formed by considering x-tuple correlations between the tuples t 1 to t i-1 while the x-tuple containing t i is omitted from it. Using (1), the context-free algorithm, denoted as CFA algorithm, computes P MSP of all tuple pairs in set S and then use the computed P MSP s to compute the most-probable matches. Algorithm 1 describes the details of our method for computing the most-probable matches. This algorithm takes as input an uncertain x-relation database D, uncertain x-tuple entity e, and context-free similarity function Sim. Steps 4-11 are repeated for every alternative t of e. Step 4 computes the similarity score of t to every tuple of D; sorts the tuples based on their similarity scores; and stores the result in list L. For each tuple L[i] in list L, steps 6-9 compute P MSP (t, L[i]). Using (1), we know that P MSP (t, L[i]) is the intersection of two independent events: t occurs; and among tuples L [START_REF] Magnani | Uncertainty in data integration: current approaches and open problems[END_REF] to L[i] only L[i] occurs. For computing the probability of the latter event, the correlated tuples have to be grouped together. This is done by steps 6-8. Step 6 puts the tuples L [START_REF] Magnani | Uncertainty in data integration: current approaches and open problems[END_REF] to L[i] in the set T and step 7 obtains the intersection of every x-tuple in D with the members of T . The resulted set, i.e. X, contains the tuples of T grouped into a number of x-tuples. Step 8 finds the x-tuple in X that includes tuple L[i] and removes it from X. Using equation (1), Step 9 computes the P MSP of the pair (t, L[i]). When the algorithm finishes computing the P MSP of all pairs, step 13 finds the most-probable matches. This step finds the most-probable match pair by finding the record in set R with the maximum value for P MSP field. The most-probable match entity can be computed by aggregating the P MSP field for every entity e i ∈ D and then finding the entity with maximum aggregated P MSP value.

Let us analyze the execution time of CFA algorithm. Let n be the number of tuples involved in D, and m be the number of alternatives of e.

for all i ∈ [1.. |L|] do 6: T ← {L[1], . . . , L[i]} 7: X ← {x | x = x ∩ T, x ∈ D, x ∅} 8: X ← X -{x | x ∈ X, x ∩ L[i] ∅} 9: P MSP ← P (L[i]) × P(t) × x∈X 1 - t∈x P(t) 10: add record (t, L[i], P MSP ) to set R 11:
end for 12: end for 13: find the most-probable matches using set R and return them

Improving CFA Algorithm

In this section, we improve the efficiency of the CFA algorithm by computing the P MSP of a subset of pairs in set e × D. We consider two versions of the CFA algorithm as follws:

-CFA-MPMP: this version only computes MPMP(e, D), i.e. the most-probable match pair.

-CFA-MPME: this version only computes MPME(e, D), i.e. the most-probable match entity.

CFA-MPMP Algorithm Consider the sorted list L in the CFA algorithm. The core idea in improving CFA is that after computing P MSP (t, L[i]), we compute the upper bound on the P MSP values that we obtain if we continue processing list L. If the computed upper bound is smaller than the maximum P MSP value which has been computed so far, then we stop processing list L. We denote this upper bound as Potential(t, L[i]). The following lemma computes the Potential of a tuple pair. Lemma 1. Let L[i] be the tuple which lies in the ith location of list L. Let Y i be the set of x-tuples formed by considering correlations between the tuples {L [START_REF] Magnani | Uncertainty in data integration: current approaches and open problems[END_REF]

, . . . , L[i]}, then Potential (t, L[i]) = P(t) × x∈Y i (1 -P(x)).
Proof. Based on its definition, Potential(t, L[i]) is an upper bound on P MSP (t, t ), where t is a tuple which comes after

L[i] in list L. We show that P MSP (t, t ) is maximized when t = L[i + 1] and P(t ) = 1.
Let W be the set {w | w ∈ PW(e, D), MSP(w) = (t, L[ j]), j > i} and P(W) be the probability that a member of W occurs. Since P(t ) = 1, it is clear that tuple pair (t, t ) exists in all members of W and is MSP in each of them. Thus, P msp (t, t ) is equal to P(W) which is the maximum possible value for P msp (t, L[ j]), where j > i. Using (1) and setting the value of P(L[i + 1]) to one, we have

P MSP (t, L[i + 1]) = P(t) × x∈Y i (1 -P(x)) = RHS (1)
where Y i is the set of x-tuples formed by considering correlations between the tuples {L [START_REF] Magnani | Uncertainty in data integration: current approaches and open problems[END_REF] Let us illustrate the CFA-MPMP algorithm using an example. Consider uncertain entity e and uncertain database D shown in Figures 3(a) and 3(b) respectively. Let Sim be a context-free similarity function. Let L, shown in Figure 3(c), be the list of D's tuples sorted based on their similarity with t e,1 , where the similarity scores are computed using Sim.

Visiting the first tuple in L, the P MSP (t e,1 , t 2,2 ) is equal to the probability of the event that t e,1 and t 2,2 occur, thus, P MSP (t e,1 , t 2,2 ) is equal to P(t e,1 ) × P(t 2,2 ) = 0.08. The Potential of this pair is equal to the probability of the event that t e,1 occurs but t 2,2 does not occur, which is equal to P(t e,1 ) × (1 -P(t 2,2 )) = 0.72. This is an upper bound on the P MSP values that we obtain if we continue processing list L. Since the computed Potential is greater than the so far computed maximum P MSP value, i.e. 0.08, we continue processing the list.

Visiting the second tuple in L, the P MSP (t e,1 , t 4,1 ) is equal to the probability of the event that t e,1 and t 4,1 occur but t 2,2 does not occur, which is equal to P(t e,1 ) × P(t 4,1 ) × (1 -P(t 2,2 )) = 0.504. The Potential of this pair is equal to the probability of the event that t e,1 occurs but neither t 2,2 nor t 4,1 occurs, which is equal to P(t e,1 ) × (1 -P(t 2,2 )) × (1 -P(t 4,1 )) = 0.216. At this point, we stop processing the list since the computed Potential is less than the so far computed maximum P MSP value, i.e. 0.504.

It is not necessary to consider the tuple pairs whose first element is t e,2 because the upper bound on their P MSP values is P(t e,2 ) = 0.1, which is less than the so far computed maximum P MSP . Thus, P MSP (t e,1 , t 4,1 ) is maximum among all pairs, and (t e,1 , t 4,1 ) is MPMP(e, D). Notice that we only process two pairs out of the whole 16 pairs to compute MPMP(e, D).

CFA-MPME Algorithm

We know that sum of the P MSP of all pairs is equal to sum of the probabilities of e's alternatives, i.e. ρ∈e×D P MSP (ρ) = t∈e P(t). We use this fact to stop the CFA algorithm when the so far computed most-probable match entity (i.e. MPME) remains the same even if we continue the algorithm.

Let us define the stop condition more precisely. Let C be the set of pairs that we have computed their P MSP s so far. Let e i be an entity in D and P agg (e i ) be its so-far computed aggregated probability to be MPME, i.e. P agg (e i ) = (t,t )∈C,t ∈e i P MSP (t, t ) let e max be the entity with maximum P agg value. Then, the stop condition can be written as follows:

∀e i ∈ D, P agg (e i ) +         t∈e P(t) - ρ∈C P MSP (ρ)         < P agg (e max )
We check the stop condition after computing P MSP in Step 9 of Algorithm 1, and finish the algorithm if the condition is met.

As an example consider uncertain entity e and uncertain database D shown in Figures 3(a) and 3(b) respectively. The sum of the probabilities of e's alternatives is equal to 0.9. Visiting the first two pairs of list L, shown in Figure 3(c), and computing P MSP (t e,1 , t 2,2 ) and P MSP (t e,1 , t 4,1 ), we have: P agg (e 1 ) = 0, P agg (e 2 ) = 0.08, P agg (e 3 ) = 0, and P agg (e 4 ) = 0.504. The sum of so far computed P MSP s is equal to 0.584 and the sum of uncomputed P MSP s is equal to 0.9 -0.584 = 0.316. The entity e 4 is MPME since even if all uncomputed P MSP s are from an entity other than e 4 , its P agg is still less than that of e 4 .

Context-sensitive Entity Resolution

In this section, we consider a context-sensitive similarity function for the ERPD problem, and present a Monte Carlo approach for approximating the most-probable matches. Then, we propose two solutions for improving the performance of the Monte Carlo algorithm.

Monte Carlo Algorithm

When the similarity function is context-sensitive, the similarity between two tuples may change when the contents of the database changes. For instance when using TFIDF, adding or removing tuples to/from database, may change the frequency of the terms in the database, which in turn changes the similarity score of two tuples. This means that the similarity of two tuples in different possible worlds does not remain constant. Therefore, we cannot use the CFA algorithm for computing most-probable matches.

In the absence of an efficient exact algorithm for ERPD in the case of context-sensitive similarity functions, we use the randomized algorithm Monte Carlo (MC) for approximating the answer. The MC algorithm repeatedly chooses at random a possible world and an alternative of the uncertain entity, and computes the tuple pair that is the most similar. For each pair ρ = (t, t ), the probability P MSP (ρ) of being the most similar match, is approximated by P MSP (ρ), which is the fraction of times that t was the most similar to t in the sampled possible worlds. The MC algorithm guarantees that after sampling M possible worlds, P MSP (ρ) is in the interval P MSP (ρ) -zδ √ M , P MSP (ρ) + zδ √ M with the confidence 1 -δ, where P {-z ≤ N(0, 1) ≤ z} = 1 -δ, N(0, 1) is the standard normal distribution, and δ is the deviation of the distribution.

Notice that the probabilities of the individual possible worlds are taken into account in the way that a high probable possible world is chosen with a higher likelihood than a less probable world.

Parallel MC

In this section, we improve the performance of the MC algorithm by proposing a parallel version of this algorithm, denoted as MC-MapReduce, using the MapReduce framework.

MapReduce provides a framework for performing a two-phase distributed computation on large datasets. In the Map phase, the system partitions the input dataset into a set of disjoint units (denoted as input splits) which are assigned to workers, known as mappers. In parallel, each mapper scans its input split and applies a user-specified map function to each record in the input split. The output of the user's map function is a set of key, value pairs which are collected for MapReduce's Reduce phase. In the reduce phase, the key-value pairs are grouped by key and are distributed to a series of workers, called reducers. Each reducer then applies a user-specified reduce function to all the values for a key and outputs a final value for the key. The collection of final values from all of the reducers is the final output of MapReduce.

Given an uncertain entity e, an uncertain database D, and M as the number of iterations in the MC algorithm, the idea of our MC-MapReduce algorithm is to ask M mappers to do one iteration of the MC algorithm in parallel, then collect the results of mappers in the reduce phase, and compute the most-probable matches.

MC-MapReduce algorithm works as follows. It gets the uncertain entity e, uncertain database D, and the required parameters of the MC algorithm (e.g. δ and ) as input and computes M as the number of possible worlds that it should sample to obtain the desired confidence. Then, MC-MapReduce assigns M mappers to do the map function.

Algorithm 2 shows the pseudo code of the map function. This algorithm gets e and D, and a context-sensitive similarity function S im as input. Steps 1-2 generate an alternative of e, say t, and a possible world of D, say W, at random. Step 3 computes the most-similar tuple of W to t, say t max . Steps 4-6 return the key-value pair (t, t max ), 1 as the output of the map function; meaning that the pair (t, t max ) has been the most-similar pair in one possible world.

Algorithm 2 Map function

Input:

- The MapReduce framework receives all generated pairs and sends all pairs with the same key, i.e. (t, t ), and the set of their values, i.e. 1, to one reducer function. Algorithm 3 shows the pseudo code of the reduce function. This algorithm gets (t, t ) as key and the set of values V, which all of its members are 1, as input. Then, it simply counts the number of members of V and generates the final key-value pair (t, t ), |V| as the output of the reduce function.

Algorithm 4 shows the steps which are performed by MC-MapReduce after all mappers and reducers finish their task. This algorithm gets all key-value pairs (t, t ), v as input. Then, it approximates P MSP of tuple pair (t, t ) by dividing the number of times that it has been the most-similar pair, i.e. v, by M, i.e. the sum of occurrence of all tuple pairs. Using these probabilities, MC-MapReduce approximately computes the most-probable matches.

CB Similarity Function

In this section, we improve the performance of the MC algorithm by proposing a new context-sensitive similarity function appropriate for MC computation. As we will show in Section 5, our similarity function significantly outperforms the baseline context-sensitive similarity functions in terms of success rate and response time.

To the best of our knowledge, all context-sensitive similarity functions in the literature need a setup time for at least one pass over the database to compute some statistical features of the data. For example TFIDF similarity function needs to compute term and document frequencies to be able to operate. In many applications, spending some time for setting up the similarity function is reasonable since we setup the function once and use it many times. However, this is not the case for our MC algorithm because for each selected possible world, we have to spend a significant time to setup the similarity function that is used once, only for the selected possible world.

In this section, we propose CB (Community Based), a novel similarity function which avoids this problem since it does not need any time to setup. In fact, setting up the function and computing the similarities happen at the same time. It gives more importance to the more discriminative attributes of the two tuples by introducing the novel concept of community. A community C of a relation D is defined as the largest subset of D's tuples that are similar, i.e. their similarity is more than a certain threshold, based on a non-empty subset of D's attributes. In CB, the similarity of two tuples depends on the size of the most specific community to which they belong. The smaller the size of the community, the more similar are the two tuples.

For computing the similarity of a tuple t to a given tuple t, CB finds the smallest community to which t and t belong, say community C, and returns 1 -log|C| log|D| as the similarity score of t and t . If no community involves both t and t , then CB returns 0 as similarity score. Indeed, if two tuples do not belong to any common community, they are not similar at all. Figure 4(b) shows an example relation D on the schema S D (gender, city, age-range) for describing people. As an example, let us take community C 1 = {t 3 , t 4 , t 5 , t 6 , t 7 , t 8 } that represents females and community C 2 = {t 6 , t 7 , t 8 } that contains all females who live in city 'A'. Figure 4(a) shows an example tuple t and Figure 4(c) shows the similarity of all tuples of relation D to t. For instance, tuple t 8 is similar to t in gender and city attributes. Therefore, the smallest community involving t and t 8 is the community of females who live in city 'A', which includes tuples t 6 , t 7 , and t 8 . Notice that there is no need for attribute values to be equal, but their similarity should be greater than a predefined threshold. We may use any string similarity function for obtaining the similarity of individual attribute values.

CB is context-sensitive since the similarity of two tuples depends not only on their attribute values, but also on the other tuples of the relation to which they belong. An important property of CB is that the similarity value drops as the tuples with matching values grows. In other words, a match between tuples is a stronger match if there aren't many of them that are the same. For instance, a tuple that is matched to a single other tuple is more important than matching with 100 other tuples. Let us now formally define CB. Definition 2. CB similarity function: Let D be a relation on schema S D and t be a tuple on schema S t and S t ⊆ S D . Suppose F is a similarity function that computes the similarity between two attribute values from the same domain. Let S i ⊆ (S D ∩ S t ) be the set of attributes in which t is similar to t i ∈ D. Let D i ⊆ D be the set of tuples that are similar to t in all attributes involved in S i . The similarity score of t to t i , denoted as score(t, t i ), is defined as The most similar tuple t max to t is defined as

score(t, t i ) =        1 -log|D i | log|D| if |D i | 0 0 if |D i | = 0 Algorithm 5
t max = arg max t i ∈D (score(t, t i )).
CB Algorithm Algorithm 5 shows the pseudo code of the CB similarity function. It takes as input tuple t and a set of tuples D. It uses a function for measuring the similarity of two attribute values of the same domain. For every tuple in the database, say t i , steps 3-13 compute its similarity score. Step 3 computes the subset S i of attributes in which t and t i are similar. Steps 4-8 either compute or use the already computed set D i of tuples that are similar to t in all attributes of S i . The algorithm uses a hash table for managing the key-value pairs S i , |D i | . Steps 9-13 compute the similarity score based on the size of the set D i .

Notice that for each subset S i of attributes, we compute the set of tuples that are similar in the attributes of S i , only once. For instance in Figure 4(c), once we compute the set of tuples that are similar to tuple t in attribute set {age-range}, we use it for computing both score(t, t 1 ) and score(t, t 10 ). This greatly reduces the execution cost of the algorithm.

Cost analysis Let us analyze the execution time of Algorithm 5. In this algorithm, the first step is to compute for every attribute a i of t, a set A i including the tuples of D that are similar to t in a i . Let the execution time of matching two attribute values be g(w) where w is the maximum size of the values, and k be the number of attributes that are common in the schemas of t and D. Thus, this step takes θ(n × g(w)) time for every attribute and θ(k × n × g(w)) time for all k attributes, where n is the number of tuples involved in the database D. In the next step, for every tuple t i ∈ D, we need to obtain the intersection of all A j sets that have t i as member, say set S i . Obtaining the intersection of S i members takes O((

|S i | -1) × (n -1)) time, which is equal to O(k × n) since |S i | is bounded to k.
We have at most 2 k different S i sets and n tuples in D. Thus, executing this step for all tuples in the worst case takes min

(2 k , n) × O(k × n) time. Therefore, the algorithm takes min(2 k , n) × O(k × n) + θ(k × n × g(w)) time.
Usually the maximum attribute value size w can be considered as a constant and 2 k < n, i.e. k < log n, thus the worst case execution time of the algorithm can be written as O(n 2 × log n). However, our experiments show that different S i sets that occur in practice are far less than n. Thus, the average execution time of the algorithm is much better than its worst case performance.

PERFORMANCE EVALUATION

In this section, we study the effectiveness of our algorithms through experimentation over synthetic and real datasets. The rest of this section is organized as follows. We first describe our experimental setup. Then, we study the performance of the MPM and MC algorithms. Afterwards, we compare the performance of our similarity function with competing approaches. Finally, we summarize the performance results.

Experimental setup

We implemented our CB similarity function, CFA, CFA-MPME, CFA-MPMP, and MC algorithms in Java. We also implemented the MapReduce version of the MC algorithm in Java using Hadoop framework. We compare CB with Jaccard, Levenshtein (also known as edit-distance), SoftTFIDF [START_REF] Bilenko | Adaptive name matching in information integration[END_REF] and a version of SoftTFIDF introduced in [START_REF] Koudas | Flexible string matching against large databases in practice[END_REF], which we denote as Flexi-SoftTFIDF. We used the SecondString Java package1 for implementing these similarity functions. The SoftTFIDF and Flexi-SoftTFIDF functions use a similarity function for finding similar tokens inside attributes. Also, CB uses a similarity function for finding similar attributes. For this purpose, we used Jaro-Winkler similarity function [START_REF] Winkler | An Application Of The Fellegi-Sunter Model Of Record Linkage To The[END_REF] for all of these methods and we used the same similarity threshold for all of them. To the best of our knowledge, there is no other approach for computing most-probable matches other than expanding the possible worlds, i.e. the naïve approach. As a result, we consider the naïve approach as the only competitor to our approach.

The datasets that we use for our experiments are listed in Table 1. The Cora, Restaurant, and Census datasets have been frequently used in the literature to evaluate similarity functions, e.g. [32-34, 30, 35, 36]. The duplicate tuples of these datasets have been labeled. The Cora dataset includes bibliographical information about scientific papers in 12 different attributes from which we only use author, title, and venue attributes. The Restaurant dataset includes the name, address, city, and the type attributes of some restaurants. The Census dataset is a synthetic census-like data from which we only use the textual attributes, i.e. first name, middle initial, last name, street, city, and state. In order to be able to control characteristics of the dataset, we use the Synthetic dataset which we generate ourselves.

We use a number of wordlists 2 for the attribute values of the Synthetic database. To generate the database, we use one wordlist, say wordlist W, for each attribute and distribute the words in that wordlist over that attribute using a Gaussian distribution with a mean of |W| /2 and a deviation of |W| /6, where |W| is the size of the wordlist W. To evaluate the performance of CFA, CFA-MPME, CFA-MPMP, and MC algorithms, we use a probabilistic version of the Synthetic database. To control the characteristic of the database, we introduce d x , called the x-degree, as the maximum number of alternatives in an x-tuple, n as the number of tuples in the database, and k as the number of attributes in the database. To generate the database, we first generate the non-probabilistic Synthetic database as we explained above, then we add an attribute named probability to the database and convert the generated database into a probabilistic database as follows. We generate d as a uniform random number in [1, d x ], and repeatedly pick d tuples at random and group them into an x-tuple. The alternative tuples of the generated x-tuple are supposed to represent the same entity. To emulate this scenario, we randomly choose one of the x-tuple's alternatives as the seed tuple, say t, and for each of the other d -1 alternatives, say t , we do the following: we randomly choose k × 0.8 attributes of t and change their values with corresponding attribute values of t. For the probability attribute of the xtuple's alternatives, we use a discrete Gaussian distribution3 with a mean of 0 and a deviation of 0.2. We repeat the process of generating x-tuples until we group all tuples in valid x-tuples. We use the default value d x = 10. We generate the uncertain entity needed for experiments, in the same way that we generate a valid x-tuple and always with 3 alternatives.

As a context-free similarity function, we use the Jaro-Winkler similarity function [START_REF] Winkler | An Application Of The Fellegi-Sunter Model Of Record Linkage To The[END_REF] to evaluate the CFA algorithms. When comparing the MC algorithm with the naïve approach, we use CB similarity function in the naïve approach. Moreover, to study the performance of different context-sensitive similarity functions in the MC algorithm, we use SoftTFIDF, Flexi-SoftTFIDF, and CB similarity functions.

Method and performance metrics. To evaluate the performance of the similarity functions, we tested them over both synthetic (i.e. Census) and real datasets (i.e. Cora and Restaurant), thus covering all practical cases. We use success-rate for comparing the efficiency of different similarity functions. Our method for measuring the success-rate is described as follows. We repeatedly pick a tuple t from dataset D. If t has at least one duplicate tuple in D, except itself, we remove t from D and give the task of finding the most similar tuple in the dataset to t, to the similarity function. If the similarity function returns the duplicate tuple of t, we denote the search as a successful search. We repeat this process for all of the tuples of the dataset. The fraction of times the search is successful denoted as successrate of the similarity function for dataset D.

We also perform a self-join on the test datasets to measure the performance of different similarity functions. The self-join operation over the dataset D returns all tuple pairs in D, say (t, t ), t t , whose similarity is more than a certain specified threshold θ. To summarize the test results, we use the maximum F1 score. The F1 score for a threshold is defined as

F1 = 2 × precision × recall precision + recall
where precision is the percentage of returned tuple pairs that are duplicates, and recall is the percentage of duplicate tuple pairs that are returned by the self-join operation. The maximum F1 score is simply the maximum value of F1 that is obtained for different threshold values. To evaluate the scalability of different similarity functions, we measure their response time, which is the time to find the most similar tuple to a given tuple. Some approaches such as SoftTFIDF and Flexi-SoftTFIDF need a time to setup the process. We denote this time as the setup time of these functions.

To evaluate the performance of the CFA and MC algorithms, we measure their response time and compare it with the naïve approach. Moreover, to compare the performance of the CFA algorithm with its two imrpoved vesrsions (i.e. CFA-MPME and CFA-MPME), we measure the numebr of tuple pairs which are visited by these algorithms. significant for the context-sensitive similarity functions (i.e. SoftTFIDF and SoftTFIDF) over all datasets. This is one of the reasons that SoftTFIDF and Flexi-SoftTFIDF perform inefficiently in the MC algorithm.

We also conducted experiments to study how the response time of different similarity functions evolves with increasing n and also k (i.e. the number of attributes). Figure 11 shows the response time of a search over Synthetic dataset with increasing n up to 500,000 and k set to 10. This figure shows that CB not only outperforms the other similarity functions but also scales far better than them with the number of tuples in the dataset. Figure 12 shows the response time of a search over Synthetic dataset with increasing k up to 1,500 and n set to 3000. This figure shows that except Jaccard, CB outperforms all other similarity functions. We also observe that CB scales very well with the number of attributes. Notice that in these figures, the response times of SoftTFIDF and Flexi-SoftTFIDF are so close that cannot be differentiated from each other.

These results reveal another reason for outperformance of CB over other similarity functions in the MC algorithm. There are two main reasons for the good response time of CB compared to the other methods. The first reason is that CB uses an efficient string similarity function (i.e. Jaro-Winkler in our experiments) for computing the similarity between individual attributes. The second reason is that while all other methods compute the score of tuples one by one, CB reuses the computed score of a tuple for other tuples that are in the same situation (i.e. are similar in the same subset of attributes). This greatly improves the response time.

Related work

In the literature, considerable attention has been devoted to the problem of identifying different representations of the same real world entity over certain data (refer to [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF] for a survey). The problem has been presented under various terms such as entity resolution, identity resolution, duplicate detection, etc. Recently, there have been some proposals dealing with entity resolution over probabilistic data [START_REF] Menestrina | Generic entity resolution with data confidences[END_REF][START_REF] Panse | Duplicate detection in probabilistic data[END_REF]. The proposals in [START_REF] Menestrina | Generic entity resolution with data confidences[END_REF][START_REF] Panse | Duplicate detection in probabilistic data[END_REF] consider the duplicate detection of an uncertain relation and hence generate a clustering of the relation's tuples. In these proposals, one of the main problems is the merging of the tuples that fall in the same cluster. In contrast, we consider an entity resolution scenario where the aim is to resolve a given uncertain entity against an uncertain database, by considering both similarity and probability of database tuples and the given entity, and using the possible worlds semantics.

Among the prior work in database literature, nearest neighbor query processing, and top-k query processing over uncertain data are relevant to ours.

While there are a number of proposals, e.g. [START_REF] Kriegel | Probabilistic nearest-neighbor query on uncertain objects[END_REF][START_REF] Trajcevski | Continuous probabilistic nearest-neighbor queries for uncertain trajectories[END_REF][START_REF] Yuen | Superseding nearest neighbor search on uncertain spatial databases[END_REF], that deal with nearest neighbor queries over uncertain data, to the best of our knowledge, all of them model uncertain data by means of probability density functions (pdfs), which thus make their problem very different than ours.

There also have been some proposals dealing with uncertain top-k query processing (e.g., [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Soliman | Top-k query processing in uncertain databases[END_REF][START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF][START_REF] Re | Efficient top-k query evaluation on probabilistic data[END_REF]). The work in [START_REF] Soliman | Top-k query processing in uncertain databases[END_REF] extends the semantics of top-k queries from certain to uncertain databases and enumerate the possible worlds space of the uncertain database to compute the query results. We inspired by the semantics defined in [START_REF] Soliman | Top-k query processing in uncertain databases[END_REF] for defining the new semantics of entity resolution over probabilistic data. The proposal in [START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF] avoids enumerating the possible worlds space by using a dynamic programming approach for efficiently processing top-k queries on uncertain databases. Overall the top-k proposals rely on a ranking function, which assigns a fixed unique rank to every uncertain tuple in the query result, but our problem setting is different in both context-free and context-sensitive similarity cases. In the case of context-free similarity function, we are faced with multiple alternatives of the given uncertain entity, which results in multiple similarity scores between the uncertain entity and a tuple in the database. In the case of using a context-sensitive similarity function, we are not only faced with multiple similarity scores, but also the rank of a tuple may change in different possible worlds.

There is an extensive literature related to similarity functions that compare individual attributes stored as strings (refer to [START_REF] Bilenko | Adaptive name matching in information integration[END_REF] and [START_REF] Cohen | A comparison of string distance metrics for name-matching tasks[END_REF] for surveys). There also are a number of proposals for comparing tuples (refer to [START_REF] Dorneles | Approximate data instance matching: a survey[END_REF] for a recent survey). They mainly rely on two main approaches for comparing tuples. The first approach is to treat a tuple as a long field and apply one of the string similarity functions. This approach can be applied to all of the string similarity functions (e.g., TFIDF, SoftTFIDF, and Monge-Elkan). The second approach is to compute the similarity values between individual attributes of the two tuples and combine these values to obtain a whole similarity value. In [START_REF] Dey | Entity matching in heterogeneous databases: a distance-based decision model[END_REF], the weighted similarity is computed by assigning static weights to attributes based on their importance. The proposed technique in [START_REF] Koudas | Flexible string matching against large databases in practice[END_REF] modifies the normalization step of the well-known TFIDF similarity function to dynamically adjust the attributes' weights based on their relative importance. [START_REF] Guha | Merging the results of approximate match operations[END_REF] creates a similarity function based on ranked list merging. The basic idea is that if we compare only one attribute from the tuple, the matching algorithm can easily find the best matches and rank them according to their similarity, putting the best matches first [START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. Our similarity function differs from these proposals since ours is built on the novel concept of communities, which neither explicitly nor implicitly has been considered by prior proposals. An important advantage of our similarity function is that it does not need any extra pass over the database for setup. This makes our similarity function more suitable for the ERPD problem.

Conclusion

In this paper, we considered the problem of Entity Resolution for Probabilistic Data (ERPD), which is crucial for many applications that process probabilistic data. We adapted the possible worlds semantics of probabilistic data to define the novel concepts of most-probable match pair and most-probable match entity as the outcomes of ERPD. Then, we proposed MPM, a PTIME algorithm, which is applicable to the context-free similarity functions. The MPM algorithm is not applicable for context-sensitive similarity functions. Thus, we used Monte Carlo algorithm for approximating the outcome of ERPD. Existing context-sensitive similarity functions need a setup time for passing over the database to compute some statistical features of data. This shortcoming makes these functions inefficient for our proposed Monte Carlo algorithm. Thus, with the aim of having a context-sensitive similarity function with no setup time, we proposed the CB similarity function. We validated CB over both synthetic and real datasets. Our experiments show that CB significantly outperforms other similarity functions in terms of response time and success rate, and in using it in our proposed Monte Carlo algorithm. To further improve the efficiency our proposed Monte Carlo algorithm, we proposed a parallel version of it using the MapReduce framework. Our experiments show that the parallel version of Monte Carlo outperforms the single-machine Monte Carlo algorithm.

Fig. 1 .

 1 Fig. 1. a) Example of an entity in the x-tuple model, b) Example of x-relation Suspects, c) the possible worlds of Suspects

Fig. 2 .

 2 Fig. 2. a) Tuple pairs ranked based on their similarity; b) possible worlds space of e and S uspects, MSP in each world; c) all pairs and their probability to be MSP (P MSP ); d) entities and their P MSP

P

  msp (ρ) = w∈PW(e,D)∧ρ=MSP(w) P(w) Then, we define the most probable match pair of e and D, MPMP(e, D), as: MPMP(e, D) = arg max ρ∈e×D P MSP (ρ) and the most-probable match entity of e and D, MPME(e, D), as: MPME(e, D) = arg max

  e i ∈D ρ=(t,t )∈e×D,t ∈e i P MSP (ρ)

  Step 4 takes O(n) time for computing the similarity scores and O(n × log n) for sorting the scores. An efficient implementation of steps 6-8 takes O(i + N) time, where N is the number of x-tuples in D. Thus, steps 5-8 take n i=1 O(i + N) time, which is O(n 2 ) since N < n. Therefore, steps 4-8 are done in O(n 2 ). Since these steps are repeated m times (i.e. the number of alternatives of e), steps 3-8 take O(m × n 2 ) time. Step 9 takes O(m × n) time, which is dominated by O(m × n 2 ). Thus, the execution cost of the algorithm is O(m × n 2 ).

Fig. 4 .

 4 Fig. 4. a) An example tuple t, b) An example relation D for representing students, c) the similarity of D tuples to t

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Response times of Naïve and CFA algorithms

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Response time of different similarity functions vs. number of tuples

  We deal with the problem of significant setup time in existing context-sensitive functions, which makes them very inefficient for the Monte Carlo algorithm. We propose a new efficient context-sensitive similarity function that is very appropriate for the Monte Carlo algorithm.-We propose a parallel version of our Monte Carlo algorithm using the MapReduce framework.

e. context-free functions. For the rest of similarity functions (i.e. context-sensitive), we propose a Monte Carlo approximation algorithm. -

  Algorithm 1 Computing most-probable matches for the case of context-free similarity function

	Input:
		-Uncertain database D
		-Uncertain entity e
		-Context-free similarity function Sim
	Output: Most-probable matches
	1: define list L
	2: define set R and R ← ∅
	3: for all t ∈ e do
	4:	sort D tuples based on Sim(t, t i ), t i ∈ D, in descending order and store the result in list L
	5:

  An example of uncertain entity e, database D, and the improvement method

			entity tuple P	t P MSP (t e,1 , t) Potential(t e,1 , t)
			e 1	t 1,1 0.9	t 2,2	0.08	0.72
	entity tuple P	e 2	t 2,1 0.5 t 2,2 0.1	t 4,1 t 1,1	0.504 -	0.216 -
	e	t e,1 0.8 t e,2 0.1	e 3	t 3,1 0.6 t 3,2 0.3	t 3,2 t 3,3	--	--
		(a) e		t 3,3 0.1	t 2,1	-	-
			e 4	t 4,1 0.7 t 4,2 0.2	t 4,2 t 3,1	--	--
				(b) D		(c) List L
	Fig. 3.

, . . . , L[i]}.

  e, D , where e is an uncertain entity, and D is an uncertain database -context-sensitive similarity function Sim 1: generate an alternative t of e at random 2: generate a possible world W of D at random 3: t max ← arg max t ∈W Sim(t, t )

	4: key ← (t, t max )
	5: value ← 1
	6: Emit key, value
	Algorithm 3 Reduce function
	Input:
	-key (t, t ), where t ∈ e, t ∈ D
	-value set V

1: key ← (t, t ) 2: value ← |V| 3: Emit key, value Algorithm 4 Finalize Input: set S of key-value pairs (t, t ), v Output: most-probable matches 1: M ← (t,t ),v ∈S v 2: for all pair (t, t ), v ∈ S do 3: P (t,t ) ← v/M 4: end for 5: compute most-probable matches using P

  Computing similarity scores based on the CB similarity function Input: -tuple t -database D = {t 1 , . . . , t n } Output: array Score[n], where Score[i] represents the similarity between t and t i 1: define hash table H and H ← ∅ 2: for all t i ∈ D do 3: compute S i ⊆ S D as the set of attributes in which t i is similar to t // let D i ⊆ D be the set of tuples that are similar to t in all attributes involved in S i 4: if H contains key S i then 5: retrieve |D i | as the value for key S i from hash table H 6: else 7: compute D i and store key-value pair S i , |D i | in hash table H

	8:	end if
	9: 10:	if |D i | 0 then Score[i] ← 1 -log|D i | log|D|
	11:	else
	12:	Score[i] ← 0
	13:	end if
	14: end for

Table 1 .

 1 Datasets used in experiments. Source is the place where the dataset was originally introduced in, and k the number of used attributes, n the number of tuples of the dataset

	Name Source	k	n
	Cora	[32]	3	1,295
	Restaurant [33]	4	864
	Census	[34]	6	3,000
	Synthetic	-	10..1, 500 10..2, 000, 000

http://secondstring.sourceforge.net

ftp://ftp.ox.ac.uk/pub/wordlists

Indeed, we use a continues Guassian distribution with a mean of 0 and a deviation 0.2, say P(x), then we divide the range [-0.6..0.6] into d equal ranges, say r 1 , . . . , r d , and for each range r i compute the value of P(x) ∈ r i .

http://www.sara.nl/project/hadoop

We conducted our single-machine experiments on a Windows 7 machine with Intel Xeon 3.3 GHz CPU and 32 GB memory. For the MapReduce implementation, we used the Sara Hadoop cluster 4 which consists of 20 machines each with Dual core 2.6 GHz CPU and 16 GB memory.

Results

Performance of CFA and MC algorithms In this section, we study the performance of CFA, CFA-MPME, CFA-MPMP, and MC algorithms. We use the synthetic database as our test database. In our experiments, we set the δ parameter of the MC algorithm to 0.1 (see Section 4).

With n increasing up to 2,000,000, Figure 5 compares the response time of the naïve approach with that of CFA and its two improved versions. This figure shows that the response time of the naïve approach increases exponentially with n but that of CFA increases very smoothly. The performance gain of CFA-MPME and CFA-MPMP over CFA is not significant because the time needed for sorting the tuple pairs dominated the time needed for visiting the pairs. In order to compare the performance gain of CFA-MPME and CFA-MPMP over CFA, Figure 6 shows the number of visited tuple pairs in these algorithms. We observe that while CFA-MPMP significantly outperforms CFA, its number of visited tuple pairs is almost constant and independent from n. Moreover, although the performance gain of CFA-MPME is far less than that of CFA-MPMP, it is still noticeable.

We conducted experiments to study the effectiveness of different context-sensitive similarity functions in the MC algorithm. Figure 7 shows the response times of the naïve approach and two implementations of the MC algorithm, i.e. on a single machine and on the MapReduce framework, using different similarity functions. Overall, both on a single machine and using the MapReduce framework, CB significantly outperforms SoftTFIDF and Flexi-SoftTFIDF. The response times of SoftTFIDF and Flexi-SoftTFIDF increases dramatically with increasing n, while that of CB smoothly. Figure 7 also shows that the MapReduce implementation always outperforms the single-machine implementation in SoftTFIDF and Flexi-SoftTFIDF. However, in CB, the MapReduce implementation outperforms the single-machine implementation for n > 6, 000. This is because the overhead of the MapReduce framework is more than its gain for small values of n. Notice that the response times of SoftTFIDF and Flexi-SoftTFIDF are so close that cannot be differentiated in the figure .   Performance of CB In this section, we compare the performance of the CB similarity function with other competing similarity functions.

Figures 8 and9 respectively compare the success-rate and maximum F1 of CB, SoftTFIDF, Flexi-SoftTFIDF, Jaccard, and Levenshtein similarity functions over the Cora, Restaurant, and Census datasets. We observe that CB always performs a little less than the best similarity function and never is the worst similarity function.

Census


Vinícius P Freire

José A F De Macêdo
email: jose.macedo@lia.ufc.br

Fábio Porto
email: fporto@lncc.br

Reza Akbarinia
email: reza.akbarinia@inria.fr

NACluster: A Non-Supervised Clustering Algorithm for Matching Multi Catalogues

Astronomy surveys use powerful instruments to browse the sky and identify objects of interest within the surveyed region. Sky objects are individually characterized with spatial coordinates, identifying their position in the sky, in addition to other descriptive attributes. Composing an integrated view of the sky based on catalogues produced by different surveys faces a hard problem of matching objects that have been captured in various catalogues. Due to variations on capturing instruments calibration, the sky position of a single sky object may vary from a catalog to the other. Moreover, in particular dense regions of the sky this problem is exacerbated by a huge number of candidate matches for each given object. Traditional approaches for dealing with this problem use a threshold distance of to reduce the number of matching candidates. Additionally, they adopt a pairwise approach for matching n catalogues inferring transitivity among matches, which not always hold. In this paper, we present NACluster a non-supervised clustering algorithm for dealing with sky object matching in multiple catalogues. NACluster matching strategy extends the traditional k-means clustering algorithm by relaxing the number k of cluster (i.e. matched sky objects). We experiment NACluster with real and synthetic catalogues and show that the results present better accuracy than state of the art solutions.

I. INTRODUCTION

In astronomy context, catalog is a dataset that contains a list of celestial objects and their characteristics, like position, magnitude and color. There are different astronomical surveys, or catalogues. They are characterized by having different formats, schemes, data structures, since they are handled by distinct and independent projects. Each one covers a specific area of the sky or even the whole area of the Universe. Then, the surveys produce catalogues with intersections in the covered area of the sky. So, It's possible to have objects in common in different catalogues. Therefore, if we want to have an integrated view provided by different catalogues, it's necessary to do the data cross-matching.

Current astronomy surveys present important challenges in the cross-matching area, where the spatial position of objects is very important. The matching tries to identify sky objects registered in different catalogues with slightly different properties but representing the same real object, once there slightly difference in the object position captured by two different telescopes. It can produce ambiguity in the matching. The cross-matching among catalogues is usually applied in peer-to-peer fashion, between two different catalogues, and generates a single output catalog identifying common objects between surveys. The algorithm selects matches considering the shortest distance between objects using a spatial radius defined by the user. However, when we want to compute a matching among three or more catalogues, a more careful process must be applied, as one shall not consider matching transitively and the ordering with which catalogues are chosen may produce different results.

Match transitivity problem occurs, for example, when given three objects

O 1 , O 2 and O 3 from different catalogues, the O 2 match with O 1 and O 3 , but O 1 does not match with O 3 . Thus, O 1 = O 2 , O 2 = O 3 , but O 1 = O 3 . In this situation, we would expect that O 1 = O 2 = O 3 .
Few works in the literature tackled cross-matching in astronomical research domain. Particularly, in [START_REF] Freire | Proceedings of the XXXIII Congress of the Brazilian Computer Society (CSBC 2013)[END_REF] some crossmatching algorithms for astronomic catalogues were evaluated. In this work, Q3C Join algorithm [START_REF] Koposov | Q3C , Quad Tree Cube -The new Skyindexing Concept for Huge Astronomical Catalogues and its Realization for Main Astronomical Queries ( Cone Search and Xmatch ) in Open Source Database PostgreSQL[END_REF] was chosen to be evaluated. However, Q3C generated some incorrect matching in the order of billions of false positives when using big catalogues. This problem is due to matching strategy of Q3C, which is ambiguity preserving. In fact, an ambiguity resolution solution is required in this context, which motivated this work.

In this paper, we propose the NACluster, a non-supervised clustering algorithm for matching multi catalogues. The aim of this algorithm is to split into clusters the celestial objects present in n catalogues, such that in each cluster there are only objects from different catalogues and representing the same real object. This contribution allows the improvement on state of the art astronomy catalog matching.

The rest of the paper is organized as follows. In Section 2, we propose the NACluster algorithm. In Section 3, we present the experiments using this algorithm and its validation, as well as a comparison with the Q3C Join algorithm [START_REF] Koposov | Q3C , Quad Tree Cube -The new Skyindexing Concept for Huge Astronomical Catalogues and its Realization for Main Astronomical Queries ( Cone Search and Xmatch ) in Open Source Database PostgreSQL[END_REF]. Finally, section 4 concludes and presents the future works.

II. NACLUSTER: A NON-SUPERVISED CLUSTERING ALGORITHM

The NACluster algorithm is short for the N-way Astronomical Clustering algorithm, a non-supervised clustering algorithm for matching multi catalogues. The algorithm takes as input n catalogues and produces a clustering composed of k clusters. In defining the matching criteria among objects, an important restriction is that all objects falling in a cluster shall originally come from different catalogues. Furthermore, each cluster is supposed to represent a real object in the observed sky. Thus, one doesn't know in advance how many objects will be produced by the merged catalogues. This restrictions refrain us from adopting a traditional clustering algorithm, such as kmeans.

The pseudocode of the NACluster algorithm is described in Algorithm 1.

The algorithm receives as input a set of catalogues. Each catalog is a set of tuples of form (id, ra, dec), where id is the object identification, ra and dec represents the spatial coordinates of this object. In line 3 of Algorithm 1, the largest catalog is selected and one cluster is created for each its object. In this step, the location of each object is taken as a cluster centroid.

The idea of the algorithm is to compare each object of one catalog to all computed cluster centroids, by computing the distance

d(O i , C a ) of an object O i to a centroid C a . When d(O i , C a ) < , then the object O i is mapped to cluster C a .
This mapping, however, can only be applied when there not exists another object O j in cluster C a that has been mapped to the same catalog of O i . In case an object of C a already exists in the cluster, two scenarios must be evaluated:

(1) if d(O j , C a ) > d(O i , C a )
then we should remove the object O j from the cluster C a , insert O i in this cluster, and search another cluster for

O j ; (2) if d(O j , C a ) < d(O i , C a )
then the algorithm performs a recursive search on the candidate list (candidates), using the procedure searchCentroid (detailed in Algorithm 2), for allocating O i .In case, no cluster is found at distance then a new cluster C b is created to the point O i and it will be the centroid.

Once all objects from the merged catalogues have been evaluated, a new iteration is performed searching for better cluster centroids. The algorithm finishes when the centroids are stable, i.e. all the computed centroids of an iteration are the same as the previous iteration.

III. EXPERIMENTS

In order to evaluate the NACluster algorithm we selected a dense part of 2MASS [START_REF] Skrutskie | The Two Micron All Sky Survey (2MASS)[END_REF] catalog (90 thousand objects relatively close together) and we applied a normal distribution function for generating new catalogues from 2MASS, simulating in this manner real variations of the same catalog. We have synthesized 5 different datasets containg from 2 to 6 catalogues using this approach.

We evaluate the NACluster by assessing the "quality" of the clustered objects produced by the algorithm. In particular, we use precision, recall, and F-measure having as baseline objects generated from the real objects. Our goal is to evaluate the performance of the NACluster in identifying this set of matched objects. We remind the reader that precision is the fraction of the set of objects retrieved that are relevant; recall is the fraction of relevant objects that were retrieved; F-measure is the harmonic mean between precision and recall [START_REF] Manning | Introduction to Information Retrieval[END_REF]. Another similar experiment was done using the UBVRI catalog [START_REF] Henden | UBVRI measurements of stars by Arne Henden (USNO)[END_REF], which is a sparse catalog containing 49,167 objects. In this case precision, recall and f-measure is around 0.99 (refer to Table II), keeping the same accuracy even when the number of merged catalogues are increased.

We can conclude from the previous results that our algorithm has a good accuracy rate, and this rate varies according to the catalog density. In all case, our algorithm converged within two iterations.

A. Comparison with Q3C Join

The Q3C Join [START_REF] Koposov | Q3C[END_REF], as most cross-matching algorithms, performs the matching of only two catalogues at a time, producing, as output, a catalog containing the matched objects. We compare the output of the Q3C Join algorithm execution with the output of the clustering algorithm NACluster taking as input the same two catalogues, both performing the matching between part of the 2MASS catalog (1 million objects) and the synthetic catalog generated from it (1 million objects). The NACluster algorithm produced as output 1,001,005 clusters, 980,282 of which were correct and 20,723 were wrong, with a hit rate around 98% and 2% error. The Figure 1 shows the region of the sky covered by the catalogues used in the comparison. The x axis is the Right Ascension coordinate, or Ra, and the y axis is the Declination, or Dec. Each light green point is a correctly classified object, i.e. its cluster was formed with its original pair. It is important to mention that the correctly classified points were plotted before the wrongly classified points,as due to the low resolution of the plot, the points take up more space than their actual size. Thus, we can have a better view of the comparison. Fig. 2. The colored area represents the region of space occupied by the objects present in part of the 2MASS catalog used in experiments with the Q3C Join (radius 0.001 degree was used as parameter). Each light green point is an object classified correctly, i.e., it formed cluster with its real pair. Each black point is an object wrongly classified, i.e. it didn't form cluster with its real pair.

The Q3C Join presented an output dependent on the size of the radius used. Figures 2 and3 illustrate the case, they follow the same caption of Figure 1. Figure 2 shows the result of the matching using a radius 0.001 degree. This radius allowed to retrieve 964,432 correct matches, but also retrieved 48,624 wrong matches. One can see that the black area of Figure 2 is much larger than in Figure 1.

We changed the radius to 0.002 degree in order to achieve all synthetic objects and understand the behavior of Q3C Join. The result is shown in Figure 3, in which the black area occupies the large area of the graphic, because the output of Q3C Join using the radius 0.002 degree returned 339,536 wrong matches, ie, 33.95% of matches, apart from the 1 million correct matches, ie all the real matches.

Table III presents the precision, recall and F-measure for these same experiments. Values in bold correspond to the highest precision, recall and F-measure. Note that the scenario using NACluster outperforms all other scenarios in precision and F-measure. When the radius in Q3C Join is 0.002 degree, its recall (1.0) is higher than the recall (0.9875) shown in the proposed approach, but its precision (0.7456) is considerably worse, leading to a relatively low F-measure (0.8549). Fig. 3. The colored area represents the region of space occupied by the objects present in part of the 2MASS catalog used in experiments with the Q3C Join (radius 0.002 degree was used as parameter). Each light green point is an object classified correctly, i.e., it formed cluster with your real pair. Each black object is an object classified wrongly, i.e. it not formed cluster with your real pair. Finally, Figure 4 shows a direct comparison of the Fmeasure for these scenarios. According that, NACluster algorithm has performance superior than the Q3C Join, even increasing its radius.

The result of this comparison leads us to conclude that, unlike the strategy of the NACluster algorithm to solve the matching ambiguity, the Q3C Join has a strategy to preserve the ambiguity, accepting duplicity at matches. This duplicity was also identified in the experiments presented in a previous paper [START_REF] Freire | Proceedings of the XXXIII Congress of the Brazilian Computer Society (CSBC 2013)[END_REF].

IV. CONCLUSION AND FUTURE WORKS

In this paper, we presented the NACluster algorithm, a nonsupervised clustering for matching multiple catalogues.

In order to evaluate the effectiveness of this algorithm, we used real astronomical catalogues, which were useful to generate new catalogues with perturbations on objects locations by using a normal distribution. These preliminary results indicate that the algorithm is effective in matching objects from different catalogues. Thus, this contribution allows improving the state of the art astronomy catalog matching.

The algorithm presents exponential complexity on the number of individual sky elements (i.e. clusters). By using a spatial indexing strategy, the actual number of comparison is reduced to a local region, making the algorithm in practice feasible and presenting a huge potential for parallelization.

In future work, we are planning to develop a parallel strategy for NACluster algorithm, and to evaluate other similarity functions. We intend to use this approach as the first step on entity resolution problems for very large catalogues.

Fig. 1 .

 1 Fig. 1. The colored area represents the region of space occupied by the objects present in part of the 2MASS catalog used in experiments with the NACluster algorithm. Each light green point represents an object correctly classified, i.e., it formed cluster with its real pair. Each black point is an object wrongly classified, i.e. it didn't form cluster with its real pair.

Fig. 4 .

 4 Fig. 4. Comparison among NACluster and Q3C Join

Table I

 I presents the precision, recall and f-measure of the results generated by NACluster. An interesting observation concerning this table is that f-measure remains around 0.97, even the number of merged catalogues in the dataset is increased. The recursive procedure to search the appropriate cluster cluster with centroid centroid to the object obj from the catalog obj.cat in the centroids candidates list candidates

	Algorithm 2 4: create cluster; 5: cluster.add(obj); 6: computeCentroid(cluster); 7: else 8: minDistance ← Double.M AX V ALU E; 9: for all centroid ∈ candidates do 10: distance ← candidates.getDistance(centroid); 11: if distance < minDistance then 12: minCentroid ← centroid 13: minDistance ← distance 14: end if 15: end for 16: if o / ∈ c[minCentroid] | o.cat=obj.cat then 17: c[minCentroid].add(obj); c is a clusters list 18: computeCentroid(c[minCentroid]); 19: else 20: oldObj ← o; 21:	Algorithm 1 The NACluster algorithm 1: Input: Dataset containing a set of catalogues 2: procedure CLUSTERING(Dataset) 3: initializeClusters(largestCatalog); 4: visitedCatalogs.add(largestCatalog); 5: while not centroids stable do 6: if iterationN umber > 1 then 7: Clear the clusters, but keep their centroids; 8: end if 9: for all cat ∈ Dataset & cat / ∈ visitedCatalogs do 10: visitedCatalogues.add(cat); 11: for all obj ∈ cat do 12: minDistace ← Double.M AX V ALU E; 13: existCentroid ← f alse; 14: for all centroid ∈ centroids do 15: distance ← computeDistance(obj,centroid); 16: if distance < then 17: existCentroid ← true; 18: candidates.add(centroid,distance); 19: if minDistance ≥ distance then 20: minCentroid ← centroid; 21: minDistance ← distance; 22: end if 23: end if
			24:	end for
			25:	if existCentroid then
			26:	if o / ∈ c[minCentroid] | o.cat=obj.cat then
			27:	c[minCentroid].add(obj);	c is a clusters list
			28:	computeCentroid(c[minCentroid]);
			29:	else
			30:	searchCentroid(obj,candidates);
			31:	candidates.clear();
			32:	end if
			33:	else
	33: 34: 35: 36: 37: 38: 39: 40: 41:	end if end if end for searchCentroide(oldObj,candidates); else candidates.remove(minCentroid); searchCentroid(obj,candidates) end if end if	34: 35: 36: 37: 38: 39: 40: 41: end procedure end if create cluster; cluster.add(obj); computeCentroid(cluster); end for end for end while 42: Output: All clusters and their objects and centroid;
	42:	end if
	43: end procedure
			TABLE I.	THE EFFECT ON THE PRECISION AND RECALL OF THE
			NACLUSTER ALGORITHM USING THE 2MASS CATALOG MATCHED
			AGAINST 1 TO 5 SYNTHETIC VERSIONS GENERATED FROM IT BY APPLYING
				A NORMAL DISTRIBUTION FUNCTION.
			No. of catalogues Precision Recall F-Measure
			2	0.9750	0.9763	0.9757
			3	0.9717	0.9727	0.9722
			4	0.9654	0.9671	0.9662
			5	0.9699	0.9713	0.9706
			6	0.9734	0.9745	0.9739
			TABLE II.	THE EFFECT ON THE PRECISION AND RECALL OF
			NACLUSTER ALGORITHM WHEN MATCHING, IN A SPARSE REGION OF THE
			SKY, THE UBVRI CATALOG AGAINST 1 TO 5 SYNTHETIC GENERATED
				VERSIONS OF IT.
			No. of catalogues Precision Recall F-Measure
			2	0.9937	0.9938	0.9938
			3	0.9944	0.9944	0.9941
			4	0.9954	0.9960	0.9957
			5	0.9932	0.9932	0.9926
			6	0.9913	0.9914	0.9906

1: Parameters: the object and the candidates list 2: procedure SEARCHCENTROIDE(obj,candidates) 3: if candidates.size = 0 then oldDistance ←computeDistance(oldObj,centroid); 22: if minDistance < oldDistance then 23: c[minCentroid].remove(oldObj); 24: c[minCentroid].add(obj); 25: computeCentroid(c[minCentroid]); 26: candidates.clear(); 27: minDistance ← Double.M AX V ALU E; 28:

for all centroid ∈ centroids do 29:

distance ← computeDistance(OldObj,centroid) 30:

if distance < then 31:

if centroid = minCentroid then 32:

candidates.add(centroid,distance);

TABLE III .

 III COMPARATIVE RESULTS, IN TERMS OF PRECISION AND RECALL, CONFRONTING MATCHING STRATEGIES BASED ON Q3C AND NACLUSTER, USING THE 2MASS AND A SYNTHETIC GENERATED CATALOG DERIVED FROM IT.

	Algorithm	Precision Recall F-measure
	NACluster	0.9834	0.9875	0.9857
	Q3C (0.001 degree)	0.9520	0.9644	0.9582
	Q3C (0.002 degree)	0.7456	1.0	0.8549

http://www.linea.gov.br

V. ACKNOWLEDGEMENTS

The authors would like to show their gratitude to the Interinstitutional e-Laboratory for Astronomy (LIneA 1 ) for having first presented the problem to us and provided the datasets and infra-structure for running the experiments. This work has been partially supported by the FAPERJ-INRIA MUSIC project E-26/110.074/2014.