Συντάχθηκε 25-01-2013 11:08
από Galateia Malandraki
Email συντάκτη: gmalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΑΡΜΗΧ.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΔΙΑΤΡΙΒΗΣ
Μαμμάς Στυλιανός-Γεώργιος
με θέμα
“Σχεδιασμός Αποδοτικών Αλγορίθμων Προσέγγισης Πιθανοτικών Δεδομένων”
“Designing Efficient Algorithms for Approximating Probabilistic Data”
Τρίτη 29 Ιανουαρίου 2013, 13:00
Αίθουσα Συνεδριάσεων Εργαστηρίου Τεχνολογίας Συστημάτων Λογισμικού & Δικτυακών Εφαρμογών (Softnet) 141.Α11,
Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επ. Καθ. Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθ. Μίνως Γαροφαλάκης
Επ. Καθ. Βασίλειος Σαμολαδάς
Abstract
Histograms have proven to be a very effective summarization mechanism, and are widely used to capture data distributions. Currently, they are an important part in commercial query engines.
Moreover, there is a growing realization that modern Data Base Management Systems (DBMSs) must be able to manage data that contain uncertainties that are represented in the form of probabilistic relations. However, it is difficult to work with the probabilistic data, because of their high complexity in contrast with the deterministic case. Even for simple queries, there is a #P hard complexity, and thus effective probabilistic histogram construction arises. Optimal Dynamic Programming (DP) algorithms, have been proposed, for building optimal probabilistic histograms for probabilistic data. Although, these algorithms are optimal in terms of overall error, they have high time-complexity.
Since, histograms are themselves approximation schemes, an extra approximation factor for speed up can be tolerable.
The main contribution of this thesis, is the incorporation of (1+ε)-approximation schemes, in the probabilistic histogram construction process. In order to reduce the high computational cost of optimal probabilistic histogram construction, we set an approximation scheme to the optimal algorithm's DP framework. The speed up is obtained, because our approximate algorithm takes into consideration only a small set of sub-problems in the DP framework, against the exhaustive/optimal approach. Our algorithm provides guarantees to the overall error of the histogram, and gives the user a useful trade-off between the accuracy of the histogram and the computational cost. Our experimental study, to explore the effect of such approximation, shows that our approximation scheme produces almost-optimal probabilistic histograms, with clear benefits in time-complexity against the optimal algorithms.
