Distributed sliding-window matrix sketchingDistributed sliding-window matrix sketching
Διπλωματική Εργασία
Diploma Work
2016-08-222016enStreaming sketching algorithms are data-processing algorithms for the summarization of an input data stream under memory and computational constraints. Their input is a long or potentially unbounded sequence of items that can be parsed a single (or a limited number of times), and the objective is to construct a concise summary of the data – a sketch – which can be later used to approximate a quantity of interest. In this work, we focus on streaming matrix sketching methods: the input is a sequence of vectors which can be regarded as the rows of a large matrix. We briefly survey matrix sketching methods for generating various kinds of sketches. We will mostly focus on the problem of approximating the principal subspace of a large matrix under the streaming model and we will describe the state-of-the-art “Frequent Directions” method of Liberty. We will further review very recent extensions of this work to monitoring the principal subspace of a stream over a sliding time window. Here, the objective is to maintain a sketch that approximates the desired quantity for the most recent segment of the input. Finally, we conclude with a novel result on the distributed construction of sketches for the sliding window model and some future directions. http://creativecommons.org/licenses/by/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών ΥπολογιστώνAsteri_Irini_Dip_2016.pdfChania [Greece]Library of TUC2016-08-22application/octetstream138.7 kBfree
Asteri Eirini
Αστερη Ειρηνη
Garofalakis Minos
Γαροφαλακης Μινως
Samoladas Vasilis
Σαμολαδας Βασιλης
Deligiannakis Antonios
Δεληγιαννακης Αντωνιος
Πολυτεχνείο Κρήτης
Technical University of Crete
Data mining