Evaluating Reachability Queries over Path Collections Full text

Panagiotis Bouros, Spiros Skiadopoulos, Theodore Dalamagas, Dimitris Sacharidis, Timos Sellis
SSDBM 2009: 398-416
2009
Συνέδριο/Workshop
Περίληψη. Πλήθος εφαρμογών σε τομείς όπως η βιοχημεία και τα γεωγραφικά πληροφοριακά συστήματα (GIS), καλούνται να διαχειριστούν και να απαντήσουν ερωτήματα σε μεγάλες συλλογές από ακολουθιακά δεδομένα, αποθηκεύμενα ως συλλογές μονοπατιών. Υπάρχει μία πλειάδα ερωτημάτων που μπορούν αποτιμηθούν σε τέτοιου είδους δεδομένα. Η παρούσα δουλειά επικεντρώνεται στα ερωτήματα προσέγγισης: δεδομένης μίας συλλογής μονοπατιών και δύο κόμβων s, t, θέλουμε να διαπιστώσουμε αν υπάρχει μονοπάτι από το s στο t και να αναγνωρίσουμε το μονοπάτι αυτό. Για την αποτίμηση των ερωτημάτων αυτών προτείνουμε τον αλγόριθμο path-first search που αντιμετωπίζει τα μονοπάτια ως πολίτες πρώτης τάξης. Για την περαιτέρω βελτίωση των επιδόσεων των μεθόδων μας, εισαγάγουμε δύο ευρετήρια που αναπαριστούν την πληροφορία πρόσβασης μεταξύ των κόμβων στα μονοπάτια. Επιπλέον, παρουσιάζουμε μεθόδους για την ενημέρωση μιας συλλογής μονοπατιών και των ευρετηρίων της. Τέλος, διεξάγουμε μία εκτενή πειραματική μελέτη που επιβεβαιώνει τα πλεονεκτήματα των μεθόδων μας.