More Web Proxy on the site http://driver.im/

research-article

A Distance-Based Approach to Entity Reconciliation in Heterogeneous Databases

Authors:

P. DeAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 14, Issue 3

Pages 567 - 582

https://doi.org/10.1109/TKDE.2002.1000343

Published: 01 May 2002 Publication History

Abstract

In modern organizations, decision makers must often be able to quickly access information from diverse sources in order to make timely decisions. A critical problem facing many such organizations is the inability to easily reconcile the information contained in heterogeneous data sources. To overcome this limitation, an organization must resolve several types of heterogeneity problems that may exist across different sources. In this paper, we examine one such problem called the entity heterogeneity problem, which arises when the same real-world entity type is represented using different identifiers in different applications. A decision-theoretic model to resolve the problem is proposed. Our model uses a distance measure to express the similarity between two entity instances. We have implemented the model and tested it on real-world data. The results indicate that the model performs quite well in terms of its ability to predict whether two entity instances should be matched or not. The model is shown to be computationally efficient. It also scales well to large relations from the perspective of the accuracy of prediction. Overall, the test results imply that this is certainly a viable approach in practical situations.

References

[1]

M.R. Anderberg, Cluster Analysis for Applications. New York: Academic Press, 1973.

[2]

F.H. Barron and B.E. Barrett, “Decision Quality Using Ranked Attribute Weights,” Management Science, vol. 42, no. 11, pp. 1515-1523, Nov. 1996.

Digital Library

[3]

C. Batini and M. Lenzerini, “A Methodology for Data Schema Integration in the Entity Relationship Model,” IEEE Trans. Software Eng., vol. 10, no. 6, pp. 650-664, Nov. 1984.

Digital Library

[4]

C. Batini M. Lenzerini and S.B. Navathe, “A Comparative Analysis of Methodologies for Database Schema Integration,” ACM Computing Surveys, vol. 18, no. 4, pp. 323-364, Dec. 1986.

Digital Library

[5]

J. Bischoff and T. Alexander, Data Warehouse: Practical Advice from the Experts. Prentice-Hall, 1997.

Digital Library

[6]

M.W. Bright A.R. Hurson and S. Pakzad, “Automated Resolution of Semantic Heterogeneity in Multidatabases,” ACM Trans. Database Systems, vol. 19, no. 2, pp. 212-253, June 1994.

Digital Library

[7]

J.R. Canada and W.G. Sullivan, Economic and Multiattribute Evaluation of Advanced Manufacturing Systems. Englewood Cliffs, N.J.: Prentice-Hall, 1989.

[8]

A. Chatterjee and A. Segev, “Rule Based Joins in Heterogeneous Databases,” Decision Support Systems, vol. 13, no. 1, pp. 313-333, 1995.

Digital Library

[9]

A.L.P. Chen P.S.M. Tsai and J.-L. Koh, “Identifying Object Isomerism in Multidatabase Systems,” Distributed and Parallel Databases, vol. 4, no. 2, pp. 143-168, Apr. 1996.

Digital Library

[10]

W.W. Cohen, “Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity,” Proc. 1998 ACM SIGMOD Conf., pp. 201-212, June 1998.

Digital Library

[11]

J.B. Copas and F.J. Hilton, “Record Linkage: Statistical Models for Matching Computer Records,” J. Royal Statistical Soc., vol. 153, no. 3, pp. 287-320, 1990.

[12]

D. Dey S. Sarkar and P. De, “A Probabilistic Decision Model for Entity Matching in Heterogeneous Databases,” Management Science, vol. 44, no. 10, pp. 1379-1395, 1998.

Digital Library

[13]

R.T. Eckenrode, “Weighting Multiple Criteria,” Management Science, vol. 12, no. 3, pp. 180-192, Nov. 1965.

Digital Library

[14]

I.P. Fellegi and A.B. Sunter, “A Theory of Record Linkage,” Am. Statistical Assoc. J., vol. 64, pp. 1183-1210, Dec. 1969.

[15]

P. Fankhauser and E.J. Neuhold, “Knowledge Based Integration of Heterogeneous Databases,” Interoperable Database Systems (DS-5), D.K. Hsiao, E.J. Neuhold, and R. Sacks-Davis eds. pp. 155-175, North-Holland, 1993.

Digital Library

[16]

S. Gass, “A Process to Determine Priorities and Weights for Large-Scale Linear Goal Programming,” Proc. 12th Int'l Symp. Math. Programming, Aug. 1985.

[17]

