ARM: Authenticated approximate record matching for outsourced databases

Boxiang Dong, Wendy Wang

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

1 Citation (Scopus)

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

Fingerprint

Outsourcing
Authentication
Servers
Data integration
Data structures
Acoustic waves
Data base
Service provider
Costs
Experiments
Integration process
Experiment
Information integration
Cheating
Paradigm

Keywords

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

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
Dong, Boxiang ; Wang, Wendy. / ARM : Authenticated approximate record matching for outsourced databases. Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 591-600 (Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016).
@inproceedings{323d7ff60f5d4c4f9fb794b9aff76bf9,
title = "ARM: Authenticated approximate record matching for outsourced databases",
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.",
keywords = "Approximate string matching, Authentication, MB-Tree, Outsourcing, Verification object",
author = "Boxiang Dong and Wendy Wang",
year = "2016",
month = "1",
day = "1",
doi = "10.1109/IRI.2016.86",
language = "English",
series = "Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "591--600",
booktitle = "Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016",

}

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. Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016, Institute of Electrical and Electronics Engineers Inc., pp. 591-600, 17th IEEE International Conference on Information Reuse and Integration, IRI 2016, Pittsburgh, United States, 28/07/16. https://doi.org/10.1109/IRI.2016.86

ARM : Authenticated approximate record matching for outsourced databases. / Dong, Boxiang; Wang, Wendy.

Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 591-600 (Proceedings - 2016 IEEE 17th International Conference on Information Reuse and Integration, IRI 2016).

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

TY - GEN

T1 - ARM

T2 - Authenticated approximate record matching for outsourced databases

AU - Dong, Boxiang

AU - Wang, Wendy

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Approximate string matching

KW - Authentication

KW - MB-Tree

KW - Outsourcing

KW - Verification object

UR - http://www.scopus.com/inward/record.url?scp=84991225870&partnerID=8YFLogxK

U2 - 10.1109/IRI.2016.86

DO - 10.1109/IRI.2016.86

M3 - Conference contribution

AN - SCOPUS:84991225870

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

SP - 591

EP - 600

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

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