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

research-article

BLAST: a loosely schema-aware meta-blocking approach for entity resolution

Authors:

Giovanni Simonini,

Sonia Bergamaschi,

H. V. JagadishAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 9, Issue 12

Pages 1173 - 1184

https://doi.org/10.14778/2994509.2994533

Published: 01 August 2016 Publication History

Abstract

Identifying records that refer to the same entity is a fundamental step for data integration. Since it is prohibitively expensive to compare every pair of records, blocking techniques are typically employed to reduce the complexity of this task. These techniques partition records into blocks and limit the comparison to records co-occurring in a block. Generally, to deal with highly heterogeneous and noisy data (e.g. semi-structured data of the Web), these techniques rely on redundancy to reduce the chance of missing matches.

Meta-blocking is the task of restructuring blocks generated by redundancy-based blocking techniques, removing superfluous comparisons. Existing meta-blocking approaches rely exclusively on schema-agnostic features.

In this paper, we demonstrate how "loose" schema information (i.e., statistics collected directly from the data) can be exploited to enhance the quality of the blocks in a holistic loosely schema-aware (meta-)blocking approach that can be used to speed up your favorite Entity Resolution algorithm. We call it Blast (Blocking with Loosely-Aware Schema Techniques). We show how Blast can automatically extract this loose information by adopting a LSH-based step for efficiently scaling to large datasets. We experimentally demonstrate, on real-world datasets, how Blast outperforms the state-of-the-art unsupervised meta-blocking approaches, and, in many cases, also the supervised one.

References

[1]

A. Agresti and M. Kateri. Categorical data analysis. In International Encyclopedia of Statistical Science, pages 206--208. 2011.

[2]

S. Bergamaschi, D. Ferrari, F. Guerra, G. Simonini, and Y. Velegrakis. Providing insight into data source topics. Journal on Data Semantics, pages 1--18, 2016.

[3]

C. Bizer, T. Heath, and T. Berners-Lee. Linked data-the story so far. Semantic Services, Interoperability and Web Applications: Emerging Concepts, 5(3):1--22, 2009.

[4]

A. Broder. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences 1997, SEQUENCES '97, pages 21--. IEEE Computer Society, 1997.

Digital Library

[5]

P. Christen. A survey of indexing techniques for scalable record linkage and deduplication. TKDE, 24(9):1537--1555, 2012.

Digital Library

[6]

T. M. Cover and J. A. Thomas. Elements of information theory. John Wiley & Sons, 2012.

Digital Library

[7]

T. de Vries, H. Ke, S. Chawla, and P. Christen. Robust record linkage blocking using suffix arrays and bloom filters. TKDD, 5(2):9, 2011.

Digital Library

[8]

X. L. Dong and D. Srivastava. Big data integration. Synthesis Lectures on Data Management, 2015.

[9]

L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In VLDB, pages 491--500, 2001.

Digital Library

[10]

H. Köpcke and E. Rahm. Frameworks for entity matching: A comparison. Data Knowl. Eng., 69(2):197--210, 2010.

Digital Library

[11]

J. Leskovec, A. Rajaraman, and J. D. Ullman. Mining of Massive Datasets, 2nd Ed. 2014.

[12]

Y. Ma and T. Tran. Typimatch: type-specific unsupervised learning of keys and key values for heterogeneous web data integration. In WSDM, pages 325--334, 2013.

Digital Library

[13]

J. Madhavan, S. Cohen, X. L. Dong, A. Y. Halevy, S. R. Jeffery, D. Ko, and C. Yu. Web-scale data integration: You can afford to pay as you go. In CIDR, pages 342--350, 2007.

[14]

A. McCallum, K. Nigam, and L. H. Ungar. Efficient clustering of high-dimensional data sets with application to reference matching. In SIGKDD, pages 169--178, 2000.

Digital Library

[15]

F. Naumann and M. Herschel. An introduction to duplicate detection. Synthesis Lectures on Data Management, 2010.

Digital Library

[16]

A. N. Ngomo and S. Auer. LIMES - A time-efficient approach for large-scale link discovery on the web of data. In IJCAI, pages 2312--2317, 2011.

Digital Library

[17]

G. Papadakis, G. Alexiou, G. Papastefanatos, and G. Koutrika. Schema-agnostic vs schema-based configurations for blocking methods on homogeneous data. PVLDB, 9(4):312--323, 2015.

Digital Library

[18]

G. Papadakis, E. Ioannou, T. Palpanas, C. Niederée, and W. Nejdl. A blocking framework for entity resolution in highly heterogeneous information spaces. TKDE, 25(12):2665--2682, 2013.

Digital Library

[19]

G. Papadakis, G. Papastefanatos, and G. Koutrika. Supervised meta-blocking. PVLDB, 7(14):1929--1940, 2014.

Digital Library

[20]

G. Papadakis, G. Papastefanatos, T. Palpanas, and M. Koubarakis. Scaling entity resolution to large, heterogeneous data with enhanced meta-blocking. In EDBT, pages 221--232, 2016.

[21]