W. Gotthard P.C. Lockemann and A. Neufeld, “System-Guided View Integration for Object-Oriented Databases,” IEEE Trans. Knowledge and Data Eng., vol. 4, no. 1, pp. 1-22, Feb. 1992.

Digital Library

[18]

J.A. Hartigan, Clustering Algorithms. John Wiley, 1975.

Digital Library

[19]

M.A. Hernández and S.J. Stolfo, “The Merge/Purge Problem for Large Databases,” Proc. 1995 ACM SIGMOD Conf., pp. 127-138, May 1995.

Digital Library

[20]

R.A. Johnson and W.W. Wichern, Applied Multivariate Statistical Analysis. Englewood Cliffs, N. J.: Prentice-Hall, 1989.

Digital Library

[21]

W. Kent R. Ahmed M. Ketabchi and M.-C. Shan, “Object Identification in Multidatabase Systems,” Interoperable Database Systems (DS-5), D.K. Hsiao, E.J. Neuhold, and R. Sacks-Davis eds., pp. 313-330, 1993.

Digital Library

[22]

W. Kim I. Choi S. Gala and M. Scheevel, “On Resolving Semantic Heterogeneity in Multidatabase Systems,” Distributed and Parallel Databases, vol. 1, no. 3, pp. 251-279, July 1993.

Digital Library

[23]

W. Kim and J. Seo, “Classifying Schematic and Data Heterogeneity in Multidatabase Systems,” IEEE Computer, vol. 24, no. 12, pp. 12-18, Dec. 1991.

Digital Library

[24]

D.E. Knuth J.H. Morris and V.R. Pratt, “Fast Pattern Matching in Strings,” SIAM J. Computing, vol. 6, no. 2, pp. 323-350, June 1977.

Digital Library

[25]

I. Kononenko and I. Bratco, “Information-Based Evaluation Criterion for Classifier's Performance,” Machine Learning, vol. 6, pp. 67-80, 1991.

Digital Library

[26]

H.W. Kuhn, “The Hungarian Method for the Assignment Algorithm,” Naval Research Logistics Quarterly, vol. 1, nos. 1/2, pp. 83-97, Mar./June 1955.

[27]

J.A. Larson S.B. Navathe and R. Elmasri, “A Theory of Attribute Equivalence in Databases with Application to Schema Integration,” IEEE Trans. Software Eng, vol. 15, no. 4, pp. 449-463, Apr. 1989.

Digital Library

[28]

E. Lawler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1976.

[29]

W.-S. Li and C. Clifton, “Semantic Integration in Heterogeneous Databases Using Neural Networks,” Proc. 20th Int'l Conf. Very Large Data Bases, pp. 1-12, Sept. 1994.

Digital Library

[30]

A.E. Monge and C.P. Elkan, “The Field Matching Problem: Algorithm and Applications,” Proc. Second Int'l Conf. Knowledge Discovery and Data Mining, pp. 267-270, Aug. 1996.

[31]

S.B. Navathe and S.G. Gadgil, “A Methodology for View Integration in Logical Database Design,” Proc. Eighth Int'l Conf. Very Large Data Bases, pp. 142-164, Sept. 1982.

Digital Library

[32]

H.B. Newcombe J.M. Kennedy S.J. Axford and A.P. James, “Automatic Linkage of Vital Records,” Science, vol. 130, no. 3381, pp. 954-959, Oct. 1959.

[33]

C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982.

Digital Library

[34]

V. Poe, Building a Data Warehouse for Decision Support. Upper Saddle River, N.J.: Prentice-Hall 1996.

Digital Library

[35]

M. Rusinkiewicz A. Sheth and G. Karabatis, “Specifying Interdatabase Dependencies in a Multidatabase Environment,” IEEE Computer, vol. 24, no. 12, pp. 46-53, Dec. 1991.

Digital Library

[36]

T.L. Saaty, The Analytic Hierarchy Process. New York: McGraw-Hill, 1980.

[37]

A.P. Sheth and J.A. Larson, “Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases,” ACM Computing Surveys, vol. 22, no. 3, pp. 183-236, Sept. 1990.

Digital Library

[38]

E. Stickel A. Hunstock A. Ortmann and J. Ortmann, “Data Sharing Economics and Requirements for Integration Tool Design,” Information Sciences, vol. 19, no. 8, pp. 629-642, Aug. 1994.

Digital Library

[39]

A. Tversky and D. Kahnemann, “Judgment under Uncertainty: Heuristics and Biases,” Science, vol. 185, pp. 1124-1131, 1974.

[40]

