Advanced Data Indexing

Προηγμένη Ευρετηρίαση Δεδομένων (ΠΜΣ)

Ακαδημαϊκό Έτος 2014-2015

Διδάσκων:	Τιάκας Ελευθέριος
Email:	tiakas@csd.auth.gr
URL:	http://delab.csd.auth.gr/~tiakas/
Διαλέξεις:	Παρασκευή 15:30-18:00 Αίθουσα 1 Forum Εθνικής Αντιστάσεως 16, 2^ος Όροφος, Καλαμαριά

Περιγραφή

Η τεράστια πρόοδος στην ικανότητά μας να αποκτούμε, να αποθηκεύουμε και να επεξεργαζόμαστε δεδομένα καθώς και η μεγάλη διείσδυση των υπολογιστών στην ζωή μας, έχει ως αποτέλεσμα την θεαματική αύξηση του όγκου των δεδομένων που χειριζόμαστε και αποθηκεύουμε. Αυτή η διαθεσιμότητα υψηλής ποιότητας δεδομένων έχει οδηγήσει τόσο την Επιστήμη όσο και την Βιομηχανία σε τεράστια άλματα. Γενικά, η κοινωνία μας βασίζεται ολοένα και περισσότερο στην αφθονία δεδομένων, κάτι που θα συνεχιστεί και τα επόμενα χρόνια.
Το αυξανόμενο πλήθος εφαρμογών για επεξεργασία τεραστίου όγκου δεδομένων που γενικά βασίζεται στην αποδοτικότητα των αλγορίθμων ολοένα και αυξάνεται. Παρόλα αυτά, το τεράστιο μέγεθος των δεδομένων καθώς και το μικρό μέγεθος των υπολογιστικών μηχανών, υποδηλώνουν ότι η αρχιτεκτονική της ιεραρχίας μνήμης παίζει έναν ολοένα και σπουδαιότερο λόγο στην αποδοτικότητα των αλγορίθμων. Επομένως, η διαθεσιμότητα τεράστιου όγκου δεδομένων προς επεξεργασία θέτει νέες προκλήσεις στους σχεδιαστές αλγορίθμων και συστημάτων και όχι μόνο. Ο στόχος του συγκεκριμένου μαθήματος είναι να εξετάσει τέτοιες σύγχρονες μεθόδους για τη διαχείριση τεράστιου όγκου δεδομένων.

Σελίδα Μαθήματος 2013-2014

Ανακοινώσεις

(6/3/2015) Εδώ θα βρείτε την 1η προγραμματιστική εργασία.

(2/4/2015) Παρουσίαση Ερευνητικής-Βιβλιογραφικής Εργασίας:

Κάθε ομάδα 2 ή 3 φοιτητών θα πρέπει να επιλέξει μία δημοσίευση (research paper) από ένα από τα παρακάτω συνέδρια:

VLDB 2015 VLDB 2014

EDBT 2015 EDBT 2014

ICDE 2015 ICDE 2014

SIGMOD 2015 SIGMOD 2014

SIGKDD 2015 SIGKDD 2014

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

Η διαδικασία θα είναι η εξής:

· Κάθε ομάδα μόλις επιλέξει μία δημοσίευση θα την ανακοινώσει στον διδάσκοντα με τους ΑΜ των φοιτητών που την αποτελούν.

· Ο διδάσκων θα ανακοινώσει το θέμα με τους ΑΜ της ομάδας στην ιστοσελίδα εάν δεν υπάρχει ταύτιση θέματος με άλλη ομάδα. Διαφορετικά, η ομάδα που θα δηλώσει πρώτη χρονικά ένα θέμα το κατοχυρώνει.

· Το παραδοτέο υλικό (power point) θα παρουσιαστεί μόνο προφορικά από τους φοιτητές της κάθε ομάδας. Οι ομάδες θα παρουσιάσουν την δημοσιευμένη εργασία στις τελευταίες δύο διαλέξεις του μαθήματος. Ο χρόνος της παρουσίασης για την κάθε ομάδα θα είναι 25 λεπτά. Δεν χρειάζεται να γραφεί κάποια αναφορά ή οποιοδήποτε άλλο κείμενο.

· Η εργασία αυτή αντιστοιχεί σε 3 βαθμούς συνολικά.

· Αν θέλετε να παρουσιάσετε κάτι που δεν υπάρχει στην παραπάνω λίστα αλλά εμπίπτει στα ενδιαφέροντα του μαθήματος μπορείτε να έρθετε σε συνεννόηση με τον διδάσκοντα.

