Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Bachelor's Thesis |
| Scope | Discipline-based scholarship |
| Title | Lineage Aggregation on Temporal-Probabilistic Relations |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Language |
|
| Institution | University of Zurich |
| Faculty | Faculty of Business, Economics and Informatics |
| Date | 2017 |
| Abstract Text | In this thesis, we investigate the challenges of lineage aggregation in temporal-probabilistic relations. In contrast to existing types of aggregation that have been specially treated, e.g. cummulative or selective, data lineage for a single result interval does not correspond to a single numerical value but can become as large as the number of input tuples. This leads to runtime and space efficiency problems due to the high number of tuples that might be valid over an interval. In order to overcome these overheads, we exploit the semantics of lineage aggregation and introduce the \emph{Lineage-Update} algorithm. The \emph{Lineage-Update} algorithm is a sweeping algorithm that uses a data structure tailored for the needs of lineage. By exploiting the semantics of lineage aggregation, our \emph{Lineage-Update} algorithm improves in both time and space complexity to existing approaches since it (a) updates data lineage instead of recomputing it for every result tuple and (b) avoids restoring subexpressions that occur in the lineages of consecutive tuples. We perform an extensive experimental analysis, using both synthetic and real datasets, that shows that \emph{Lineage-Update} outperforms established aggregation algorithms when lineage-aggregation is performed. |
| Zusammenfassung | In dieser Bachelorarbeit untersuchen wir die Herausforderungen von der Aggregation des Lineage Attributes mit zeitlich-probabilistische Relationen. Im Gegensatz zu den existierenden Aggregations-Typen, wie cumulative oder selective Aggregation, kann die aggregierte Lineage die gleiche Anzahl Elemente wie Tupels in der Input-Relation haben. Das Resultat der existierenden Aggregations-Typen ist immer eine einzelne Zahl. Das führt zu Effizienzproblemen in der Laufzeit und dem Speicher aufgrund der grossen Anzahl an Tupels, die zur gleichen Zeit aktiv sein können. Um diese Probleme zu lösen, nutzen wir die Semantik der Aggregation der Lineage und stellen den Lineage-Update Algorithmus vor. Der Lineage-Update Algorithmus ist ein sweeping basierender Algorithmus, der eine Daten Struktur verwendet, die speziell für die Aggregation der Lineage entwickelt wurde. Weil wir die Semantik der Aggregation der Lineage kennen und ausnutzen, hat unser Lineage-Update Algorithmus eine verbesserte Laufzeit und Speicher Verwendung, da er (a) die aggregierte Lineage aktualisiert anstatt sie ganz neu zu berechnen und (b) Teil-Ausdrücke der Resultate, die sich aufeinanderfolgenden Resultate teilen, nicht erneut speichert. Wir führen eine ausführliche empirische Analyse mit synthetischen und echten Datensets durch, die zeigt, dass der Lineage-Update Algorithmus besser als die existierenden Algorithmen funktioniert, wenn die Aggregation der Lineage ausgeführt wird. |
| PDF File |
Download
|
| Export |
BibTeX
|