Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Smart Caching for Efficient Functional Dependency Discovery. / Birillo, Anastasia; Bobrov, Nikita.
New Trends in Databases and Information Systems. Springer Nature, 2019. p. 52-59 (Communications in Computer and Information Science; Vol. 1064).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Smart Caching for Efficient Functional Dependency Discovery
AU - Birillo, Anastasia
AU - Bobrov, Nikita
N1 - Conference code: 231719
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Functional dependency (FD) is a concept for describing regularities in data, that traditionally was used for schema normalization. Recently, a different problem has emerged: For a given dataset, find FDs that are contained in it. Efficient FD discovery is of great importance due to FD usage in many tasks such as data cleaning, schema recovery, and query optimization. In this paper we consider a particular class of FD discovery algorithms that rely on partition intersection. We present a simple approach for caching intermediate results that are generated during run times of these algorithms. Our approach is essentially a heuristic that selects which partitions to cache based on measures of disorder in data. For this purpose, we adopt such well-known measures as Entropy and Gini Impurity, and propose a novel one—Inverted Entropy. Our approach has a negligible computational overhead, and can be used with a number of FD discovery algorithms, both exact and approximate. Our experiments demonstrate that our heuristic allows to decrease algorithm run times by up to 40% while simultaneously requiring up to an order of magnitude less space compared to the state-of-the-art caching approaches.
AB - Functional dependency (FD) is a concept for describing regularities in data, that traditionally was used for schema normalization. Recently, a different problem has emerged: For a given dataset, find FDs that are contained in it. Efficient FD discovery is of great importance due to FD usage in many tasks such as data cleaning, schema recovery, and query optimization. In this paper we consider a particular class of FD discovery algorithms that rely on partition intersection. We present a simple approach for caching intermediate results that are generated during run times of these algorithms. Our approach is essentially a heuristic that selects which partitions to cache based on measures of disorder in data. For this purpose, we adopt such well-known measures as Entropy and Gini Impurity, and propose a novel one—Inverted Entropy. Our approach has a negligible computational overhead, and can be used with a number of FD discovery algorithms, both exact and approximate. Our experiments demonstrate that our heuristic allows to decrease algorithm run times by up to 40% while simultaneously requiring up to an order of magnitude less space compared to the state-of-the-art caching approaches.
KW - Caching
KW - Entropy
KW - Functional dependency
KW - Gini impurity
KW - Partition caching
KW - Partition intersection
KW - PYRO
KW - TANE
UR - http://www.scopus.com/inward/record.url?scp=85072952979&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-30278-8_7
DO - 10.1007/978-3-030-30278-8_7
M3 - Conference contribution
AN - SCOPUS:85072952979
SN - 978-3-030-30277-1
T3 - Communications in Computer and Information Science
SP - 52
EP - 59
BT - New Trends in Databases and Information Systems
PB - Springer Nature
T2 - 23rd European Conference on Advances in Databases and Information Systems, ADBIS 2019
Y2 - 8 September 2019 through 11 September 2019
ER -
ID: 113380819