· Θα πρέπει να έχετε ορίσει τις ομάδες και τα θέματα το αργότερο μέχρι τις 8/5/2015.

Θέματα που Επιλέχθηκαν:

(10/4/2015) ΟΜΑΔΑ-1: ΑΜ: 585,597 Θέμα: ”In-Memory Performance for Big Data” (από VLDB) [Goetz Graefe et al.]

(19/4/2015) ΟΜΑΔΑ-2: ΑΜ: 560,604 Θέμα: ” Holistic Indexing in Main-memory Column-stores” (από SIGMOD) [Eleni Petraki et al.]

(24/4/2015) ΟΜΑΔΑ-3: ΑΜ: 563,589 Θέμα: “Memory Efficient Hash Joins” (από VLDB) [R. Barber et al.]

(24/4/2015) ΟΜΑΔΑ-4: ΑΜ: 567,586,593 Θέμα: “Anti-Caching: A New Approach to Database Management System Architecture” (από VLDB) [Justin DeBrabant et al.]

(1/5/2015) ΟΜΑΔΑ-5: ΑΜ: 562,576 Θέμα: “Indexing for Interactive Exploration of Big Data Series” (από SIGMOD) [Kostas Zoumpatianos et al.]

(4/5/2015) ΟΜΑΔΑ-6: ΑΜ: 568,575,578 Θέμα: “'Persistent B+Trees in Non Volatile Main Memory” (από VLDB) [Shimin Chen et al.]

(8/5/2015) ΟΜΑΔΑ-7: ΑΜ: 553,577,580 Θέμα: “A Scalable Search Engine for Mass Storage Smart Objects “ (από VLDB) [Nicolas Anciaux et al.]

(8/5/2015) ΟΜΑΔΑ-8: ΑΜ: 498,556,571 Θέμα: “Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions” (από VLDB) [Hiroshi Inoue et al.]

(15/4/2015) Εδώ θα βρείτε την 2η προγραμματιστική εργασία.

(5/6/2015) Προτεινόμενα Θέματα Διπλωματικών Εργασιών.

(11/6/2015) Ενδεικτικές ερωτήσεις-θέματα για την εξέταση της θεωρίας

(1/7/2015) Σύμφωνα με απόφαση της Πρυτανείας του ΑΠΘ δεν θα γίνει η εξέταση του μαθήματος την Παρασκευή 3/7. Η εξέταση μεταφέρεται για την Τρίτη 7/7 ώρα 3:30μμ-6:00μμ στην αίθουσα 1 στο Forum (Εθνικής Αντιστάσεως 16, 2ος Όροφος, Καλαμαριά), στον ίδιο χώρο δηλαδή που έγιναν και οι διαλέξεις.

(10/7/2015) Εδώ θα βρείτε την Τελική Βαθμολογία σας. Καλό Καλοκαίρι.

Διαλέξεις

