Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark
Το R-δέντρο είναι μια πολυδιάστατη δομή δεδομένων που παρουσιάστηκε από τον Guttman, Antonin το 1984, πρόκειται για μια δυναμική δομή δεικτοδότησης, είναι ένα ισοζυγισμένο δέντρο παρόμοιο με το B+ -δέντρο και χρησιμοποιείται για μεθόδους χωρικής αναζήτησης. Το συγκεκριμένο δέντρο εκφράζει κάθε κόμβο...
Κύριος συγγραφέας: | |
---|---|
Άλλοι συγγραφείς: | |
Γλώσσα: | Greek |
Έκδοση: |
2023
|
Θέματα: | |
Διαθέσιμο Online: | https://hdl.handle.net/10889/24594 |
id |
nemertes-10889-24594 |
---|---|
record_format |
dspace |
spelling |
nemertes-10889-245942023-03-01T04:38:00Z Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark Development of an efficient data structure in Apache Spark enviroment Κωνσταντόπουλος, Νικόλαος Konstantopoulos, Nikolaos R-δέντρο Πολυδιάστατη δομή δεδομένων Ορθογώνιο ελαχίστου ορίου Κορυφογραμμή Μεγάλα δεδομένα Κιβωτιοποίηση Συστάδες R-tree Multidimensional data structures Minimum bounding rectangle Distributed Skyline Big data Clusters Apache Spark Docker Το R-δέντρο είναι μια πολυδιάστατη δομή δεδομένων που παρουσιάστηκε από τον Guttman, Antonin το 1984, πρόκειται για μια δυναμική δομή δεικτοδότησης, είναι ένα ισοζυγισμένο δέντρο παρόμοιο με το B+ -δέντρο και χρησιμοποιείται για μεθόδους χωρικής αναζήτησης. Το συγκεκριμένο δέντρο εκφράζει κάθε κόμβο του από μια περιοχή, η οποία ορίζεται από ένα ορθογώνιο ελαχίστου ορίου εκτός απο τα φύλλα του, που περιέχουν τις πλειάδες των σημείων που βρίσκονται εντός του αντίστοιχου ορίου. Στην παρούσα εργασία υλοποιείται η συγκεκριμένη πολυδιάστατη δομή, μαζί με τις βασικές λειτουργίες της, την κατασκευή, την εισαγωγή και την αναζήτηση εύρους, μαζί με την κατασκευή κορυφογραμμής και αναζήτη- σης εύρους εντός της κορυφογραμμής. Η υλοποίηση έγινε για κεντρικοποιημένο περιβάλλον αλλά και για κατανεμημένο, στο περιβάλλον της Apache Spark. Στόχος της εργασίας είναι να υποστηρίζονται όλες οι λειτουργίες του δέντρου στο περιβάλλον της Spark, να συγκρίνει τις δύο υλοποιήσεις και τελικά να εξάγει συμπεράσματα για τις προοπτικές που υπάρχουν για αξιοποίηση της κατανεμημένης υλοποίησης σε μεγάλα δεδομένα. Τέλος, αξιοποιείται και η τεχνολογία της κιβωτιοποίησης μέσω του λογισμικού εργαλείου Docker ώστε να υπάρχει μια εικονική συστάδα και να εξασφαλίζεται η αξιοπιστία της υλοποίησης και η δυνατότητα της για επέκταση σε πραγματική συστάδα υπολογιστών. The R-tree is a multidimensional data structure that was introduced from Guttman Antonin in 1984. It is a dynamic indexing structure, also it is a balanced tree similar to B + -tree and used in spatial access methods. The particular tree represents each node from a region that is defined from a Minimum Bounding Rectangle (MBR), except from the leafs of the tree, the leafs contain the tuples of the points that covered from the corresponding region limit.In this diploma thesis, the specific multidimensional structure is implemented, together with it’s basic functions, the creation, the insertion and the range query, along side with the creation of the skyline and the range query inside the skyline. The implementation have been developed for centralized environment and also for distributed, in the Apache Spark enviroment. This thesis aims to implement and support all the functionalities of R-tree in the Spark enviroment, compare both implementations and draw conclusions about the use of the distirbuted implementation on Big Data. Lastly, this thesis used the containerization technology via the Docker software tool, to implemed a virtual cluster in order to ensure the reliability of the implementation and the potential to be developed in a real cluster. 2023-02-28T06:49:30Z 2023-02-28T06:49:30Z 2023-02-20 https://hdl.handle.net/10889/24594 el Attribution 3.0 United States http://creativecommons.org/licenses/by/3.0/us/ application/pdf application/octet-stream |
institution |
UPatras |
collection |
Nemertes |
language |
Greek |
topic |
R-δέντρο Πολυδιάστατη δομή δεδομένων Ορθογώνιο ελαχίστου ορίου Κορυφογραμμή Μεγάλα δεδομένα Κιβωτιοποίηση Συστάδες R-tree Multidimensional data structures Minimum bounding rectangle Distributed Skyline Big data Clusters Apache Spark Docker |
spellingShingle |
R-δέντρο Πολυδιάστατη δομή δεδομένων Ορθογώνιο ελαχίστου ορίου Κορυφογραμμή Μεγάλα δεδομένα Κιβωτιοποίηση Συστάδες R-tree Multidimensional data structures Minimum bounding rectangle Distributed Skyline Big data Clusters Apache Spark Docker Κωνσταντόπουλος, Νικόλαος Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
description |
Το R-δέντρο είναι μια πολυδιάστατη δομή δεδομένων που παρουσιάστηκε από τον Guttman,
Antonin το 1984, πρόκειται για μια δυναμική δομή δεικτοδότησης, είναι ένα ισοζυγισμένο
δέντρο παρόμοιο με το B+ -δέντρο και χρησιμοποιείται για μεθόδους χωρικής αναζήτησης.
Το συγκεκριμένο δέντρο εκφράζει κάθε κόμβο του από μια περιοχή, η οποία ορίζεται από
ένα ορθογώνιο ελαχίστου ορίου εκτός απο τα φύλλα του, που περιέχουν τις πλειάδες των
σημείων που βρίσκονται εντός του αντίστοιχου ορίου. Στην παρούσα εργασία υλοποιείται η
συγκεκριμένη πολυδιάστατη δομή, μαζί με τις βασικές λειτουργίες της, την κατασκευή, την
εισαγωγή και την αναζήτηση εύρους, μαζί με την κατασκευή κορυφογραμμής και αναζήτη-
σης εύρους εντός της κορυφογραμμής. Η υλοποίηση έγινε για κεντρικοποιημένο περιβάλλον
αλλά και για κατανεμημένο, στο περιβάλλον της Apache Spark. Στόχος της εργασίας είναι
να υποστηρίζονται όλες οι λειτουργίες του δέντρου στο περιβάλλον της Spark, να συγκρίνει
τις δύο υλοποιήσεις και τελικά να εξάγει συμπεράσματα για τις προοπτικές που υπάρχουν για
αξιοποίηση της κατανεμημένης υλοποίησης σε μεγάλα δεδομένα. Τέλος, αξιοποιείται και η
τεχνολογία της κιβωτιοποίησης μέσω του λογισμικού εργαλείου Docker ώστε να υπάρχει μια
εικονική συστάδα και να εξασφαλίζεται η αξιοπιστία της υλοποίησης και η δυνατότητα της για
επέκταση σε πραγματική συστάδα υπολογιστών. |
author2 |
Konstantopoulos, Nikolaos |
author_facet |
Konstantopoulos, Nikolaos Κωνσταντόπουλος, Νικόλαος |
author |
Κωνσταντόπουλος, Νικόλαος |
author_sort |
Κωνσταντόπουλος, Νικόλαος |
title |
Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
title_short |
Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
title_full |
Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
title_fullStr |
Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
title_full_unstemmed |
Υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον Apache Spark |
title_sort |
υλοποίηση αποδοτικών δομών δεδομένων σε περιβάλλον apache spark |
publishDate |
2023 |
url |
https://hdl.handle.net/10889/24594 |
work_keys_str_mv |
AT kōnstantopoulosnikolaos ylopoiēsēapodotikōndomōndedomenōnseperiballonapachespark AT kōnstantopoulosnikolaos developmentofanefficientdatastructureinapachesparkenviroment |
_version_ |
1771297304695799808 |