Entity Resolution (ER) is the process of identifying references referring to the same entity from one or more data sources. In the ER process, most existing approaches exploit the content information of references, categorized as content-based ER, or additionally consider linkage information among references, categorized as context-based ER. However, in new applications of ER, such as in the genealogical domain, the very limited linkage information among references results in a disjoint graph in which the existing content-/context-based ER techniques have very limited applicability. Therefore, in this paper we propose first, to use the homophily principle for augmentation of the original input graph by connecting the potential similar references, and second, to use a Random Walk based approach to consider contextual information available for each reference in the augmented graph. We evaluate the proposed method by applying it to a large genealogical dataset and we succeed to predict 420,000 reference matches with precision 92% and discover six novel and informative patterns among them which can not be detected in the original disjoint graph.
NewcombeH.B., KennedyJ.M., AxfordS.J. and JamesA.P., Automatic linkage of vital records, Science130 (1959), 954-959.
2.
FellegiI.P. and SunterA.B., A theory for record linkage, Journal of the American Statistical Association64 (1969), 1183-1210.
3.
WinklerW., The state of record linkage and current research problems, 1999, URL: http://www.census.gov/srd/papers/ pdf/rr99-04.pdf.
4.
BhattacharyaI. and GetoorL., Iterative record linkage for cleaning and integration, in: Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, DMKD '04, ACM, New York, NY, USA, (2004), 11-18. URL: http://doi.acm.org/10.1145/1008694.1008697. doi: 10.1145/1008694.1008697.
5.
RavikumarP. and CohenW.W., A hierarchical graphical model for record linkage, in: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, AUAI Press, Arlington, Virginia, United States, (2004), 454-461. http: //dlacm.org/citation.cfm?id=1036843.1036898.
6.
WinklerW.E., Methods for record linkage and bayesian networks, Technical Report, Statistical Research Division, U.S. Census Bureau, 1994.
7.
HernándezM.A. and StolfoS.J., The merge/purge problem for large databases, SIGMOD Rec24 (1995), 127-138.
8.
MongeA.E. and ElkanC., An efficient domain-independent algorithm for detecting approximately duplicate database records, in: DMKD, (1997). URL: http://dblp.uni-trier.de/db/conf/dmkd/dmkd97.html#MongeE97.
9.
SarawagiS. and BhamidipatyA., Interactive deduplication using active learning, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, ACM, New York, NY, USA, (2002), 269-278. URL: http://doi.acm.org/10.1145/775047.775087. doi: 10.1145/775047.775087.
10.
AnanthakrishnaR., ChaudhuriS. and GantiV., Eliminating fuzzy duplicates in data warehouses, in: Proceedings of the 28th International Conference on Very Large Data Bases, VLDB '02, VLDB Endowment, (2002), 586-597. URL: http:// dlacm.org/citation.cfm?id=1287369.1287420.
11.
CohenW.W., KautzH.A. and McAllesterD.A., Hardening soft information sources, in: KDD, R. Ramakrishnan, S.J. Stolfo, R.J. Bayardo and I. Parsa, eds, ACM, (2000), 255-259. URL: http://dblp.uni-trier.de/db/conf/kdd/kdd2000.html# CohenKM00.
12.
McCallumA., NigamK. and UngarL.H., Efficient clustering of high-dimensional data sets with application to reference matching, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, (2000), 169-178.
13.
SinglaP. and DomingosP., Entity resolution with markov logic, in: In ICDM, IEEE Computer Society Press, (2006), 572-582.
14.
BenjellounO., Garcia-MolinaH., MenestrinaD., SuQ., WhangS.E. and WidomJ., Swoosh: A generic approach to entity resolution, VLDB J18 (2009), 255-276.
15.
GetoorL. and MachanavajjhalaA., Entity resolution for big data, in: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, (2013), 1527-1527.
16.
EfremovaJ., Ranjbar-SahraeiB., OliehoekF.A., CaldersT. and TuylsK., A baseline method for genealogical entity resolution, in: Workshop on Population Reconstruction, (2014).
17.
BhattacharyaI. and GetoorL., Entity resolutions in graphs, in: Mining Graph Data, D. Cook and L. Holder, eds, Wiley, 2006.
18.
KolbL. and RahmE., Parallel entity resolution with dedoop, Datenbank-Spektrum13 (2013), 23-32.
19.
WhangS.E., MenestrinaD., KoutrikaG., TheobaldM. and Garcia-molinaH., Entity resolution with iterative blocking, Technical Report, 2008.
20.
WhangS. and Garcia-MolinaH., Entity resolution with evolving rules, PVLDB3 (2010), 1326-1337.
21.
WinklerW.E., String comparator metrics and enhanced decision rules in the fellegi-sunter model of record linkage, 1990.
22.
NavarroG., A guided tour to approximate string matching, ACM Computing Surveys (CSUR)33 (2001), 31-88.
23.
EfremovaJ., Ranjbar-SahraeiB. and CaldersT., A hybrid disambiguation measure for inaccurate cultural heritage data, in: The 8th Workshop on Language Technology for Cultural Heritage, Social Sciences, and Humanities, (2014).
24.
BogdanovP. and SinghA.K., Function prediction using neighborhood patterns, in: BioKDD Workshop, (2008).
25.
HeJ., LiM., ZhangH.-J., TongH. and ZhangC., Manifold-ranking based image retrieval, in: Proceedings of the 12th Annual ACM International Conference on Multimedia, MULTIMEDIA '04, ACM, New York, NY, USA, (2004), 9-16. URL: http://doi.acm.org/10.1145/1027527.1027531. doi: 10.1145/1027527.1027531.
26.
JehG. and WidomJ., Simrank: A measure of structural-context similarity, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, ACM, New York, NY, USA, (2002), 538-543. URL: http://doi.acm.org/10.1145/775047.775126. doi: 10.1145/775047.775126.
27.
PageL., BrinS., MotwaniR. and WinogradT., The pagerank citation ranking: Bringing order to the web, in: Proceedings of the 7th International World Wide Web Conference, Brisbane, Australia, (1998), 161-172. URL: citeseer.nj.nec.com/ page98pagerankhtml.
28.
MongeA.E. and ElkanC., An efficient domain-independent algorithm for detecting approximately duplicate database records, in: DMKD, (1997).
29.
WinklerW.E., Matching and record linkage, Business Survey Methods1 (1995), 355-384.
30.
MongeA. and ElkanC., The field matching problem: Algorithms and applications, in: In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, (1996), 267-270.
31.
NavarroG., A guided tour to approximate string matching, ACM Comput Surv33 (2001), 31-88.
32.
CohenW.W., RavikumarP. and FienbergS.E., in: Proceedings of IJCAI-03 Workshop on Information Integration.
33.
ChaudhuriS., GanjamK., GantiV. and MotwaniR., Robust and efficient fuzzy match for online data cleaning, in: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, SIGMOD '03, ACM, New York, NY, USA, (2003), 313-324. URL: http://doi.acm.org/10.1145/872757.872796. doi: 10.1145/872757.872796.
34.
RistadE.S., YianilosP.N. and MemberS., Learning string edit distance, IEEE Transactions on Pattern Analysis and Machine Intelligence20 (1998), 522-532.
35.
BilenkoM. and MooneyR.J., Adaptive duplicate detection using learnable string similarity measures, in: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, ACM, New York, NY, USA, (2003), 39-48. URL: http://doi.acm.org/10.1145/956750.956759. doi: 10.1145/956750.956759.
36.
CohenW.W. and RichmanJ., Learning to match and cluster large high-dimensional data sets for data integration, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, ACM, New York, NY, USA, (2002), 475-480. URL: http://doi.acm.org/10.1145/775047.775116. doi: 10.1145/775047. 775116.
37.
TejadaS., KnoblockC.A. and MintonS., Learning object identification rules for information integration, Information Systems26 (2001), 2001.
38.
SarawagiS. and BhamidipatyA., Interactive deduplication using active learning, in: The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2002), (2002), 269-278.
39.
KoudasN., MaratheA. and SrivastavaD., Flexible string matching against large databases in practice, in: Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30, VLDB '04, VLDB Endowment, (2004), 1078-1086. URL: http://dlacm.org/citation.cfm?id=1316689.1316782.
40.
YanceyW.E. and YanceyW.E., Evaluating string comparator performance for record linkage, Technical Report, Bureau of the Census, 2005.
41.
BilenkoM., MooneyR., CohenW., RavikumarP. and FienbergS., Adaptive name matching in information integration, IEEE Intelligent Systems18 (2003), 16-23.
42.
SinglaP. and DomingosP., Multi-relational record linkage, in: KDD-2004 Workshop on Multi-Relational Data Mining, (2004), 31-48.
43.
DongX., HalevyA. and MadhavanJ., Reference reconciliation in complex information spaces, in: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD '05, ACM, New York, NY, USA, (2005), 85-96. URL: http://doi.acm.org/10.1145/1066157.1066168. doi: 10.1145/1066157.1066168.
44.
KalashnikovD.V. and MehrotraS., Domain-independent data cleaning via analysis of entity-relationship graph, ACM Trans Database Syst31 (2006), 716-767.
45.
DoanA., LuY., LeeY. and HanJ., Object matching for information integration: A profiler-based approach, in: Proceedings of the IJCAI-2003 Workshop on Information Integration on the Web, Acapulco, Mexico, (2003), 53-58.
46.
NevilleJ., AdlerM. and JensenD., Clustering relational data using attribute and link information, in: In Proceedings of the Text Mining and Link Analysis Workshop, 18th International Joint Conference on Artificial Intelligence, (2003), 9-15.
47.
CoddE.F., The Relational Model for Database Management: Version 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1990.
48.
ElmasriR.A. and NavatheS.B., Fundamentals of Database Systems, 3rd edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
49.
McPhersonM., Smith-LovinL. and CookJ.M., Birds of a feather: Homophily in social networks, Annual Review of Sociology27 (2001), 415-444.
50.
McCallumA., NigamK. and UngarL.H., Efficient clustering of high-dimensional data sets with application to reference matching, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '00, ACM, New York, NY, USA, (2000), 169-178. URL: http://doi.acm.org/10.1145/347090.347123. doi: 10.1145/347090.347123.
51.
BaxterR., ChristenP. and ChurchesT., A comparison of fast blocking methods for record linkage, in: ACM SIGKDD '03 Workshop on Data Cleaning, Record Linkage, and Object Consolidation, (2003), 25-27.
52.
BilenkoM., KamathB. and MooneyR.J., Adaptive blocking: Learning to scale up record linkage, in: ICDM, IEEE Computer Society, (2006), 87-96. URL: http://dblp.uni-trier.de/db/conf/icdm/icdm2006.html#BilenkoKM06.
53.
EvangelistaL.O., CortezE., da SilvaA.S. and MeiraW., Jr, Adaptive and flexible blocking for record linkage tasks, JIDM1 (2010), 167-182.
54.
KnuthD., The art of computer programming 1: Fundamental algorithms 2: Seminumerical algorithms 3: Sorting and searching, 1968.
55.
PhilipsL., Hanging on the metaphone, Computer Language7 (1990).
RahmaniH., Ranjbar-SahraeiB., WeissG. and TuylsK., Contextual entity resolution approach for genealogical data, in: Workshop on Knowledge Discovery, Data Mining and Machine Learning, (2014).
58.
InstituteM., Meertens institute databases, 2014. URL: http://www.meertens.knaw.nl/cms/en/collections/databases.
59.
CanT., ÇamoğluO. and SinghA.K., Analysis of protein-protein interaction networks using random walks, in: Proceedings of the 5th International Workshop on Bioinformatics, ACM, (2005), 61-68.
60.
BhattacharyaI. and GetoorL., Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery From Data (TKDD)1 (2007), 5.
61.
MooreD.S., McCabeG.P. and CraigB.A., Introduction to the Practice of Statistics: Extended, FreemanW.H., New York, 2009. URL: http://opac.inria.fr/record=b1131072.
62.
KrejcieR.V. and MorganD.W., Determining sample size for research activities, Educational and Psychological Measurement30 (1970), 607-610.
63.
EfremovaJ., Ranjbar-SahraeiB., OliehoekF.A., CaldersT. and TuylsK., An interactive, web-based tool for genealogical entity resolution, in: 25th Benelux Conference on Artificial Intelligence, (2013), 376-377.
64.
KoenraadV., MyriamC. and JanD., A short manual to the art of prosopography, in: Prosopography Approaches and Applications A Handbook, K.-R. K.S.B., ed., Unit for Prosopographical Research (Linacre College), Oxford, (2007), 35-69.
65.
ElloumiM. and ZomayaA.Y., Biological Knowledge Discovery Handbook: Preprocessing, Mining and Postprocessing of Biological Data, 1st edition, Wiley Publishing, 2013.
66.
StelzlU., WormU., LalowskiM., HaenigC., BrembeckF.H., GoehlerH., StroedickeM., ZenknerM., SchoenherrA., KoeppenS., TimmJ., MintzlaffS., AbrahamC., BockN., KietzmannS., GoeddeA., ToksözE., DroegeA., KrobitschS., KornB., BirchmeierW., LehrachH. and WankerE.E., A human protein-protein interaction network: A resource for annotating the proteome, Cell122 (2005), 957-968.
67.
MilenkoviT. and PruljN., Uncovering biological network function via graphlet degree signatures, Cancer Informatics6 (2008), 257-273.
68.
DezsoZ., NikolskyY., NikolskayaT., MillerJ., CherbaD., WebbC. and BugrimA., Identifying disease-specific genes based on their topological significance in protein networks, BMC Systems Biology3 (2009), 36+.
69.
RuffnerH., BauerA. and BouwmeesterT., Human protein-protein interaction networks and the value for drug discovery, Drug Discovery Today12 (2007), 709-716.
