National and Kapodistrian University of Athens
Enhancing CHRONOGRAPH: Adaptive Integer Compression for Temporal Graphs
Abstract
dc:descriptionΚαθώς τα χρονικά δεδομένα γράφων γίνονται όλο και μεγαλύτερα και πιο λεπτομερή, η ανάγκη για αποδοτικές τεχνικές συμπίεσης γίνεται επιτακτική, ώστε να μειωθεί ο χώ- ρος αποθήκευσης και να επιταχυνθεί η εκτέλεση ερωτημάτων. Το CHRONOGRAPH, ένα προηγμένο σύστημα συμπίεσης χρονικών γράφων, διαχωρίζει τη δομή του γράφου από τα χρονικά δεδομένα και χρησιμοποιεί την κωδικοποίηση Zeta για τη συμπίεση των χρο- νικών στιγμών. Ωστόσο, παρουσιάζει μειωμένη απόδοση όταν τα χρονικά σημεία είναι ακανόνιστα ή έχουν υψηλή συχνότητα. Σε αυτή τη διπλωματική εργασία προτείνεται μια βελτιωμένη μέθοδος συμπίεσης που βασίζεται σε έναν υβριδικό συνδυασμό τεχνικών συμπίεσης ακεραίων. Η μέθοδος αυτή συνδυάζει τους αλγορίθμους IntegratedIntCompressor (IIC), FastPFOR, VariableByte και ZetaLong, και επιλέγει αυτόματα την πιο κατάλληλη τεχνική για κάθε μπλοκ δεδομένων, με βάση τα στατιστικά του χαρακτηριστικά. Αυτή η προσαρμοστική προσέγγιση βελτιώ- νει σημαντικά την αποτελεσματικότητα της συμπίεσης, διατηρώντας ταυτόχρονα γρήγορη αποσυμπίεση και γρήγορη εκτέλεση ερωτημάτων. Η αξιολόγηση της μεθόδου σε πραγματικά και συνθετικά δεδομένα χρονικών γράφων δεί- χνει βελτίωση έως και 18% στην αναλογία συμπίεσης ενώ τα ερωτήματα πλήρους ανάκτη- σης γειτόνων ήταν έως και 35% ταχύτερα, με μέσο όρο βελτίωσης χρόνου εκτέλεσης άνω του 23% σε όλα τα σύνολα δεδομένων. Ωστόσο, τα στοχευμένα ερωτήματα παρουσίασαν μικτά αποτελέσματα, με την απόδοση να εξαρτάται από τη δομή του γράφου και τον τύπο του ερωτήματος. Παρόλα αυτά, η συνολική εικόνα από τα πλήρη ερωτήματα και τη συ- μπίεση δείχνει ότι οι υβριδικές, προσαρμοστικές τεχνικές είναι ιδιαίτερα αποτελεσματικές για τη διαχείριση μεγάλων και ποικίλων χρονικών δεδομένων γράφων.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Λιακοπούλου Αθηνά
- Liakopoulou Athina
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:5300598