| Περίληψη : | Με την ανάπτυξη της τεχνολογίας ο όγκος των πληροφοριών έχει αυξηθεί υπερβολικά. Για να απλοποιήσουμε την εμφάνιση των δεδομένων συχνά χρησιμοποιούμε τη μορφή γράφων. Οι γράφοι είναι ένα σύνολο από κόμβους και ακμές που συνθέτουν ένα περιβάλλον. Χαρακτηριστικά παραδείγματα μπορεί να είναι οι κοινωνικοί γράφοι (π.χ. Facebook, Twitter, LinkedIn κ.α.), οι γράφοι αναπαράστασης των αλυσίδων των πρωτεϊνών κτλ. Υπάρχει μια αυξανόμενη ανάγκη στη σημερινή εποχή να μπορούμε να αλληλεπιδρούμε με τους γράφους αυτούς και να εξάγουμε αποτελέσματα. Μια τέτοια αλληλεπίδραση είναι οι ερωτήσεις προσβασιμότητας που εξετάζουν αν δύο κόμβοι σε έναν γράφο είναι μεταξύ τους προσβάσιμοι. Η συγκεκριμένη περιοχή έχει μεγάλο ενδιαφέρον και υπάρχει πληθώρα ερευνών που εξετάζουν το πρόβλημα και προτείνουν λύσεις. Οι λύσεις αυτές είναι σε μορφή αλγορίθμων που δημιουργούν κάποιο είδος ευρετηρίου για να μπορούν έπειτα να εξετάζουν σε εύλογο χρονικό διάστημα αν ένας κόμβος έχει πρόσβαση σε έναν άλλον κόμβο. Τέτοιο παράδειγμα θα μπορούσε να είναι το δίκτυο πρότασης φίλων στο Facebook. Υπάρχουν πολλές διαφορετικές προτάσεις στο χώρο αυτόν που ποικίλουν ως προς το χρόνο απάντησης των ερωτήσεων προσβασιμότητας, το χώρο που καταλαμβάνουν τα ευρετήρια και το χρόνο κατασκευής των ευρετηρίων. Μια τέτοια λύση προτείνουμε και εμείς στη διπλωματική αυτή. Η λύση μας ανήκει στην κατηγορία των μεθόδων που δίνουν ετικέτες στους κόμβους του γράφου (online search methods) και χρησιμοποιώντας τις ετικέτες αυτές απαντάμε σε ε-ρωτήσεις προσβασιμότητας. Τη μέθοδο μας την ονομάσαμε FAROS επειδή για να δώσουμε ετικέτες στο γράφο διασχίζουμε με μια διάσχιση τα παιδιά κάθε κόμβου μια φορά και μια δεύτερη φορά με την αντίστροφη (reversed) σειρά. Επίσης προτείναμε και μια νέα μορφή διάσχισης που διασχίζεται ο γράφος από τα φύλλα του προς τις ρίζες του γράφου και μπορεί έτσι να δίνονται καλύτερες ετικέτες. Η μέθοδος μας πήρε το όνομα της και από ένα καινούργιο φίλτρο που δημιουργήσαμε που επιταχύνει τη διαδικασία απάντησης των ερωτήσεων προσβασιμότητας. Το φίλτρο αυτό βασίζεται στο θεμελιώδες θεώρημα της αριθμητικής και δίνει σε κάθε κόμβο που είναι φύλλο του γράφου μια επιπλέον ετικέτα που είναι ένας διαφορετικός κάθε φορά πρώτος αριθμός. Έπειτα, κάθε άλλος κόμβος παίρνει μια ετικέτα που προκύπτει από το γινόμενο των πρώτων αριθμών που συνθέτουν την ετικέτα των παιδιών του. Με τον τρόπο αυτό μπορούμε να εφαρμόσουμε το θεμελιώδες θεώρημα των πρώτων αριθμών και να εξετάσουμε εάν ένας κόμβος έχει πρόσβαση σε έναν άλλον με τη χρήση των ετικετών αυτών. Διεξήγαμε αρκετές πειραματικές μετρήσεις για να δούμε την αποτελεσματικότητα της μεθόδου FAROS και τα αποτελέσματα ήταν ικανοποιητικά. Στις μετρήσεις είδαμε ότι η μέθοδος μας απαντάει πολύ γρήγορα ερωτήσεις προσβασιμότητας αλλά δεν έχει εξίσου καλή κλιμάκωση σε πολύ μεγάλους γράφους το φίλτρο που εισήγαμε (πάνω από ένα εκατομμύριο κόμβους) επειδή δε μπορούμε να αποθηκεύσουμε στη μνήμη πάρα πολλούς πρώτους αριθμούς. Καταλήγοντας, υπάρχει χώρος για βελτίωση της μεθόδου μας ώστε να μπορέσει να κλιμακωθεί καλύτερα και να παράγει ακόμη καλύτερα αποτελέσματα.
With the fast advance of technology, the volume of data has dramatically increased. For us to better display our data we usually use graphs. A graph is a set of nodes and edges that create an environment. Characteristic examples are the social graphs (such as Facebook, Twitter etc.), graphs that represent the protein network, the road network and many more. There is a growing need to be able to use graphs as databases and extract results from their unique structure and representation. An example is to perform reachability queries in order to see if a node can reach another node in the graph. The area of reachability queries has recently attracted much attention and there is a lot of ongoing work in order to produce algorithms that answer reachability queries more efficiently. These algorithms produce an index that maps the graph and speeds up the process of answering reachability queries. There are many different approaches in the field based on the index they create on the graph such as path-based algorithms and online search algorithms. After studying many different solutions to the problem, we managed to create our own algorithm which we called FAROS that can answer reachability queries very fast. FAROS is an algorithm that belongs to the interval labeling category (because it gives labels to the nodes to be used as its index). The idea behind FAROS was based on another method that applies multiple labels on each node to later use them to answer reachability queries. FAROS first creates an acyclic graph out of the original graph and apply our index onto it. The index creates two sets of labels (one of which is our creation) that are made from depth-first searches on the acyclic graph in a reverse order so as for our index to be more efficient. After the index is made, we create some extra filters that speed up the answering of reachability queries, namely the topological filter and a new filter we created called Prime Numbers Filter. So the process of answering reachability queries is done by using comparisons between the different labels of the nodes we want to query. We have done thorough experiments on our method in comparison with the method we based on and the results were satisfying. We were able to achieve far greater times than the previous method in many different graphs both synthetic and real. The only disadvantage we have found is the exponential time of creation of our prime numbers filter when in-creasing the nodes of the input graph to the scale of millions. This was caused by the immense calculations that the filter requires. This is not an obstacle though if we want to improve the algorithm further in the future. To sum up, FAROS has been proven a promising algorithm that can produce very good results in answering reachability queries and can be compared to the other up-to-data algorithms.
|
|---|
Copyright © 2013 Βιβλιοθήκη Ο.Π.Α. Με την επιφύλαξη παντός δικαιώματος.