P. Shvaiko and J. Euzenat. Ontology matching: State of the art and future challenges. TKDE, 25(1):158--176, 2013.

Digital Library

[22]

P. Vandenbussche and B. Vatant. Linked open vocabularies. ERCIM, 2014(96), 2014.

Cited By

Hagan NTalburt J(2024)SparkDWM: a scalable design of a Data Washing Machine using Apache SparkFrontiers in Big Data10.3389/fdata.2024.14460717Online publication date: 9-Sep-2024
https://doi.org/10.3389/fdata.2024.1446071
Hagan NTalburt JAnderson KHagan D(2024)A scalable MapReduce-based design of an unsupervised entity resolution systemFrontiers in Big Data10.3389/fdata.2024.12965527Online publication date: 1-Mar-2024
https://doi.org/10.3389/fdata.2024.1296552
Zhu XXie MDeng TZhang Q(2024)HyperBlocker: Accelerating Rule-Based Blocking in Entity Resolution Using GPUsProceedings of the VLDB Endowment10.14778/3705829.370584718:2(308-321)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.14778/3705829.3705847
Show More Cited By

BLAST: a loosely schema-aware meta-blocking approach for entity resolution
1. Information systems
  1. Information systems applications

Recommendations

Blast: a binary large structured transmission format for the web
Web3D '14: Proceedings of the 19th International ACM Conference on 3D Web Technologies

Recent advances in Web technology, especially real-time 3D content using WebGL, require an efficient way to transfer binary data. Images, audio and video have respective HTML tags and accompanying data formats that transparently handle binary ...
ArThUR: A Tool for Markov Logic Network
Proceedings of the Confederated International Workshops on On the Move to Meaningful Internet Systems: OTM 2014 Workshops - Volume 8842

Logical approaches-and ontologies in particular-offer a well-adapted framework for representing knowledge present on the Semantic Web [InlineEquation not available: see fulltext.]. These ontologies are formulated in [InlineEquation not available: see ...
The Coolest Way to Generate Binary Strings

Pick a binary string of length n and remove its first bit b . Now insert b after the first remaining 10, or insert $\overline{b}$ at the end if there is no remaining 10. Do it again. And again. Keep going! Eventually, you will cycle through all 2ⁿ of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 9, Issue 12

August 2016

345 pages

ISSN:2150-8097

Editors:
Surajit Chaudhuri
Microsoft Research
,
Jayant Haritsa
I.I.Sc. Bangalore

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2016

Published in PVLDB Volume 9, Issue 12

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
203
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hagan NTalburt J(2024)SparkDWM: a scalable design of a Data Washing Machine using Apache SparkFrontiers in Big Data10.3389/fdata.2024.14460717Online publication date: 9-Sep-2024
https://doi.org/10.3389/fdata.2024.1446071
Hagan NTalburt JAnderson KHagan D(2024)A scalable MapReduce-based design of an unsupervised entity resolution systemFrontiers in Big Data10.3389/fdata.2024.12965527Online publication date: 1-Mar-2024
https://doi.org/10.3389/fdata.2024.1296552
Zhu XXie MDeng TZhang Q(2024)HyperBlocker: Accelerating Rule-Based Blocking in Entity Resolution Using GPUsProceedings of the VLDB Endowment10.14778/3705829.370584718:2(308-321)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.14778/3705829.3705847
Zahrae SAli CMohamed A(2024)Record Linkage Approaches in Big Data: A Comprehensive Review2024 International Conference on Intelligent Systems and Computer Vision (ISCV)10.1109/ISCV60512.2024.10620076(1-6)Online publication date: 8-May-2024
https://doi.org/10.1109/ISCV60512.2024.10620076
Shahbazi NWang JMiao ZBhutani N(2024)Fairness-Aware Data Preparation for Entity Matching2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00268(3476-3489)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00268
Neuhof FFisichella MPapadakis GNikoletos KAugsten NNejdl WKoubarakis M(2024)Open benchmark for filtering techniques in entity resolutionThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00868-733:5(1671-1696)Online publication date: 9-Jul-2024
https://dl.acm.org/doi/10.1007/s00778-024-00868-7
Leventidis ADi Rocco LGatterbauer WMiller RRiedewald M(2023)DomainNet: Homograph Detection and Understanding in Data Lake DisambiguationACM Transactions on Database Systems10.1145/361291948:3(1-40)Online publication date: 12-Sep-2023
https://dl.acm.org/doi/10.1145/3612919
Buono FFaggioli GPaganelli MBaraldi AGuerra FFerro N(2023)A Framework to Evaluate the Quality of Integrated DatasetsACM SIGAPP Applied Computing Review10.1145/3584014.358401522:4(5-23)Online publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1145/3584014.3584015
Wang RLi YWang J(2023)Sudowoodo: Contrastive Self-supervised Learning for Multi-purpose Data Integration and Preparation2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00391(1502-1515)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00391
Papadakis GFisichella MSchoger FMandilaras GAugsten NNejdl W(2023)Benchmarking Filtering Techniques for Entity Resolution2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00389(653-666)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00389
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents