Ανάπτυξη Ευρετηρίων Για Σύνθετα Δεδομένα

Abstract

Ο στόχος της διπλωματικής αυτής εργασίας είναι η ανάπτυξη ενός ευρετηρίου το οποίο θα είναι αποδοτικό για χρήση σε σύνθετα δεδομένα και συγκεκριμένα για τιμές-σύνολα, δηλαδή για δοσοληψίες, η κάθε μία από τις οποίες αποτελείται από ένα σύνολο (set) από ίδιου τύπου δεδομένα. Το ευρετήριο που αναπτύσσουμε μας ενδιαφέρει να μπορεί να απαντάει σε συγκεκριμένα ερωτήματα, τα οποία είναι subset queries, equality queries και superset queries. Έτσι, για την ανάπτυξη του ευρετηρίου μας χρησιμοποιούμε το πιο αποδοτικό από τα ήδη υπάρχοντα ευρετήρια, το inverted file, το οποίο συνδυάζουμε με το γνωστό Β-Δέντρο, δημιουργώντας έτσι το ordered inverted file. Ο στόχος που επιθυμούμε να πετύχουμε με την ανάπτυξη του ordered inverted file είναι να κάνουμε πιο αποδοτική την αποτίμηση των ερωτημάτων, αποκτώντας μέσω του Β-Δέντρου πρόσβαση και σε άλλα σημεία των λιστών του inverted file εκτός από την αρχή τους. Αναπτύσσεται επίσης κώδικας σε C++ ο οποίος υλοποιεί την κατασκευή του ordered inverted file καθώς και την αποτίμηση ερωτημάτων με χρήση αυτού, και ο οποίος χρησιμοποιείται για τη διενέργεια πειραμάτων που συγκρίνουν την απόδοση του ordered inverted file με αυτή του απλού inverted file. Η υλοποίησή μας αποθηκεύει τα Β-Δέντρα στο σκληρό δίσκο ενώ για το inverted file τμήμα του ευρετηρίου προσφέρει την επιλογή να αποθηκευτεί είτε στο δίσκο είτε στην κύρια μνήμη. Τα πειράματα που έγιναν με χρήση του κώδικα αυτού δείχνουν ότι σε γενικές γραμμές το ordered inverted file είναι πιο αποδοτικό από το inverted file, ειδικά για την αποτίμηση ερωτημάτων equality και superset. Για την αποτίμηση subset queries κατά την οποία η απόδοση του ordered inverted file δε φάνηκε να υπερτερεί σημαντικά αυτής του απλού inverted file προτείνονται επιπλέον μέθοδοι βελτίωσης, οι οποίες όμως δε συμπεριλαμβάνονται στην υλοποίηση.