Διάλεξη	Ημερομηνία	Περιγραφή (Ύλη Εβδομάδας)	Υλικό
1η	27/2/2015	Εισαγωγή - Το πρόβλημα του τεράστιου όγκου δεδομένων - Παραδείγματα	Διαφάνειες pptx pdf
2η	6/3/2015	Ιεραρχία Μνήμης - Ο Σκληρός Δίσκος	Διαφάνειες pptx pdf Επιπλέον πληροφορίες και στοιχεία για την ιεραρχία μνήμης και τους σκληρούς δίσκους θα βρείτε στα [11], στο [3] (σελ. 1-23), στο [13], καθώς και στα links των διαφανειών.
3η	13/3/2015	Μοντέλα Δευτερεύουσας Μνήμης - Τεχνική Λωρίδων - Στοιχειώδεις Διαδικασίες - Ι/Ο Κόστος - Ταξινόμηση - Ταξινόμηση Διαχωρισμού και Συγχώνευσης	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τα μοντέλα και την τεχνική λωρίδων θα βρείτε στο [3] (σελ. 1-20). Για τις στοιχειώδεις διαδικασίες και το Ι/Ο κόστος στο [3] (σελ. 21-28). Για την ταξινόμηση και τους αλγορίθμους διαχωρισμού και συγχώνευσης στο [3] (σελ. 29-32, 38-40, 54).
4η	20/3/2015	Αναζήτηση, Δέντρα, (α,b)-Δέντρα, Β-Δέντρα, Β^+-Δέντρα, Βαροζυγισμένα Β-Δέντρα.	Διαφάνειες pptx pdf και pptx pdf Πληροφορίες και στοιχεία για τα (α,b)-Δέντρα, Β-Δέντρα, Β^+-Δέντρα στο [4] (σελ. 3-6). Για τα Βαροζυγισμένα Β-Δέντρα στο [4] (σελ. 6-8).
5η	27/3/2015	Βαροζυγισμένα Β-Δέντρα (συνέχεια), Διαχρονικά Β-Δέντρα, Δέντρα Ενδιάμεσης Μνήμης	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τα Βαροζυγισμένα Β-Δέντρα στο [4] (σελ. 6-8). Για τα Διαχρονικά Β-Δέντρα στο [4] (σελ. 8-10). Για τα Δέντρα Ενδιάμεσης Μνήμης στο [4] (σελ. 10-13).
6η	3/4/2015	Παρουσιάσεις από φοιτητές της 1ης Εργασίας - Κατακερματισμός - Συναρτήσεις Κατακερματισμού - Κατακερματισμός με αλυσίδες - Καθολικός Κατακερματισμός - Τέλειος Κατακερματισμός	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τον Κατακερματισμό και τις Συναρτήσεις Κατακερματισμού στο [12] και στο [2] (Κεφ.9^ο παρ. 9.1,9.2). Για τον Κατακερματισμό με Αλυσίδες στο [12] και στο [2] (παρ. 9.3.1). Για την μέθοδο Διαίρεσης και Πολλαπλασιασμού στο [2] (παρ. 9.2.1, 9.2.2). Για τον Καθολικό Κατακερματισμό στο [12] και στο [2] (παρ. 9.2.3). Για τις k-wise ανεξάρτητες οικογένειες συναρτήσεων στο [12]. Για τον Τέλειο Κατακερματισμό στο [12] και στο [2] (παρ. 9.2.4).
7η	24/4/2015	Κατακερματισμός με Ανοικτή Διευθυνσιοδότηση - Γραμμικός Έλεγχος - Τετραγωνικός Έλεγχος - Διπλός Κατακερματισμός - Μέθοδος του Brent - Κατακερματισμός Πολλαπλής Επιλογής	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τον Κατακερματισμό με Ανοικτή Διευθυνσιοδότηση στο [2] (Κεφ.9^ο παρ. 9.3.2). Για τον Γραμμικό Έλεγχο στο [12] και στο [2] (παρ. 9.3.3). Για τον Τετραγωνικό Έλεγχο στο [2] (παρ. 9.3.4). Για τον Διπλό Κατακερματισμό στο [2] (παρ. 9.3.5). Για την Μέθοδο του Brent στο [2] (παρ. 9.3.6). Για τον Κατακερματισμό Πολλαπλής Επιλογής στο [2] (παρ. 9.3.7).
8η	8/5/2015	Ασύμμετρος Κατακερματισμός - Κατακερματισμός LCFS - Robin-Hood Κατακερματισμός - Cuckoo Κατακερματισμός - Bloom Φίλτρα - Στρατηγικές - Επεκτάσιμος Κατακερματισμός	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τον Ασύμμετρο Κατακερματισμό στο [2] (Κεφ.9^ο παρ. 9.3.8). Για τον Κατακερματισμό LCFS στο [2] (παρ. 9.3.9). Για τον Robin-Hood Κατακερματισμό στο [2] (παρ. 9.3.10). Για τον Cuckoo Κατακερματισμό στο [12] και στο [2] (παρ. 9.3.11). Για τα Bloom Φίλτρα στο [14]. Για τις Στρατηγικές Κατακερματισμού στη Δευτερεύουσα Μνήμη και για τον Επεκτάσιμο Κατακερματισμό στο [3] (σελ. 83-88).
9η	15/5/2015	Εισαγωγή στις Ροές - Μοντέλα Ροών - Εργαλεία - Δειγματοληψία - Sketches	Διαφάνειες pptx pdf Πληροφορίες και στοιχεία για τις ροές στο [6] (σελ.10-12). Για τα βασικά μοντέλα ροών στο [6] (σελ. 12-18). Για το πρόβλημα της εύρεσης αριθμών που λείπουν στο [6] (σελ. 5-7). Για τα βασικά εργαλεία, την προσέγγιση, την τυχαιότητα, τα όρια πιθανοτήτων και την δειγματοληψία στο [6] (σελ. 19-25). Για τα Sketches και το Count-Min Sketch στο [6] (σελ. 25-28)..
10η	22/5/2015	Sketches - Κυλιόμενα παράθυρα - Ιστογράμματα - Wavelets Το πρόβλημα των συχνών στοιχείων - Αλγόριθμοι που βασίζονται σε μετρητές	Διαφάνειες pptx pdf και pptx pdf Πληροφορίες και στοιχεία για το FM Sketch στο [6] (σελ. 28-29). Για το μοντέλο κυλιόμενου παράθυρου στο [6] (σελ.53-54). Για τα ιστογράμματα στο [6] (σελ.34,36,50,51). Για τα Wavelets στο [6] (σελ.32,33). Πληροφορίες και στοιχεία για το πρόβλημα των συχνών στοιχείων (Frequent Items - Heavy Hitters) στο [6] (σελ. 21-22 και 30-32): Αλγόριθμοι που βασίζονται σε μετρητές (Frequent, Lossy-Counting, Space-Saving).
11η	29/5/2015	Το πρόβλημα των συχνών στοιχείων - Αλγόριθμοι που χρησιμοποιούν Sketches Αποτυπώματα - Haar Wavelets	Διαφάνειες pptx pdf και pptx pdf Πληροφορίες και στοιχεία για το πρόβλημα των συχνών στοιχείων (Frequent Items - Heavy Hitters) στο [6] (σελ. 21-22 και 30-32): Αλγόριθμοι που χρησιμοποιούν Sketches (Hierarchical Search + Group Testing, Count-Min Sketch, Count Sketch). Πληροφορίες και στοιχεία για τα αποτυπώματα του Rabin στο [15] και για τα Haar Wavelets στο [6] (σελ.32,33).
12η	5/6/2015	Παρουσιάσεις Ερευνητικών-Βιβλιογραφικών Εργασιών	ΟΜΑΔΕΣ: 1, 2, 3, 4
13η	12/6/2015	Παρουσιάσεις Ερευνητικών-Βιβλιογραφικών Εργασιών	ΟΜΑΔΕΣ: 5, 6, 7, 8

