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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-229767 |
| Date | January 2018 |
| Creators | Norelius, Jenny, Tacchi, Antonello |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2018:280 |
Page generated in 0.0023 seconds