V. Ventrone and S. Heiler, “Semantic Heterogeneity as a Result of Domain Evolution,” ACM SIGMOD Record, vol. 20, no. 4, pp. 16-20, Dec. 1991.

Digital Library

[41]

Y.R. Wang and S. Madnick, “The Interdatabase Instance Identification Problem in Integrating Autonomous Systems,” Proc. Fifth Int'l Conf. Data Eng., pp. 46-55, Feb. 1989.

Digital Library

Cited By

Tonci NRivault SBamha MRobert SLimet STorquati M(2024)LSH SimilarityJoin Pattern in FastFlowInternational Journal of Parallel Programming10.1007/s10766-024-00772-152:3(207-230)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10766-024-00772-1
Kathuria MNagpal CDuhan N(2022)A Hybrid Approach to Discover Entity SynonymsInternational Journal of Information Retrieval Research10.4018/IJIRR.30029612:3(1-18)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.4018/IJIRR.300296
Rivault SBamha MLimet SRobert S(2022)Towards a Scalable Set Similarity Join Using MapReduce and LSHComputational Science – ICCS 202210.1007/978-3-031-08751-6_41(569-583)Online publication date: 21-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-08751-6_41
Show More Cited By

Index Terms

A Distance-Based Approach to Entity Reconciliation in Heterogeneous Databases

Recommendations

Entity matching across heterogeneous data sources: An approach based on constrained cascade generalization

To integrate or link the data stored in heterogeneous data sources, a critical problem is entity matching, i.e., matching records representing semantically corresponding entities in the real world, across the sources. While decision tree techniques have ...
Entity reconciliation in big data sources

Systematic Mapping Study about entity reconciliation in Big Data.Eleven databases were consulted. Rigorous process where 2255 papers were analyzed leaving 61 primary studies.Analytic data statistics after the classification of the primary ...
Towards privacy preserving data reconciliation for criminal justice chains
dg.o '09: Proceedings of the 10th Annual International Conference on Digital Government Research: Social Networks: Making Connections between Citizens, Data and Government

In many organizations different databases contain different kind of data concerning the same entity. This may have several good reasons. However, to have an integral and unified view of an entity, data reconciliation is of crucial importance. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 14, Issue 3

May 2002

206 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 2002 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2002

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tonci NRivault SBamha MRobert SLimet STorquati M(2024)LSH SimilarityJoin Pattern in FastFlowInternational Journal of Parallel Programming10.1007/s10766-024-00772-152:3(207-230)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10766-024-00772-1
Kathuria MNagpal CDuhan N(2022)A Hybrid Approach to Discover Entity SynonymsInternational Journal of Information Retrieval Research10.4018/IJIRR.30029612:3(1-18)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.4018/IJIRR.300296
Rivault SBamha MLimet SRobert S(2022)Towards a Scalable Set Similarity Join Using MapReduce and LSHComputational Science – ICCS 202210.1007/978-3-031-08751-6_41(569-583)Online publication date: 21-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-08751-6_41
Fier FAugsten NBouros PLeser UFreytag J(2018)Set similarity joins on mapreduceProceedings of the VLDB Endowment10.14778/3231751.323176011:10(1110-1122)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231760
B. KM.N. S(2015)Efficient identity matching using static pruning q-gram indexing approachDecision Support Systems10.1016/j.dss.2015.02.01573:C(97-108)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.dss.2015.02.015
Wandelt SDeng DGerdjikov SMishra SMitankin PPatil MSiragusa ETiskin AWang WWang JLeser U(2014)State-of-the-art in string similarity search and joinACM SIGMOD Record10.1145/2627692.262770643:1(64-76)Online publication date: 13-May-2014
https://dl.acm.org/doi/10.1145/2627692.2627706
Castano SFerrara AMontanelli SVarese G(2011)Ontology and instance matchingKnowledge-driven multimedia information extraction and ontology evolution10.5555/2001069.2001076(167-195)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2001069.2001076
Li JWang GChen H(2011)Identity matching using personal and social identity featuresInformation Systems Frontiers10.1007/s10796-010-9270-013:1(101-113)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1007/s10796-010-9270-0
Choenni Svan Dijk JLeeuw F(2010)Preserving privacy whilst integrating data: Applied to criminal justiceInformation Polity10.5555/1858974.185898315:1,2(125-138)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1858974.1858983
Magnani MMontesi D(2010)A Survey on Uncertainty Management in Data IntegrationJournal of Data and Information Quality10.1145/1805286.18052912:1(1-33)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1145/1805286.1805291
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents