Συστήματα δεδομένων και
αλγοριθμικές τεχνικές

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

Ο 1ος άξονας της Δράσης Δ1.2.3 έχει ως στόχο την εκ θεμελίων αναθεώρηση της απάντησης μιας ερώτησης σε βάσεις πολυδιάστατων δεδομένων και την αντικατάστασή της με μια αφήγηση δεδομένων (data story), δηλαδή μιας αναφοράς που όχι μόνο επιστρέφει τα αποτελέσματα, αλλά αυτόματα παράγει συνοπτικές και μεστές νοήματος επισημάνσεις (highlights) και τις κατάλληλες οπτικοποιήσεις, με στόχο την καλύτερη κατανόηση των αποτελεσμάτων από τον χρήστη. Αυτό επιτυγχάνεται με την χρήση μιας άλγεβρας τελεστών πρόθεσης (intentional operators), η χρήση της οποίας βοηθά τον χρήστη να δηλώσει την πρόθεσή του σχετικά με τα αποτελέσματα της ερώτησης και με την χρήση μηχανικής μάθησης και αλγορίθμων αποτίμησης ενδιαφέροντος, αξιολογούνται τα αποτελέσματα της ερώτησης και συναρτήσει της πρόθεσης του χρήστη να παράγεται το τελικό data story, με τα κατάλληλα highlights.
Αρχικά έγινε κατηγοριοποίηση της σχετικής βιβλιογραφίας σε τρεις περιοχές: (α) Data Narratives ή Αφηγήσεις Δεδομένων. Πρόκειται για άρθρα που περιγράφουν το μοντέλο γύρω από τα data stories το οποίο πρόκειται να ακολουθηθεί και για το παρόν έργο. Το μοντέλο αυτό θα καθορίζει τον τρόπο παρουσίασης των αποτελεσμάτων στον χρήστη, πώς δηλαδή θα είναι δομημένα τα data stories που θα παρουσιάζονται σαν αποτέλεσμα. (β) Intentional Operators που αφορά το μοντέλο προθέσεων (Intentional Model), το οποίο θα ακολουθηθεί για να μπορεί ο χρήστης να δηλώνει πρόθεση με την υποβολή ενός ερωτήματος. Επίσης, αυτή η κατηγορία εμπεριέχει άρθρα σχετικά με Intentional Operators, δηλαδή τελεστές πρόθεσης που ακολουθούν το μοντέλο πρόθεσης. Αυτοί οι operators είναι που χρησιμοποιούνται από τον χρήστη για την δήλωση πρόθεσης. (γ) Διερευνητική Ανάλυση Δεδομένων (Exploratory Data Analysis). Αυτή η κατηγορία περιλαμβάνει μια σειρά από συστήματα που στόχο έχουν την εξαγωγή των highlights από κάποια datasets, σαν αυτά τα οποία επιθυμούμε να εξάγουμε ώστε να παρουσιάσουμε στον χρήστη με την μορφή ενός data story. (δ) Αποτίμηση του ενδιαφέροντος ερωτήσεων και αποτελεσμάτων, που έχει ως αντικείμενο την κατάταξη ως προς διαφορετικές διαστάσεις ενδιαφέροντος των προαναφερθέντων στοιχείων και μπορεί να βοηθήσει στην διαδικασία επιλογής highlights που θα παρουσιάζονται στον χρήστη.
Σχετικά με την κατάσταση του συστήματος που χρησιμοποιείται ως βάση της ερευνητικής προσπάθειας, το Delian Cubes1, έχουν γίνει μια σειρά από αλλαγές. Αρχικά, έχει ενσωματωθεί το εργαλείο Spark, το οποίο μας επιτρέπει να ρωτάμε δεδομένα με την χρήση SQL χωρίς την χρήση ενός σχεσιακού DBMS, σε περιβάλλοντα εξαιρετικά μεγάλης παραλληλοποίησης. Έπειτα, στο σύστημα έχει ενσωματωθεί μια πρωτόλεια μορφή κάποιων βασικών πράξεων OLAP, όπως είναι το Roll-up και το Drill-down. Tέλος, έχει γίνει αναμόρφωση στον υπάρχοντα κώδικα.
Σημαντική πρόοδος έχει ήδη γίνει στον τομέα της αποτίμησης ενδιαφέροντος, τόσο σε θεωρητικό όσο και σε πρακτικό επίπεδο. Έχει αναπτυχθεί ένα σύνολο αλγορίθμων που ανήκει στις 4 κατηγορίες Interestingness, όπως αυτές ορίζονται από την σχετική βιβλιογραφία: Relevance, Novelty, Surprise, Peculiarity. Οι αλγόριθμοι αυτοί, όχι μόνο έχουν αναπτυχθεί σε θεωρητικό επίπεδο, αλλά έχουν προστεθεί με την μορφή κώδικα στο Delian Cubes, κάτι που μας δίνει την δυνατότητα της online αποτίμησης ενδιαφέροντος.
Στο πλαίσιο της ερευνητικής δραστηριότητας που αφορά στον 2ο άξονα της δράσης Δ1.2.3, αναπτύσσεται ένα πρότυπο παράλληλο και κατανεμημένο σύστημα διαχείρισης χωρικών δεδομένων. Ένα τέτοιο σύστημα έχει τεράστιο εύρος πρακτικών εφαρμογών, όπως πάνω σε geo-tagged δεδομένα μέσω GPS (π.χ. Twitter, Uber) ή IoT generated δεδομένα, καθώς ο ρυθμός παραγωγής δεδομένων αυξάνεται καθημερινά.
Στην τρέχουσά του μορφή, το σύστημα υποστηρίζει την αποδοτική απάντηση window και spatial join queries πολυγώνων. Σκοπός της συγκεκριμένης δραστηριότητας, είναι η υλοποίηση ενός ολοκληρωμένου συστήματος τέτοιου τύπου, το οποίο θα μπορεί να ανταγωνιστεί σε απόδοση τα ήδη υπάρχοντα. Δίνεται έμφαση στο να προσφέρει περισσότερη ευελιξία, καλύτερη εξατομίκευση και στο να έχει την ιδιότητα της επεκτασιμότητας, ώστε να μπορεί συνεχώς να αναβαθμίζεται όσον αφορά τις τεχνικές διαχείρισης χωρικών δεδομένων, βάσει της επιστημονικής εξέλιξης στον τομέα.
Το σύστημα χρησιμοποιεί τεχνική partitioning για να μοιράσει τα δεδομένα στους κόμβους του κατανεμημένου περιβάλλοντος. Ο διαμοιρασμός γίνεται με τρόπο που ευνοεί την παράλληλη διαχείριση των δεδομένων από τους κόμβους, έτσι ώστε ο καθένας να μπορεί να εργάζεται πάνω στα ιδιωτικά του δεδομένα ανεξάρτητα από τους άλλους. Έτσι ευνοείται ο παραλληλισμός αλλά και η συνολική ταχύτητα του συστήματος. Μέχρι στιγμής η τεχνική partitioning που χρησιμοποιείται ευνοεί εξαιρετικά τα window και spatial join queries. Για την υποστήριξη επιπλέον τύπων ευρετηρίων, θα διερευνηθεί η πιθανή ωφελιμότητα της τρέχουσας τεχνικής partitioning σε συνδυασμό με αυτά και θα γίνει έρευνα πάνω σε άλλες υποψήφιες τεχνικές που ενδέχεται να ωφελήσουν το σύστημα.
Πέραν του παραλληλισμού λόγω του κατανεμημένου περιβάλλοντος, γίνεται χρήση (όπου διαπιστώθηκε ότι ωφελεί) των νημάτων του κάθε κόμβου, με αποτέλεσμα να παραλληλοποιθούν ακόμη περισσότερο ορισμένες λειτουργίες ευνοώντας έτσι την συνολική ταχύτητα απάντησης των ευρετηρίων. Το σύστημα μπορεί να απαντήσει αποδοτικά σε window queries και spatial joins πολυγώνων σε χρόνο που μπορεί να συγκριθεί με μοντέρνα state of the art παρόμοιου τύπου συστήματα όπως το GeoSpark κ.α. Υπάρχει πλάνο λεπτομερούς σύγκρισης με τον ανταγωνισμό, σε θέματα όπως διαχείριση μνήμης, χρόνο εκτέλεσης, scalability και expendability.
Επιπλέον, σε διαφορετικό πλαίσιο, αναπτύσσονται νέοι μέθοδοι που επιταχύνουν το refinement step σε πράξεις μεταξύ πολυγώνων χρησιμοποιώντας τεχνικές συμπίεσης, προσέγγισης και bitwise λειτουργίες. Ο σκοπός είναι να μειωθεί το κόστος του refinement step, το οποίο είναι και το πιο ακριβό λόγω των γεωμετρικών πράξεων μεταξύ πολυγώνων.
Όσον αφορά στον 3ο άξονα της Δ1.2.3, που αναφέρεται στην ανάλυση δεδομένων που ακολουθούν το μοντέλο γράφου, έχει διεξαχθεί έρευνα για την ανάπτυξη ενός συστήματος που θα επιτρέπει την εξερεύνηση (exploration) δεδομένων γράφου μεγάλου όγκου. Οι γράφοι αποτελούν ένα πολύ φυσικό μοντέλο για την αναπαράσταση σχέσεων και εξαρτήσεων ανάμεσα σε οντότητες.
Μελετήθηκαν σύγχρονες τεχνικές βασισμένες σε μηχανική μάθηση για δεδομένα γράφου. Συγκεκριμένα μελετήθηκαν νευρωνικά δίκτυα για γραφήματα, Graph Neural Networks, ή GNNs για συντομία. Αξιολογήθηκαν διάφορες σύγχρονες αρχιτεκτονικές GNN ως προς τη δυνατότητα τους να χρησιμοποιηθούν στη εξερεύνηση γραφημάτων. Επίσης, υλοποιήθηκε μια τεχνική για collaborative flitering συστάσεις που βασίζεται σε GNNs. Τέλος, μελετήθηκαν προβλήματα σχετικά με τη δικαιοσύνη αυτών των μεθόδων στην περίπτωση που χειρίζονται δεδομένα με προστατευόμενα γνωρίσματα.
Στον ίδιο άξονα, στην κατεύθυνση της ανάλυσης και υλοποίησης αλγορίθμων υψηλής απόδοσης για την επεξεργασία μεγάλου όγκου δεδομένων που αναπαρίστανται με τη μορφή γραφημάτων, επικεντρωθήκαμε στο πρόβλημα υπολογισμού βασικών παραμέτρων της συνεκτικότητας γραφημάτων, οι οποίες αποτελούν τη βάση πολλών μεθόδων ανάλυσης δικτύων που χρησιμοποιούνται σε μια πληθώρα εφαρμογών.
Ένα σημαντικό πρόβλημα στη μελέτη της συνεκτικότητας ενός γραφήματος είναι ο υπολογισμός όλων των ελάχιστων τομών του (global minimum cuts), δηλαδή όλων των ελάχιστων συνόλων ακμών ενός γραφήματος, η διαγραφή των οποίων προκαλεί την αύξηση των συνεκτικών του συνιστωσών. Αν και το πλήθος των ελάχιστων τομών ενός μη κατευθυνόμενου γραφήματος μπορεί να είναι τετραγωνικό σε σχέση με το πλήθος των κόμβων του (οπότε ο υπολογισμός τους στην πράξη, για γραφήματα μεγάλης κλίμακας, είναι μάλλον ασύμφορος), στη βιβλιογραφία έχουν προταθεί διάφορες αποδοτικές δομές (όπως π.χ. το cactus γράφημα) που αναπαριστούν ουσιαστικά όλες τις ελάχιστες τομές και καταλαμβάνουν γραμμικό χώρο σε σχέση με το πλήθος των κόμβων. Επιπλέον, με την χρήση τέτοιων δομών μπορεί κανείς να υπολογίσει σύνολα κόμβων με σχετικά μεγάλο βαθμό συνεκτικότητας (k-edge-connected components), που δηλαδή παραμένουν συνδεδεμένοι μεταξύ τους παρά την όποια απώλεια (ενός περιορισμένου πλήθους) ακμών του γραφήματος. Στο πλαίσιο αυτό, υπήρξε δραστηριότητα ως προς τη σχεδίαση και υλοποίηση αποδοτικών αλγορίθμων (ντετερμινιστικών ή πιθανοκρατικών) για την κατασκευή τέτοιων δομών, ούτως ώστε να μελετηθεί η απόδοσή τους στην πράξη, σε γραφήματα μεγάλης κλίμακας. Ειδικά για ορισμένους μικρούς βαθμούς συνεκτικότητας (2 ή 3), εφόσον υπάρχουν αλγόριθμοι ασυμπτωτικά βέλτιστης πολυπλοκότητας, παρουσιάζει μεγάλο ενδιαφέρον η πειραματική ανάλυση και σύγκριση της σχετικής τους απόδοσης στην πράξη. Έχει πραγματοποιηθεί η συλλογή και μελέτη της σχετικής βιβλιογραφίας, όσο και η οργάνωση των βημάτων υλοποίησης των κατάλληλων αλγορίθμων.
Αντίστοιχες έννοιες ορίζονται και σε κατευθυνόμενα γραφήματα, όπου αντιμετωπίζονται ακόμα μεγαλύτερες προκλήσεις για τον υπολογισμό τους. Για παράδειγμα, το πλήθος των ελάχιστων τομών σε ένα κατευθυνόμενο γράφημα μπορεί να είναι εκθετικό σε σχέση με το πλήθος των ακμών του. Ωστόσο, στη σχετική βιβλιογραφία έχουν προταθεί τεχνικές που αναπαριστούν αυτές τις δομές με συμπαγή τρόπο, υπολογίζοντας ένα υποσύνολο σημαντικών τομών του γραφήματος. Στο πλαίσιο του προγράμματος, έχει πραγματοποιηθεί μια ενδελεχής μελέτη της σχετικής βιβλιογραφίας με επόμενο βήμα τη σχεδίαση και υλοποίηση μεθόδων υπολογισμού των σημαντικών τομών ενός κατευθυνόμενου γραφήματος αποδοτικά στην πράξη.
Τέλος, ο 4ος άξονας αφορά δεδομένα μεγάλης κλίμακας παραγόμενα από χρήστες (User-Generated data), όπως δεδομένα από αξιολογήσεις χρηστών, δημοσιεύσεις και άρθρα χρηστών σε κοινωνικά και άλλα δίκτυα, καθώς και σε ιστοσελίδες και άλλα μέσα. Η μέχρι στιγμής σχετική δραστηριότητα περιλαμβάνει έρευνα για την ανάπτυξη ενός συστήματος που θα επιτρέπει την ανίχνευση ακραίου κειμένου σε διαδικτυακά κοινωνικά δίκτυα και μέσα όπως το Twitter και το Reddit. Στο πλαίσιο της έρευνας σε αυτή την περιοχή ο κ. Τσαπάρας συμμετείχε στην οργάνωση του συμποσίου "Integrity 2022: 3rd Workshop on Integrity in Social Networks and Media" στα πλαίσια του συνεδρίου WSDM 2022: ACM Conference on Web Search and Data Mining.