Approximate Top-K Answering under Uncertain Schema Mappings

Li, Longzhuang, Tian, Feng, Liu, Yonghuai and Mao, Shanxian (2018) Approximate Top-K Answering under Uncertain Schema Mappings. Data & Knowledge Engineering, 118. pp. 71-91. ISSN 0169-023X DOI

[img] Text
DKE Elsevier_revision.docx - Accepted Version
Restricted to Repository staff only until 17 October 2020.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (843kB) | Request a copy


Data integration techniques provide a communication bridge between isolated sources and offer a platform for information exchange. When the schemas of heterogeneous data sources map to the centralized schema in a mediated data integration system or a source schema maps to a target schema in a peer-to-peer system, multiple schema mappings may exist due to the ambiguities in the attribute matching. The obscure schema mappings lead to the uncertainty in query answering, and frequently people are only interested in retrieving the best k answers (top-k) with the biggest probabilities. Retrieving the top-k answers efficiently has become a research issue. For uncertain queries, two semantics, by-table and by-tuple, have been developed to capture top-k answers based on the schema mapping probabilities. However, although the existing algorithms support certain features to capture the accurate top-k answers and avoid accessing all data from sources, they cannot effectively reduce the number of processed tuples in most cases. In this paper, new algorithms based on the histogram approximation and heuristic are proposed to efficiently identify the top-k answers for the data integration systems under uncertain schema mappings. In the experiments, the Histogram algorithm in the by-table semantics and the expected approach in the by-tuple semantics are shown to significantly reduce the number of processed tuples while maintaining high accuracy with the estimated probabilistic confidence.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computing and Information Systems
Date Deposited: 22 Nov 2018 13:21

Archive staff only

Item control page Item control page