Paper Info
Title
An Efficient and Scalable Algorithm to Mine Functional Dependencies from Distributed Big Data
Abstract
A crucial step in improving data quality is to discover semantic relationships between data. Functional dependencies are rules that describe semantic relationships between data in relational databases and have been applied to improve data quality recently. However, traditional functional discovery algorithms applied to distributed data may lead to errors and the inability to scale to large-scale data. To solve the above problems, we propose a novel distributed functional dependency discovery algorithm based on Apache Spark, which can effectively discover functional dependencies in large-scale data. The basic idea is to use data redistribution to discover functional dependencies in parallel on multiple nodes. In this algorithm, we take a sampling approach to quickly remove invalid functional dependencies and propose a greedy-based task assignment strategy to balance the load. In addition, the prefix tree is used to store intermediate computation results during the validation process to avoid repeated computation of equivalence classes. Experimental results on real and synthetic datasets show that the proposed algorithm in this paper is more efficient than existing methods while ensuring accuracy.
Year
DOI
Venue
2022
10.3390/s22103856
SENSORS
Keywords
DocType
Volume
data mining, functional dependency, distributed computing, big data
Journal
22
Issue
ISSN
Citations 
10
1424-8220
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Wanqing Wu100.34
Wenyu Mao200.34