Κατανεμημένη Επεξεργασία Ερωτημάτων Κυριαρχίας
Creators: name: Καραγιαννίδης, Δημήτριος Πέτρου
Publisher: name: Aristotle University of Thessaloniki
Year: 2019
Subjects: Κατανεμημένη Επεξεργασία
Ερωτήματα Κυριαρχίας
Πρόβλημα Skyline
Distributed Processing
Dominance-Based Queries
Skyline Problem

description: Τα τελευταία χρόνια μεγάλο μέρος της επιστημονικής κοινότητας ασχολείται με το πρόβλημα της έκδοσης ολοκληρωμένων αποτελεσμάτων σε οποιαδήποτε ερώτηση του χρήστη. Σε μια αναζήτηση του χρήστη ενδέχεται να υπάρχουν πολλά και διαφορετικά κριτήρια, με αποτέλεσμα να μην είναι τις περισσότερες φορές ευδιάκριτη η σειρά ή ο συνδυασμός των προτιμήσεων των κριτηρίων που επιθυμεί ο κάθε χρήστης. Έτσι, δημιουργείται η ανάγκη χρήσης μεθόδων που βοηθούν στην καλύτερη κατανομή και επεξεργασία των ερωτημάτων αυτών δίνοντας μια πιο σφαιρική απάντηση. Με τη χρήση των ερωτημάτων προτίμησης και τον αλγόριθμο Skyline επιτυγχάνεται ο εντοπισμός των καλύτερων αποτελεσμάτων μέσα από ένα μεγάλο σύνολο δεδομένων, καλύπτοντας κάθε πιθανό σενάριο. Ο αλγόριθμος αυτός βρίσκει χρήση σε μια πληθώρα εφαρμογών για τη λήψη αποφάσεων. Σήμερα, υπάρχουν διάφορες εφαρμογές που είναι υπεύθυνες για τη λήψη αποφάσεων για την έκδοση αποτελεσμάτων μέσω ενός συνόλου δεδομένων, λαμβάνοντας υπόψη πολλά και διαφορετικά κριτήρια. Η λύση σε αυτές τις εφαρμογές είναι ο υπολογισμός του Skyline. Ο υπολογισμός Skyline βασίζεται στην σύγκρισης δύο διαφορετικών σημείων για να διαπιστωθεί ποιο σημείο κυριαρχεί. Ένα σημείο κυριαρχεί ενός άλλου σημείο όταν σε κάθε διάσταση είναι ίσο ή μικρότερο και υποχρεωτικά σε μία διάσταση τουλάχιστον είναι μικρότερο από το άλλο σημείο. Επιπλέον, ένα σημείο μπορεί να είναι μέρος των σημείων Skyline, αν χαρακτηρίζεται ως ασύγκριτο, πράγμα που σημαίνει ότι είναι μεγαλύτερο σε μια διάσταση και μικρότερο σε μια άλλη. Το κύριο πρόβλημα είναι ότι το μέγεθος των δεδομένων δεν ταιριάζει στη δευτερεύουσα μνήμη (Ram). Έτσι, ο χρήστης είναι μερικές φορές ανίκανος να ολοκληρώσει κάποια ερωτήματα λόγω αυτού του περιορισμού, επειδή τα σημεία που ο αλγόριθμος χρειάζεται να ελέγξει είναι πάρα πολλά και καθυστερεί πολύ για να φτάσει στο σημείο ταυτοποίησης σημείων ενδιαφέροντος. Για να υπολογίσουμε το σημείο που ανήκει στο Skyline, σε αυτήν την διπλώματικη, εστιάζουμε σε αλγόριθμους βάσης χωρίς index όπως Block Nested Loop (BNL), Sort-Φίλτρο-Skyline (SFS), Linear Elimination Sort for Skyline (LESS) Αλγόριθμοι Sort and Limit Skyline(SaLSa)
description: Over the past few years quite a few members of the scientific community have been dealing with the problem of giving the best results in every given user search. In such a search there may be various diverse criteria though, so most of the time the order or the combination of user preferences of the criteria that every user desires is not distinct. For this reason, there is a need to use methods that help to better allocate and process these inquiries, giving a more comprehensive answer to them. By using preference inquiries and the Skyline algorithm, one can manage to locate the best results through a large set of data thus covering each possible scenario. Finally, this algorithm can be quite useful to a wide variety of decision-making applications. Nowadays, there are several applications which are in charge of making decisions in order to issue results through a set of data, taking into account many different criteria. The solution to these applications is the computation of Skyline. The Skyline computation is based on the comparison condition of two different points to see which point dominate which. One point dominates another point when in every dimension it is equal or smaller and obligingly in one dimension at least it is smaller than the other point. Furthermore, one point can be a part of Skyline points, if it is characterized as incomparable, which means that it is greater in one dimension and smaller in another. The main problem is that the size of the data does not fit in the secondary memory (Ram). So the user is sometimes unable to complete some queries due to this limitation, because the points, that the algorithm needs to control, are too many and it lags long to get to the point of identifying points of interest .To compute the point that belongs in Skyline, in this research, we focus on the non-indexed base algorithms, like Block Nested Loop(BNL), Sort-Filter-Skyline (SFS), Linear Elimination Sort for Skyline(LESS) and Sort and Limit Skyline algorithm (SaLSa)