{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T07:41:14Z","timestamp":1768722074106,"version":"3.49.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            Keys for graphs aim to uniquely identify entities represented by vertices in a graph. We propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. Extending conventional keys for relations and XML, these keys find applications in object identification, knowledge fusion and social network reconciliation. As an application, we study the entity matching problem that, given a graph\n            <jats:italic>G<\/jats:italic>\n            and a set \u03a3 of keys, is to find all pairs of entities (vertices) in\n            <jats:italic>G<\/jats:italic>\n            that are identified by keys in \u03a3. We show that the problem is intractable, and cannot be parallelized in logarithmic rounds. Nonetheless, we provide two parallel scalable algorithms for entity matching, in MapReduce and a vertex-centric asynchronous model. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824056","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1590-1601","source":"Crossref","is-referenced-by-count":58,"title":["Keys for graphs"],"prefix":"10.14778","volume":"8","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh and Beihang University"}]},{"given":"Zhe","family":"Fan","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}]},{"given":"Chao","family":"Tian","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Beihang University"}]},{"given":"Xin Luna","family":"Dong","sequence":"additional","affiliation":[{"name":"Google Inc."}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Dbpedia. http:\/\/wiki.dbpedia.org\/Downloads2014.  Dbpedia. http:\/\/wiki.dbpedia.org\/Downloads2014."},{"key":"e_1_2_1_2_1","unstructured":"Full version. http:\/\/homepages.inf.ed.ac.uk\/s1368930\/keys.pdf.  Full version. http:\/\/homepages.inf.ed.ac.uk\/s1368930\/keys.pdf."},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951367"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153752"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.43"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.96"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217304"},{"key":"e_1_2_1_9_1","volume-title":"PVLDB, 2010","author":"Bu Y.","year":"1920"},{"key":"e_1_2_1_10_1","volume-title":"WWW, 2001","author":"Buneman P.","year":"1920"},{"key":"e_1_2_1_11_1","volume-title":"A Rule-Based Citation System for Structured and Evolving Datasets","author":"Buneman P.","year":"2010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.127"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_14_1","volume-title":"SIGMOD","author":"Dong X.","year":"2005"},{"key":"e_1_2_1_15_1","volume-title":"PVLDB","author":"Dong X. L.","year":"2014"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623623"},{"key":"e_1_2_1_17_1","first-page":"0206","volume-title":"VLDBJ","author":"Fan W.","year":"2011"},{"key":"e_1_2_1_18_1","volume-title":"USEWOD workshop","author":"Gallego M. A.","year":"2011"},{"key":"e_1_2_1_19_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367564"},{"key":"e_1_2_1_21_1","volume-title":"IMC '12","author":"Gong N. Z.","year":"2012"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/IA3.2014.10"},{"key":"e_1_2_1_23_1","unstructured":"R. V. Guha. Communicating and resolving entity references. http:\/\/arxiv.org\/abs\/1406.6973.  R. V. Guha. Communicating and resolving entity references. http:\/\/arxiv.org\/abs\/1406.6973."},{"key":"e_1_2_1_24_1","first-page":"337","volume-title":"SIGMOD","author":"Han W.-S.","year":"2013"},{"key":"e_1_2_1_25_1","volume-title":"TKDE, 2012","author":"Herschel M.","year":"2011"},{"key":"e_1_2_1_26_1","first-page":"33","volume-title":"DBKDA","author":"Kim S.-H.","year":"2013"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367527"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732274"},{"key":"e_1_2_1_29_1","volume-title":"EMNLP","author":"Lao N.","year":"2011"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_32_1","volume-title":"EDBT\/ICDT Workshops","author":"Malhotra P.","year":"2014"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2013.07.001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807212"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621939"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938546"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"e_1_2_1_38_1","volume-title":"PVLDB, 2012","author":"Sun Z.","year":"1906"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:19Z","timestamp":1672222459000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":38,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824056"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824056","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}