Data Quality Web Services are services that enhance the quality of data in the sense of making it t for use. This paper concentrates on duplicate detection, which identi es multiple representations of real-world objects within large datasets where these representations are similar to a certain degree. Measures to estimate this similarity are one of the major research e orts in the community since many years. However for Web Services, these heuristics di er in the amount of underlaying meta information, which is usually much poorer. The type of missing meta data is analyzed and classi ed in this paper. It also examines on di erent ways of making the duplicate-containing data available to the Data Quality Web Service.
Due to the aforementioned di culties and costs, measures ensuring data quality are often omitted. This can also be formulated as a need for ad-hoc, fair-priced, simple, lowcon guration data cleansing. The Software as a Service paradigm promises to be a valid solution for this need since it employs services (most frequently in the shape of Web Services) as basic building blocks.
Detection of duplicates is the process of identifying
multiple representations of same real world objects. Traditional
duplicate detection (also called deduplication or record
linkage) employs well-established algorithms and heuristics, see
Elmagarmid [
Typically, those algorithms concentrate on (a) the selection of duplication candidates and/or on (b) a measure to estimate the similarity between two items. For (a) the goal is to nd an elaborate selection of candidate pairs to avoid comparison of all (O(n2)) pairs of elements, where the overwhelming number of comparisons will not be promising. For (b) the goal is to compare elements e ciently, i.e., with a good estimation of the actual similarity or in short time. 2.1 Web Services for Duplicate Detection The comparison of two elements bases on data type and value of their attributes and additional information to identify these pairs as possible duplicates. However, sometimes the amount of available information is restricted or { as in Web Services { just not available: the schema might not be up-to-date, the eld-mapping is unclear, privacy issues prevent full access to all the data, etc.
Thus, the question is how a good similarity measure can be created under the described conditions while still achieving appropriate results and while remaining as general as possible. Therefore, it has to be examined which information is essential for a duplicate detection process and which information therefore has to be inferred from the data or retrieved from other sources.
Web Service implementations of data cleansing { resp. duplication detection { methods (Data Quality Web Services) are invoked on-demand with exactly the information that is to be decided about, e.g., in case of only a small number of items that shall be tested for similarity in an ad-hoc manner. Further, they provide a clearly speci ed functionality while remaining as general as possible to ensure a broad number of possible service requesters. These properties turn Web Services into the ideal foundation for evaluating duplicate detection algorithms with the limitations described above.
Without the assumption of a Web Service to deduplicate
only a small number of elements, further problems arise.
The issue of how the data have to be made accessible to
the services is covered by Faruquie et al. [
Successful duplicate detection within unforeseeable data and structure requires some e orts before the actual detection of duplicates can take place. Di erent pieces of information may be missing, i.e., \semantics" of data, attribute names of data, mapping between elds, and attribute separators. All those terms are explained in the following. The lack of information can be seen as di erent levels of challenges for a good similarity measure. These levels are presented in the following. 3.1 Challenges for Similarity Measure Selection Level 0 This represents the \traditional" scenario for similarity measures as depicted in Table 1. The record's attributes have proper names, the mapping is reliable (the last name of the rst record has to be compared to the last name of the second record), and, of course, separators are available (represented by the table grid). Finally, the \semantics" are also clear due to the fact that the database managers are at hand and can provide this kind of information.
Therefore, speci c measures such as a ne-grained heuristic for birthdates would detect that 1955|10|05 and 10.05.1955 mean the same date. Furthermore, it might be clear that the person's title is often guessed or omitted and thus, Mr. and an empty entry would match. The only requirement here is that these specialized similarity measures are available.
Level 1 If the data are provided without expert knowledge, e.g. in the XML-like shape illustrated in Figure 2, specialized similarity measures cannot be applied directly. First, attributes have to be classi ed. The result of this classi cation is some degree of certainty that a similarity measure is appropriate. To achieve this knowledge, the occurring values as well as the attribute names can <address record="1"> <title>Mr.</title> <firstname>Homer Jay</firstname> <lastname>Simpson</lastname> <birthday>1955|10|05</birthday> </address> <address record="2"> <title/> <firstname>H. J.</firstname> <lastname>Simpspn</lastname> <birthday>10.05.1955</birthday> </address> be used. A particular challenge is to nd out languagespeci c features, e.g., the order of month and day in a date eld. Therefore, correlating data such as the domain of names or location information, should be considered, too. Note that the kind of representations is independent from the lack of expert knowledge. Level 2 Di erent records might have a di erent schema or no schema at all, e.g., because they come from di erent data sources or di erent owners. Figure 3 illustrates two records, where the rst one is in XML format, the second one is in CSV format. It is obvious, that the schema is not clear. Not only are the entries in di erent order, also the occurrence of some attributes is di erent (e.g., the telephone number). Moreover, the granularity di ers. The rst record has separated title and name, the second one has separated family name from the rest.
It is commonly not clear, which attributes have to be compared with each other. The names of attributes might support the creation of a corresponding mapping, however those are not always available. Moreover, the telephone number of the second record might match the birthday of the rst entry better than both birthdays match one another. Using meta information, such as thesauri or ontologies, help resolve synonym relations between terms, e.g., \surname" and \family name".
Level 3 The elds of a record might not be clearly distinguishable (c.f. Figure 4). E.g., the separator is not known or the record is represented as un- or semistructured text. Therefore, the separator has to be found and entities have to be recognized, respectively. While the rst separator (;) is rather common, the second one (|) is less frequent and might normally not be automatically recognized as an attribute separator. 4. DEALING WITH LARGE AMOUNT OF
DATA As described as goal (a) earlier, checking for duplicates in a large set of data poses additional challenges, which are discussed here.
There are three principles of how data transfer between the customer's database and the processing unit (the Web Service) can be done. All have di erent requirements on network bandwidth, ease of use and requirements towards the customer's infrastructure.
Homer Jay;Simpson;742 Evergreen Terrace;Springfield Mr.|Homer Jay|Simpson|742 Evergreen Terrace|Springfield Bulk File Transfer The relevant records can be exported from the customer's database into a at le and then \charrsid87854 \par Homer Simpson}{\rtlch\fcs1 be transfered as-is to the Web Service. Technical re\af31507 \ltrch\fcs0 \lang1033\langfe1033 strictions such as the le being too large can be tack\langnp1033\insrsid6695672\charrsid87854 led by compressing the le or by splitting the le into \par }{\rtlch\fcs1 \af31507 \ltrch\fcs0 smaller parts. The overall network usage is minimized \lang1033\langfe1033\langnp1033\insrsid87854 here, rst if compression is used and second, because \charrsid87854 \par 742 Evergreen-Terrace \par } each record is only transferred once. Moreover, the {\rtlch\fcs1 \af31507 \ltrch\fcs0 \insrsid87854 transfer is rather atomic from the point of view of the Springfield \par USA \par \par }{\*\themedata 504b03 customer. There is no need to continuously being in charge of providing data. The third example in this gure shows an RTF snippet kwhere these terms occur, too.
The challenges presented in Section 3.1 can be arranged in a tree as pictured in Figure 5. Each black node represents the decision for the existence of a speci c piece of information, starting from the top (whether or not attribute separators are available) and reaching to the bottom (whether or not insights in the \semantics" of the attributes are present). If the corresponding information is available, the left subtree is investigated further, else the right one. Each pass leads to a leaf node that holds one of seven scenarios which have been elaborated on in the previous section. The best results for a similarity measure can be achieved if the left-most scenario is selected.
Read the tree in the following way: For example to infer a mapping between the attributes, the separators (resp. the entities and their attributes) have to be identi ed before. This is also the reason for the tree being very unbalanced. For example, it makes no sense to try to detect the data type if it is unclear, where one attribute ends and another one starts. However, there might be an overlap for this detection process. To nd a valid mapping it can be necessary to check the similarity of di erent candidate pairs on an attribute value level. Recall the example in Figure 4. When creating a mapping between the two record's attributes, different matching candidate pairs have to be examined, here <birthday>1955|10|05</birthday> with both, 10.05.1955 and (019) 55 10 05.
ODBC Access The Web Service could be provided with a possibility to directly access the customer's database. In this case, Web Service (SOAP) requests are only needed for the control connection, the actual data is transferred directly. However, this is only possible, if the customer is able and willing to provide a way to access the database. Most probably, the network topology ( rewalls, NAT) and security policies will complicate this access. The overhead is also higher in this approach, because the Web Service will either send many independent queries to the database or (most probably) will just issue a SELECT * FROM relevant_records query to retrieve the needed data. Then, the data transfer is not as condensed as the approach above. Web Service The third possibility for the customer is to provide a (Web Service) API to his database. This will on the one hand reduce network topology problems, but on the other hand drastically increase bandwidth usage and CPU load, since much SOAP en- and decoding is to be under way. Furthermore, the customer has to provide an environment where this API is embedded. However, if the total amount of data is fairly small, the API already exists and the duplicate detection shall be very autonomous, this might also render an appropriate approach.
If the data is on the Web Service's side once, processing can
begin. Assuming that the challenges described in Section 3
are successfully managed, duplicate detection can take place
as usual. However in this scenario, many customers are to be
served at the same time (with potentially also large amounts
of data). Therefore, parallelized algorithms for searching
for duplicates in relatively promising subsets of the whole
dataset are needed.
In principle, two basic algorithms are widely used, Sorted
Neighborhood and Blocking. In the Sorted Neighborhood
approach [
The di erent classes are already in focus of ongoing research,
separately. For example, duplicate detection in XML
structures [
Research in duplicate detection for unstructured or
semistructured texts is often applied in plagiarism detection
systems as MOSS (Schleimer et al. [
Faruquie et al. [
There are a number of providers and registries for Data Quality Web Services. They provide services for data alignment (e.g., format telephone numbers properly), data completion (e.g., add postcodes to cities), or data veri cation (e.g., check ISBNs against book titles). However, there are no Web Services for duplicate detection.
The process of Data Cleansing commonly comprises the normalization of data, the identi cation of duplicates within these data and the elimination of these duplicates by fusing or discarding duplicate elements. Employing services for this task is bene cial, because set-up and maintenance costs are low and they are only paid for on a by-use scheme. Duplicate detection commonly faces two challenges: having a good, e cient similarity measure and selecting the \right" records to compare. In a Web Service application, the similarity measure is especially hard, since one or more of different (meta) data can be missing: \semantics", datatypes, mappings, and eld separators. These information have to be inferred from the available data to decide for appropriate comparison operators.
Another challenge is the selection of promising duplicate candidates which becomes even more tricky when it comes to parallelization e orts. Depending on this is also the decision on the way of how to bring the customer's data to the service. Currently, there is no best practice commonly agreed upon.