Χρήσιμο Υλικό

Τα ακόλουθα βιβλία και ιστότοποι είναι αρκετά χρήσιμοι για το μάθημα (με αστεράκι είναι τα βασικά εγχειρίδια).

1.    J. Abello, P.M. Pardalos and M.G.C. Resende (editors). Handbook of Massive Data Sets. Kluwer Academic Publishers. 2002, ISBN: 1-4020-0489-3.

2.    *D. Menta and S Sahni, Handbook of Data Structures and Application. 2005, ISBN 1-5848-8435-5

3.    *J. Vitter, Algorithms and Data Structures for External Memory, Book, (http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf)

4.    *External Memory Geometric Data Structures. L. Arge, Duke University Lecture notes

5.    *Erik Demaine, Cache Oblivious Algorithms and Data-Structures, in Lecture Notes from the EEF Summer School on Massive Data Sets, Lecture Notes in Computer Science, BRICS, University of Aarhus, Denmark, June 27-July 1, 2002, (http://erikdemaine.org/papers/BRICS2002/)

6.    *Muthu Muthukrishnan, Data Streams: Algorithms and Applications (ebook) (http://algo.research.googlepages.com/eight.ps)

7.    Charu C. Aggarwal, Philip S. Yu, A Survey of Synopsis Construction in Data Streams, Chapter 9, Data Streams, Book Series: Advances in Database Systems, ISBN 978-0-387-28759-1 (Print) 978-0-387-47534-9 (Online), (http://www.springerlink.com/content/wx43561lv4678637/)  (Μπορείτε να κατεβάσετε ηλεκτρονικά το συγκεκριμένο άρθρο μόνο από Η/Υ εντός του ΑΠΘ - ή με virtual Network)

8. Τοπολογίες P2P δικτύων με πλεονεκτήματα και μειονεκτήματα. http://www.openp2p.com/pub/a/p2p/2002/01/08/p2p_topologies_pt2.html

9. Το CHORD: http://pdos.csail.mit.edu/chord/papers/chord.pdf

10. Γενικά περί P2P: http://www.dmst.aueb.gr/dds/pubs/jrnl/2004-ACMCS-p2p/html/AS04.pdf

11. Σχετικά με σκληρούς δίσκους και SSDs από τη Wikipedia καθώς και σχετικά με τις ιεραρχίες μνήμης.

12. *Σημειώσεις για Hashing.

13. Algorithms for Memory Hierarchies. Advanced Lectures. U. Meyer, P. Sanders and J. Sibeyn. Springer-Verlag, LNCS 2625.

14. Πληροφορίες για Bloom Φίλτρα: http://en.wikipedia.org/wiki/Bloom_filter, Προσομοιωτής: https://www.jasondavies.com/bloomfilter/.

15. Πληροφορίες για Rabin fingerprinting scheme: http://en.wikipedia.org/wiki/Rabin_fingerprint