ARM: Authenticated approximate record matching for outsourced databases

Boxiang Dong, Wendy Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this paper, we consider the outsourcing model in which a third-party server provides data integration as a service. Identifying approximately duplicate records in databases is an essential step for the information integration processes. Most existing approaches rely on estimating the similarity of potential duplicates. The service provider returns all records from the outsourced dataset that are similar according to specific distance metrics. A major security concern of this outsourcing paradigm is whether the service provider returns sound and complete near-duplicates. In this paper, we design ARM, an authentication system for the outsourced record matching. The key idea of ARM is that besides the similar record pairs, the server returns the verification object (VO) of these similar pairs to prove their correctness. First, we design an authenticated data structure namedMB-Tree forVO construction. Second, we design a lightweight authentication method that can catch the service provider's various cheating behaviors by utilizing VOs. We perform an extensive set of experiment on real-world datasets to demonstrate that ARM can verify the record matching results with cheap cost.

Original languageEnglish
Title of host publicationProceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages591-600
Number of pages10
ISBN (Electronic)9781509032075
DOIs
StatePublished - 1 Jan 2016
Event17th IEEE International Conference on Information Reuse and Integration, IRI 2016 - Pittsburgh, United States
Duration: 28 Jul 201630 Jul 2016

Publication series

NameProceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016

Other

Other17th IEEE International Conference on Information Reuse and Integration, IRI 2016
CountryUnited States
CityPittsburgh
Period28/07/1630/07/16

Keywords

  • Approximate string matching
  • Authentication
  • MB-Tree
  • Outsourcing
  • Verification object

Fingerprint Dive into the research topics of 'ARM: Authenticated approximate record matching for outsourced databases'. Together they form a unique fingerprint.

  • Cite this

    Dong, B., & Wang, W. (2016). ARM: Authenticated approximate record matching for outsourced databases. In Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016 (pp. 591-600). (Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IRI.2016.86