Μελέτη των αλγορίθμων ταξινόμησης KD-tree και Box assisted και εφαρμογή τους σε Σχεσιακά Μοντέλα Βάσεων Δεδομένων

Abstract

Σκοπός αυτής της πτυχιακής εργασίας είναι η υλοποίηση των αλγορίθμων συσχέτισης διαστάσεων KD-tree και Box assisted οι οποίοι θα αντλούν δεδομένα (Ν-διάστατα σημεία) από Βάσεις Δεδομένων (Β.Δ.). Δηλαδή η κατασκευή μιας εφαρμογής σε προγραμματιστικό περιβάλλον (χρησιμοποιώντας τη Borland C++ 6.0 Builder), συνδεδεμένη με μια Β.Δ. (Microsoft SQL Server 2000), που θα διαβάζει τα δεδομένα αυτά και θα τα συσχετίζει, στηριζόμενη στον εκάστοτε αλγόριθμο. Αρχικά δίδεται η δυνατότητα στο χρήστη να δημιουργεί, να εισάγει ή να διαμορφώνει πίνακες δεδομένων, που θα χρησιμοποιηθούν αργότερα από τους δυο αλγορίθμους. Έπειτα, ο χρήστης καλείται να επιλέξει ποια μέθοδο θα χρησιμοποιήσει. Η κάθε μέθοδος αποτελείται από δυο μέρη, την ταξινόμηση και την αναζήτηση. Η ταξινόμηση είναι μια αρκετά χρονοβόρα διαδικασία, η οποία κατασκευάζει ένα πίνακα συσχέτισης των σημείων της B.Δ. Μετά την ολοκλήρωση της ταξινόμησης, ο χρήστης μπορεί να εισάγει παραμέτρους στην αναζήτηση και να λάβει ταχύτατα αποτελέσματα. Η διαδικασία υλοποίησης αυτής της πτυχιακής εργασίας μπορεί να χωριστεί στα εξής τμήματα: • Συλλογή απαραίτητων πληροφοριών. • Υλοποίηση του προγράμματος. • Συγγραφή του παρόντος βιβλίου.

The purpose of this thesis is the implementation of the KD-tree and Box assisted correlation dimension algorithms that can derive N-Dimensional data from Databases and the construction of an application using the Borland C++ Builder, connected to a D.B. (Microsoft SQL Server 2000), that will read data and correlate them, using these algorithms. At first, the user has the option to create, input or change data tables, that will be used later by the two algorithms. Afterwards, the user will have to choose the method he is going to use. Each method consists of two parts, sorting and searching. Sorting is quite a time-consuming process that constructs a correlation table of points in the Database. After sorting is completed, the user can input his parameters in the search, and receive fast results. The productive process of this thesis can be divided in the following parts: • Collection of the necessary information • Implementation of the application • Writing of this paper.