Robust Identification of Fuzzy Duplicates
Published 19 April 2005
Surajit Chaudhuri, Venkatesh Ganti, R. Motwani
Citations172
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work proposes two novel criteria that enable characterization of fuzzy duplicates more accurately than is possible with existing techniques, and proposes a novel framework for the fuzzy duplicate elimination problem.
Abstract
Detecting and eliminating fuzzy duplicates is a critical data cleaning task that is required by many applications. Fuzzy duplicates are multiple seemingly distinct tuples, which represent the same real-world entity. We propose two novel criteria that enable characterization of fuzzy duplicates more accurately than is possible with existing techniques. Using these criteria, we propose a novel framework for the fuzzy duplicate elimination problem. We show that solutions within the new framework result in better accuracy than earlier approaches. We present an efficient algorithm for solving instantiations within the framework. We evaluate it on real datasets to demonstrate the accuracy and scalability of our algorithm.
Keywords
Computer ScienceDecision Sciences
A density-based algorithm for discovering clusters in large spatial Databases with Noise
19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.
Journal of Molecular BiologyIdentification of common molecular subsequences
10,081 Citations1981Temple F. Smith, Michael S. Waterman
This letter extends the heuristic homology algorithm of Needleman & Wunsch (1970) to find a pair of segments, one from each of two long sequences, such that there is no other Pair of segments with greater similarity (homology).
IEEE ExpertData mining and knowledge discovery: making sense out of data
4,643 Citations1996U.M. Feyyad
Find loads of the data mining and knowledge discovery making sense out of data book catalogues in this site as the choice of you visiting this page.
LOF
3,862 Citations2000Markus Breunig, Hans‐Peter Kriegel +2 more
This paper contends that for many scenarios, it is more meaningful to assign to each object a degree of being an outlier, called the local outlier factor (LOF), and gives a detailed formal analysis showing that LOF enjoys many desirable properties.
Journal of the American Statistical AssociationA Theory for Record Linkage
2,399 Citations1969Ivan P. Fellegi, A. B. Sunter
Qucosa (Saxon State and University Library Dresden)Data Cleaning: Problems and Current Approaches.
1,441 Citations2000Erhard Rahm, Hai Hong
This work classifies data quality problems that are addressed by data cleaning and provides an overview of the main solution approaches and discusses current tool support for data cleaning.
Adaptive duplicate detection using learnable string similarity measures
930 Citations2003Mikhail Bilenko, Raymond J. Mooney
This paper proposes to employ learnable text distance functions for each database field, and shows that such measures are capable of adapting to the specific notion of similarity that is appropriate for the field's domain.
Data Mining and Knowledge DiscoveryReal-world Data is Dirty: Data Cleansing and The Merge/Purge Problem
813 Citations1998Mauricio A. Hernández, Salvatore J. Stolfo
This paper develops a system for accomplishing this Data Cleansing task and demonstrates its use for cleansing lists of names of potential customers in a direct marketing-type application and reports on the successful implementation for a real-world database that conclusively validates results previously achieved for statistically generated data.
Interactive deduplication using active learning
693 Citations2002Sunita Sarawagi, Anuradha Bhamidipaty
This work presents the design of a learning-based deduplication system that uses a novel method of interactively discovering challenging training pairs using active learning and investigates various design issues that arise in building a system to provide interactive response, fast convergence, and interpretable output.
An Impossibility Theorem for Clustering
514 Citations2002Jon Kleinberg
A formal perspective on the difficulty in finding a unified framework for reasoning about clustering at a technical level is suggested, in the form of an impossibility theorem: for a set of three simple properties, it is shown that there is no clustering function satisfying all three.
Approximate String Joins in a Database (Almost) for Free
510 Citations2001Luis Gravano, Panagiotis G. Ipeirotis +4 more
This paper develops a technique for building approximate string join capabilities on top of commercial databases by exploiting facilities already available in them, and demonstrates experimentally the benefits of the technique over the direct use of UDFs.
The field matching problem: Algorithms and applications
482 Citations1996Alvaro Monge, Charles Elkan
Three field matching algorithms are described, one of which is the well-known Smith-Waterman algorithm for comparing DNA and protein sequences, and their performance on real-world datasets is evaluated.
Robust and efficient fuzzy match for online data cleaning
456 Citations2003Surajit Chaudhuri, Kris Ganjam +2 more
A new similarity function is proposed which overcomes limitations of commonly used similarity functions, and an efficient fuzzy match algorithm is developed which can effectively clean an incoming tuple if it fails to match exactly with any tuple in the reference relation.
Elsevier eBooksEliminating Fuzzy Duplicates in Data Warehouses
387 Citations2002R. Ananthakrishna, Surajit Chaudhuri +1 more
An algorithm for eliminating duplicates in dimensional tables in a data warehouse, which is usually associated with hierarchies is developed and evaluated on real datasets from an operational data warehouse.
Integration of heterogeneous databases without common domains using queries based on textual similarity
380 Citations1998William W. Cohen
This paper rejects the assumption that global domains can be easily constructed, and assumes instead that the names are given in natural language text, and proposes a logic called WHIRL which reasons explicitly about the similarity of local names, as measured using the vector-space model commonly adopted in statistical information retrieval.
An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records.
354 Citations1997Alvaro Monge, Charles Elkan
An eecient algorithm for recognizing clusters of approximately duplicate records that typically reduces by over 75% the number of times that the expensive pair-wise record matching (Smith-Waterman or other) is applied, without impairing accuracy.
Journal of the American Statistical AssociationA Theory for Record Linkage
349 Citations1969Ivan P. Fellegi, A. B. Sunter
Learning to match and cluster large high-dimensional data sets for data integration
345 Citations2002William W. Cohen, Jacob Richman
Techniques for clustering and matching identifier names that are both scalable and adaptive, in the sense that they can be trained to obtain better performance in a particular domain are described.
ANU Open Research (Australian National University)A Comparison of Fast Blocking Methods for Record Linkage
338 Citations2003Rohan A. Baxter, Peter Christen +1 more
This work compares two new blocking methods, bigram indexing and canopy clustering with TFIDF (Term Frequency/Inverse Document Frequency), with two older methods of standard traditional blocking and sorted neighbourhood blocking to show there is a potential for large performance speed-ups and better accuracy to be achieved by these newblocking methods.
The VLDB JournalSearching in metric spaces by spatial approximation
270 Citations2002Gonzalo Navarro
This work proposes a new data structure, called sa-tree (“spatial approximation tree”), which is based on approaching the searched objects spatially, that is, getting closer and closer to them, rather than the classic divide-and-conquer approach of other data structures.
Learning domain-independent string transformation weights for high accuracy object identification
255 Citations2002Sheila Tejada, Craig A. Knoblock +1 more
Extensions to the Active Atlas system are discussed, which allow it to learn to tailor the weights of a set of general transformations to a specific application domain through limited user input, and demonstrate that this approach achieves higher accuracy and requires less user involvement than previous methods.
Indexing methods for approximate string matching
190 Citations2001Gonzalo Navarro, Ricardo Baeza‐Yates +2 more
This work classifies most indexing methods in a taxonomy that helps understand their essential features and shows that the existing methods form a range of solutions whose optimum is usually somewhere in between.
ACM Transactions on Database SystemsDuplicate record elimination in large data files
180 Citations1983Dina Bitton, David J. DeWitt
The issue of duplicate elimination for large data files in which many occurrences of the same record may appear is addressed and a comprehensive cost analysis of the duplicate elimination operation is presented.
Learning to match and cluster large high-dimensional data sets for data integration
83 Citations2002William W. Cohen, Jacob Richman
Knowledge Discovery and Data MiningOn Evaluation and Training-Set Construction for Duplicate Detection
83 Citations2003Mikhail Bilenko and Raymond J. Mooney
A proposed two new approaches to collecting training data called static-active learning and weaklylabeled non-duplicates are proposed, and experimental results on their effectiveness are presented.
IEEE Transactions on Knowledge and Data EngineeringMultiple similarity queries: a basic DBMS operation for mining in metric databases
27 Citations2001Bernhard Braunmüller, Martin Ester +2 more
This work introduces a generic scheme for data mining algorithms and investigates two orthogonal approaches, reducing I/O cost as well as CPU cost, to speed-up the processing of multiple similarity queries in metric databases.
Symposium on Discrete AlgorithmsApproximate Nearest Neighbor under edit distance via product metrics
27 Citations2004Piotr Indyk
To the knowledge, this is the first data structure for this problem with both query time and storage subexponential in d and the space requirement of this data structure is roughlyO, i.e., strongly subexp exponential.