Τεχνικές Επεξεργασίας Δεδομένων

Μαθησιακά Αποτελέσματα

Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με: (α) την εκμάθηση τεχνικών προσπέλασης δεδομένων μεγάλου όγκου από διάφορες πηγές και σε ποικίλους μορφότυπους καθώς και την εγγραφή τους με γρήγορο τρόπο, (β) την αποδοτική αποθήκευση και ανάκτηση των δεδομένων με χρήση κατάλληλων τεχνικών ευρετηρίασης, και (γ) τη σχεδίαση και ανάπτυξη αλγορίθμων επεξεργασίας δεδομένων με απώτερο στόχο την ανάπτυξη αποδοτικών εφαρμογών διαχείρισης δεδομένων.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής /τρια θα είναι σε θέση:

• να αναπτύσσει δεδομενο-κεντρικές εφαρμογές με έμφαση στην απόδοση και στην κλιμακωσιμότητα
• να χρησιμοποιεί τις καταλληλότερες μεθόδους ευρετηρίασης για το εκάστοτε πρόβλημα
• να αξιολογεί και βελτιώνει τα τμήματα ενός αλγόριθμου επεξεργασίας δεδομένων που επιφέρουν υψηλό υπολογιστικό φόρτο
• να εφαρμόζει τις καταλληλότερες τεχνικές επεξεργασίας δεδομένων που ταιριάζουν για τα υπό ανάλυση δεδομένα και για το εκτιμώμενο σύνολο επερωτήσεων
• να αναπτύσσει με τρόπο αποδοτικό αλγόριθμους επεξεργασίας δεδομένων

Περιεχόμενα

• Τρόπος λειτουργίας δίσκου και κύριας μνήμης, σειριακή και τυχαία προσπέλαση, θέματα κόστους και απόδοσης, τοπικότητα στο δίσκο και στη μνήμη, άμεση και έμμεση προσπέλαση, δομές δεδομένων κύριας μνήμης (πίνακες, ουρές προτεραιότητας, κατακερματισμός).
• Τεχνικές προσπέλασης για δομημένα, ημι-δομημένα και αδόμητα δεδομένα, και πιο συγκεκριμένα από: σχεσιακές βάσεις δεδομένων, XML, RDF, έγγραφα κειμένου (text), ιστοσελίδες στο Διαδίκτυο (web pages), διαδικτυακές προγραμματιστικές διεπαφές (Web APIs), κοινωνικά δίκτυα (social networks).
• Μονοδιάστατα δεδομένα και ευρετηρίαση, το B-tree, παραλλαγές (B+tree, B*tree), επερωτήσεις εύρους (range queries), αντεστραμμένα ευρετήρια (Inverted Indexes).
• Χωρικά δεδομένα, τύποι δεδομένων, τύποι χωρικών τελεστών επερώτησης, προσεγγιστική αναπαράσταση, μέτρα απόστασης, επεκτάσεις για πολυδιάστατα δεδομένα.
• Μέθοδοι ευρετηρίασης για χωρικά δεδομένα, η μέθοδος πλέγματος, χωρικά ευρετήρια (R-tree, Quad-Tree), καμπύλες πλήρωσης χώρου (Hilbert, Z-Order),
• Αναζήτηση με βάση την ομοιότητα (similarity search), k κοντινότεροι γείτονες (k-NN), αλγόριθμοι branch-and-bound, locality sensitive hashing (LSH), προσεγγιστικοί αλγόριθμοι k-NN.
• Αναζήτηση κορυφαίων k (top-k), αλγόριθμοι που βασίζονται προεπεξεργασία, άμεσοι αλγόριθμοι (online), ο αλγόριθμος του Fagin, αλγόριθμοι με χρήση ευρετηρίου.
• Αλγόριθμοι για επερωτήσεις σύζευξης (join queries), χωρικές συζεύξεις (spatial joins), συζεύξεις κορυφαίων k (top-k joins).
• Χωρο-κειμενικά δεδομένα (spatio-textual data), τύποι ερωτήσεων, μέθοδοι ευρετηρίασης, αλγόριθμοι επεξεργασίας.

Προτεινόμενα Συγγράμματα

• R. Ramakrishnan, J. Gehrke (2012): Συστήματα Διαχείρισης Βάσεων Δεδομένων, 3η έκδοση, Εκδόσεις Τζιόλα.
• Ε. Στεφανάκης (2003): Βάσεις γεωγραφικών δεδομένων και συστήματα γεωγραφικών πληροφοριών, Εκδόσεις Παπασωτηρίου.
• N. Mamoulis (2011): Spatial Data Management, Synthesis Lectures on Data Management, Morgan & Claypool.