Our brain and nervous system is a vital organ to us, since it is from there our thoughts, personalities, and other mental capacities originate. Within this field of neuroscience a common method of study is to build and run large scale brain simulations where up to hundred thousand neurons are used to produce a model of a brain in three dimensional space. To find all neurites within a specific area is to perform a range query. A vast number of range queries are required when running brain simulations which makes it important that the data structure used to store the simulated neurons is efficient. This study evaluate three common data structures, also called spatial index; the R-tree, Quadtree and R*-tree (Rstar-tree). We test their performance for range queries with regards to execution time, incurred reads, build time, size of data and density of data. The data used is models of a typical neuron so that the characteristics of the data set is preserved. The results show that the R*-tree outperforms the other indices by being significantly more efficient compared to the others, with the R-tree having slightly worse performance than the Quadtree. The time it takes to build the index is to be almost identical for all implementations. / Vår hjärna och nervsystem är ett grundläggande organ för oss. Det är där ifrån våra tankar, personligheter och mentala kapaciteter kommer ifrån. Inom neurovetenskap är en vanlig forskningsmetod att köra storskaliga hjärnsimuleringar där hundratusentals neuroner används för att skapa en modell av hjärnan i 3D. För att hitta alla neuroner inom en viss area används en så kallad intervallfråga. En stor mängd intervallfrågor behövs för hjärnsimuleringar vilket gör det viktigt att datastrukturerna som används för detta är kostnadseffektiva. Denna studie har som mål att jämföra tre stycken vanliga datastrukturer som används för intervallfrågor. Dessa är R-tree, Quadtree och R*-tree. Deras prestanda testas för exekveringstid, antal läsningar, konstruktionstid, samt storlek och densitet på neuroner. För att skapa hjärnsimuleringen används en typisk neuron som standard sådant att dess karakteristiska egenskaper bevaras. Resultaten från studien visar att R*-tree hade den tydligt bästa prestandan för de givna kriterierna, och att Quadtree har en något bättre prestanda än R-tree. Tiden det tar att mata in neuronerna i datastrukturerna är i stort sett densamma.

Aquesta tesi està dedicada al disseny i a l'anàlisi d'estructures de dades multidimensionals, és a dir, estructures de dades que serveixen per emmagatzemar registres $K$-dimensionals que solen representar-se com a punts en l'espai $[0,1]^K$. Aquestes estructures tenen aplicacions en diverses àrees de la informàtica com poden ser els sistemes d'informació geogràfica, la robòtica, el processament d'imatges, la world wide web, el data mining, entre d'altres. Les estructures de dades multidimensionals també es poden utilitzar com a indexos d'estructures de dades que emmagatzemen, possiblement en memòria externa, dades més complexes que els punts.Les estructures de dades multidimensionals han d'oferir la possibilitat de realitzar operacions d'inserció i esborrat de claus dinàmicament, a més de permetre realitzar cerques anomenades associatives. Exemples d'aquest tipus de cerques són les cerques per rangs ortogonals (quins punts cauen dintre d'un hiper-rectangle donat?) i les cerques del veí més proper (quin és el punt més proper a un punt donat?).Podem dividir les contribucions d'aquesta tesi en dues parts: La primera part està relacionada amb el disseny d'estructures de dades per a punts multidimensionals. Inclou el disseny d'arbres binaris $K$-dimensionals al·leatoritzats (Randomized $K$-d trees), el d'arbres quaternaris al·leatoritzats (Randomized quad trees) i el d'arbres multidimensionals amb punters de referència (Fingered multidimensional trees).La segona part analitza el comportament de les estructures de dades multidimensionals. En particular, s'analitza el cost mitjà de les cerques parcials en arbres $K$-dimensionals relaxats, i el de les cerques per rang en diverses estructures de dades multidimensionals. Respecte al disseny d'estructures de dades multidimensionals, proposem algorismes al·leatoritzats d'inserció i esborrat de registres per als arbres $K$-dimensionals i per als arbres quaternaris. Aquests algorismes produeixen arbres aleatoris, independentment de l'ordre d'inserció dels registres i desprès de qualsevol seqüència d'insercions i esborrats. De fet, el comportament esperat de les estructures produïdes mitjançant els algorismes al·leatoritzats és independent de la distribució de les dades d'entrada, tot i conservant la simplicitat i la flexibilitat dels arbres $K$-dimensionals i quaternaris estàndard. Introduïm també els arbres multidimensionals amb punters de referència. Això permet que les estructures multidimensionals puguin aprofitar l'anomenada localitat de referència en cerques associatives altament correlacionades.I respecte de l'anàlisi d'estructures de dades multidimensionals, primer analitzem el cost esperat de las cerques parcials en els arbres $K$-dimensionals relaxats. Seguidament utilitzem aquest resultat com a base per a l'anàlisi de les cerques per rangs ortogonals, juntament amb arguments combinatoris i geomètrics. D'aquesta manera obtenim un estimat asimptòtic precís del cost de les cerques per rangs ortogonals en els arbres $K$-dimensionals aleatoris. Finalment, mostrem que les tècniques utilitzades es poden estendre fàcilment a d'altres estructures de dades i per tant proporcionem una anàlisi exacta del cost mitjà de cerques per rang en estructures de dades com són els arbres $K$-dimensionals estàndard, els arbres quaternaris, els tries quaternaris i els tries $K$-dimensionals. / Esta tesis está dedicada al diseño y al análisis de estructuras de datos multidimensionales; es decir, estructuras de datos específicas para almacenar registros $K$-dimensionales que suelen representarse como puntos en el espacio $[0,1]^K$. Estas estructuras de datos tienen aplicaciones en diversas áreas de la informática como son: los sistemas de información geográfica, la robótica, el procesamiento de imágenes, la world wide web o data mining, entre otras.Las estructuras de datos multidimensionales suelen utilizarse también como índices de estructuras que almacenan, posiblemente en memoria externa, datos complejos.Las estructuras de datos multidimensionales deben ofrecer la posibilidad de realizar operaciones de inserción y borrado de llaves de manera dinámica, pero además deben permitir realizar búsquedas asociativas en los registros almacenados. Ejemplos de búsquedas asociativas son las búsquedas por rangos ortogonales (¿qué puntos de la estructura de datos están dentro de un hiper-rectángulo dado?) y las búsquedas del vecino más cercano (¿cuál es el punto de la estructura de datos más cercano a un punto dado?).Las contribuciones de esta tesis se dividen en dos partes:La primera parte está dedicada al diseño de estructuras de datos para puntos multidimensionales, que incluye el diseño de los árboles binarios $K$-dimensionales aleatorios (Randomized $K$-d trees), el de los árboles cuaternarios aleatorios (Randomized quad trees), y el de los árboles multidimensionales con punteros de referencia (Fingered multidimensional trees).La segunda parte contiene contribuciones al análisis del comportamiento de las estructuras de datos para puntos multidimensionales. En particular, damos el análisis del costo promedio de las búsquedas parciales en los árboles $K$-dimensionales relajados y el de las búsquedas por rango en varias estructuras de datos multidimensionales.Con respecto al diseño de estructuras de datos multidimensionales, proponemos algoritmos aleatorios de inserción y borrado de registros para los árboles $K$-dimensionales y los árboles cuaternarios que producen árboles aleatorios independientemente del orden de inserción de los registros y después de cualquier secuencia de inserciones y borrados intercalados. De hecho, con la aleatorización garantizamos un buen rendimiento esperado de las estructuras de datos resultantes, que es independiente de la distribución de los datos de entrada, conservando la flexibilidad y la simplicidad de los árboles $K$-dimensionales y de los árboles cuaternarios estándar. También proponemos los árboles multidimensionales con punteros de referencia, una técnica que permite que las estructuras de datos multidimensionales exploten la localidad de referencia en búsquedas asociativas que se presentan altamente correlacionadas.Con respecto al análisis de estructuras de datos multidimensionales, comenzamos dando un análisis preciso del costo esperado de las búsquedas parciales en los árboles $K$-dimensionales relajados. A continuación, utilizamos este resultado como base para el análisis de las búsquedas por rangos ortogonales, combinándolo con argumentos combinatorios y geométricos. Como resultado obtenemos un estimado asintótico preciso del costo de las búsquedas por rango en los árboles $K$-dimensionales relajados. Finalmente, mostramos que las técnicas utilizadas pueden extenderse fácilmente a otras estructuras de datos y por tanto proporcionamos un análisis preciso del costo promedio de búsquedas por rango en estructuras de datos como los árboles $K$-dimensionales estándar, los árboles cuaternarios, los tries cuaternarios y los tries $K$-dimensionales. / This thesis is about the design and analysis of point multidimensional data structures: data structures that store $K$-dimensional keys which we may abstract as points in $[0,1]^K$. These data structures are present in many applications of geographical information systems, image processing or robotics, among others. They are also frequently used as indexes of more complex data structures, possibly stored in external memory.Point multidimensional data structures must have capabilities such as insertion, deletion and (exact) search of items, but in addition they must support the so called {em associative queries}. Examples of these queries are orthogonal range queries (which are the items that fall inside a given hyper-rectangle?) and nearest neighbour queries (which is the closest item to some given point?).The contributions of this thesis are two-fold:Contributions to the design of point multidimensional data structures: the design of randomized $K$-d trees, the design of randomized quad trees and the design of fingered multidimensional search trees;Contributions to the analysis of the performance of point multidimensional data structures: the average-case analysis of partial match queries in relaxed $K$-d trees and the average-case analysis of orthogonal range queries in various multidimensional data structures.Concerning the design of randomized point multidimensional data structures, we propose randomized insertion and deletion algorithms for $K$-d trees and quad trees that produce random $K$-d trees and quad trees independently of the order in which items are inserted into them and after any sequence of interleaved insertions and deletions. The use of randomization provides expected performance guarantees, irrespective of any assumption on the data distribution, while retaining the simplicity and flexibility of standard $K$-d trees and quad trees.Also related to the design of point multidimensional data structures is the proposal of fingered multidimensional search trees, a new technique that enhances point multidimensional data structures to exploit locality of reference in associative queries.With regards to performance analysis, we start by giving a precise analysis of the cost of partial matches in randomized $K$-d trees. We use these results as a building block in our analysis of orthogonal range queries, together with combinatorial and geometric arguments and we provide a tight asymptotic estimate of the cost of orthogonal range search in randomized $K$-d trees. We finally show that the techniques used apply easily to other data structures, so we can provide an analysis of the average cost of orthogonal range search in other data structures such as standard $K$-d trees, quad trees, quad tries, and $K$-d tries.

Τα κατανεμημένα δίκτυα κλίμακας Ίντερνετ και κυρίως τα δίκτυα ομοτίμων εταίρων, γνωστά και ως peer-to-peer (p2p), που αποτελούν το πιο αντιπροσωπευτικό παράδειγμά τους, προσελκύουν τα τελευταία χρόνια μεγάλο ενδιαφέρον από τους ερευνητές και τις επιχειρήσεις λόγω των ιδιόμορφων χαρακτηριστικών τους, όπως ο πλήρης αποκεντρωτικός χαρακτήρας, η αυτονομία των κόμβων, η ικανότητα κλιμάκωσης, κ.λπ. Αρχικά σχεδιασμένα να υποστηρίζουν εφαρμογές διαμοιρασμού αρχείων με βασική υπηρεσία την επεξεργασία απλών ερωτημάτων, σύντομα εξελίχτηκαν σε ένα καινούργιο μοντέλο κατανεμημένων συστημάτων, με μεγάλες και αυξανόμενες δυνατότητες για διαδικτυακές εφαρμογές, υποστηρίζοντας πολύπλοκες εφαρμογές διαμοιρασμού δομημένων και σημασιολογικά προσδιορισμένων δεδομένων. Η προσέγγισή μας στην περιοχή αυτή γίνεται προς δύο βασικές κατευθύνσεις: (α) την επεξεργασία πολύπλοκων ερωτημάτων και (β) την εκτίμηση των ανομοιομορφιών των διαφόρων κατανομών που συναντάμε στα δίκτυα αυτά (π.χ. φορτίου, προσφοράς ή κατανάλωσης ενός πόρου, τιμών των δεδομένων των κόμβων, κ.λπ.), που εκτός των άλλων αποτελεί ένα σημαντικό εργαλείο στην υποστήριξη πολύπλοκων ερωτημάτων. Συγκεκριμένα, ασχολούμαστε και επιλύουμε τρία βασικά ανοικτά προβλήματα. Το πρώτο ανοικτό πρόβλημα είναι η επεξεργασία ερωτημάτων εύρους τιμών σε ομότιμα συστήματα κατανεμημένου πίνακα κατακερματισμού, με ταυτόχρονη εξασφάλιση της εξισορρόπησης του φορτίου των κόμβων και της ανοχής σε σφάλματα. Προτείνουμε μια αρχιτεκτονική επικάλυψης, που ονομάζουμε Saturn, που εφαρμόζεται πάνω από ένα δίκτυο κατανεμημένου πίνακα κατακερματισμού. Η αρχιτεκτονική Saturn χρησιμοποιεί: (α) μια πρωτότυπη συνάρτηση κατακερματισμού που τοποθετεί διαδοχικές τιμές δεδομένων σε γειτονικούς κόμβους, για την αποδοτική επεξεργασία των ερωτημάτων εύρους τιμών και (β) την αντιγραφή, για την εξασφάλιση της εξισορρόπησης του φορτίου προσπελάσεων (κάθετη, καθοδηγούμενη από το φορτίο αντιγραφή) και της ανοχής σε σφάλματα (οριζόντια αντιγραφή). Μέσα από μια εκτεταμένη πειραματική αξιολόγηση του Saturn και σύγκριση με δύο βασικά δίκτυα κατανεμημένου πίνακα κατακερματισμού (Chord και OP-Chord) πιστοποιούμε την ανωτερότητα του Saturn να αντιμετωπίζει και τα τρία ζητήματα που θέσαμε, αλλά και την ικανότητά του να συντονίζει το βαθμό αντιγραφής ώστε να ανταλλάζει ανάμεσα στο κόστος αντιγραφής και στο βαθμό εξισορρόπησης του φορτίου. Το δεύτερο ανοικτό πρόβλημα που αντιμετωπίζουμε αφορά την έλλειψη κατάλληλων μετρικών που να εκφράζουν τις ανομοιομορφίες των διαφόρων κατανομών (όπως, για παράδειγμα, το βαθμό δικαιοσύνης μιας κατανομής φορτίου) σε κατανεμημένα δίκτυα κλίμακας Ίντερνετ και την μη αποτελεσματική ή δυναμική εκμετάλλευση μετρικών ανομοιομορφίας σε συνδυασμό με αλγορίθμους διόρθωσης (όπως ο αλγόριθμος εξισορρόπησης φορτίου). Το πρόβλημα είναι σημαντικό γιατί η εκτίμηση των κατανομών συντελεί στην ικανότητα κλιμάκωσης και στην επίδοση αυτών των δικτύων. Αρχικά, προτείνουμε τρεις μετρικές ανομοιομορφίας (το συντελεστή του Gini, τον δείκτη δικαιοσύνης και το συντελεστή διασποράς) μετά από μια αναλυτική αξιολόγηση μεταξύ γνωστών μετρικών εκτίμησης ανομοιομορφίας και στη συνέχεια, αναπτύσσουμε τεχνικές δειγματοληψίας (τρεις γνωστές τεχνικές και τρεις προτεινόμενες) για τη δυναμική εκτίμηση αυτών των μετρικών. Με εκτεταμένα πειράματα αξιολογούμε συγκριτικά τους προτεινόμενους αλγορίθμους εκτίμησης και τις τρεις μετρικές και επιδεικνύουμε πώς αυτές οι μετρικές και ειδικά, ο συντελεστής του Gini, μπορούν να χρησιμοποιηθούν εύκολα και δυναμικά από υψηλότερου επιπέδου αλγορίθμους, οι οποίοι μπορούν τώρα να ξέρουν πότε να επέμβουν για να διορθώσουν τις άδικες κατανομές. Το τρίτο και τελευταίο ανοικτό πρόβλημα αφορά την εκτίμηση του μεγέθους αυτοσύνδεσης μιας σχέσης όπου οι πλειάδες της είναι κατανεμημένες σε κόμβους δεδομένων που αποτελούν ένα ομότιμο δίκτυο επικάλυψης. Το μέγεθος αυτοσύνδεσης έχει χρησιμοποιηθεί εκτεταμένα σε συγκεντρωτικές βάσεις δεδομένων για τη βελτιστοποίηση ερωτημάτων και υποστηρίζουμε ότι μπορεί να χρησιμοποιηθεί και σε ένα πλήθος άλλων εφαρμογών, ειδικά στα ομότιμα δίκτυα (π.χ. συσταδοποίηση του Ιστού, αναζήτηση στον Ιστό, κ.λπ.). Η συνεισφορά μας περιλαμβάνει, αρχικά, τις προσαρμογές πέντε γνωστών συγκεντρωτικών τεχνικών εκτίμησης του μεγέθους αυτοσύνδεσης (συγκεκριμένα, σειριακή, ετεροδειγματοληπτική, προσαρμοστική και διεστιακή δειγματοληψία και δειγματοληψία με μέτρηση δείγματος) στο περιβάλλον ομοτίμων εταίρων και η ανάπτυξη μια πρωτότυπης τεχνικής εκτίμησης του μεγέθους αυτοσύνδεσης, βασισμένη στο συντελεστή του Gini. Με μαθηματική ανάλυση δείχνουμε ότι οι εκτιμήσεις του συντελεστή του Gini μπορούν να οδηγήσουν σε εκτιμήσεις των υποκείμενων κατανομών δεδομένων, όταν αυτά ακολουθούν το νόμο της δύναμης ή το νόμο του Zipf και αυτές, με τη σειρά τους, σε εκτιμήσεις του μεγέθους αυτοσύνδεσης των σχέσεων των δεδομένων. Μετά από αναλυτική πειραματική μελέτη και σύγκριση όλων των παραπάνω τεχνικών αποδεικνύουμε ότι η καινούργια τεχνική που προτείνουμε είναι πολύ αποτελεσματική ως προς την ακρίβεια, την πιστότητα και την απόδοση έναντι των άλλων πέντε μεθόδων. / The distributed, Internet-scale networks, and mainly, the peer-to-peer networks (p2p), that constitute their most representative example, recently attract a great interest from the researchers and the industry, due to their outstanding properties, such as full decentralization, autonomy of nodes, scalability, etc. Initially designed to support file sharing applications with simple lookup operations, they soon developed in a new model of distributed systems, with many and increasing possibilities for Internet applications, supporting complex applications of structured and semantically rich data. Our research to the area has two basic points of view: (a) complex query processing and (b) estimation of skewness in various distributions existing in these networks (e.g. load distribution, distribution of offer, or consumption of resources, data value distributions, etc), which, among others, it is an important tool to complex query processing support. Specifically, we deal with and solve three basic open problems. The first open problem is range query processing in p2p systems based on distributed hash tables (DHT), with simultaneous guarantees of access load balancing and fault tolerance. We propose an overlay DHT architecture, coined Saturn. Saturn uses a novel order-preserving hash function that places consecutive data values in successive nodes to provide efficient range query processing, and replication to guarantee access load balancing (vertical, load-driven replication) and fault tolerance (horizontal replication). With extensive experimentation, we evaluate and compare Saturn with two basic DHT networks (Chord and OP - Chord), and certify its superiority to cope with the three above requirements, but also its ability to tune the degree of replication to trade off replication costs for access load balancing. The second open problem that we face concerns the lack of appropriate metrics to express the degree of skewness of various distributions (for example, the fairness degree of load balancing) in p2p networks, and the inefficient and offline-only exploitation of metrics of skewness, which does not enable any cooperation with corrective algorithms (for example, load balancing algorithms). The problem is important because estimation of distribution fairness contributes to system scalability and efficiency. First, after a comprehensive study and evaluation of popular metrics of skewness, we propose three of them (the coefficient of Gini, the fairness index, and the coefficient of variation), and, then, we develop sampling techniques (three already known techniques, and three novel ones) to dynamically estimate these metrics. With extensive experimentation, which comparatively evaluates both the various proposed estimation algorithms and the three metrics we propose, we show how these three metrics, and especially, the coefficient of Gini, can be easily utilized online by higher-level algorithms, which can now know when to best intervene to correct unfairness. The third and last open problem concerns self-join size estimation of a relation whose tuples are distributed over data nodes which comprise an overlay network. Self-join size has been extensively used in centralized databases for query optimization purposes, and we support that it can also be used in various other applications, specifically in p2p networks (e.g. web clustering, web searching, etc). Our contribution first includes the adaptations of five well-known self-join size estimation, centralized techniques (specifically, sequential sampling, cross-sampling, adaptive and bifocal sampling, and sample-count) to the p2p environment and a novel estimation technique which is based on the Gini coefficient. With mathematical analysis we show that, the estimates of the Gini coefficient can lead to estimates of the degree of skewness of the underlying data distribution, when these follow the power, or Zipf’s law, and these estimates can lead to self-join size estimates of those data relations. With extensive experimental study and comparison of all above techniques, we prove that the proposed technique is very efficient in terms of accuracy, precision, and cost of estimation against the other five methods.