The brain is the most complex organ in the human body, and there are many reasons to study it. One way of studying the brain is through digital simulations. Such simulations typically require large amounts of data on the 3dimensional structure of individual neurons to be stored and processed efficiently. Commonly, such data is stored using data structures for spatial indexing such as R-trees. A typical operation within neuroscience which needs to make use of these data structures is the range query: a search for all elements within a given subvolume of the model. Since these queries are common, it is important they can be made efficiently. The purpose of this study is to compare a selection of construction methods (repeated R*-tree insertion, one-dimensional sorting packing, Sort-Tile-Recursive (STR) packing, Adaptive STR packing, Hilbert/Z-order/Peano curve packing, and binary splitting packing) for R-trees with respect to their performance in terms of building time, query page reads and query execution time. With reconstructions of neurons from the human brain, ten datasets were generated with densities ranging from 5,000 to 50,000 neurons/mm3 in a 300 µm 600 µm 300 µm volume. Range queries were then run on the R-trees constructed from these datasets. The results show that the lowest query times were achieved using STR packing and Adaptive STR packing. The best performing construction techniques in terms of build time were Peano and Z-order curve packing. / Hjärnan är kroppens mest komplicerade organ och det finns många anledningar att studera den. Ett sätt att studera hjärnan är genom datorsimuleringar. Sådana datorsimuleringar kräver en stor mängd tredimensionell neurondata som behöver lagras och behandlas effektivt. R-träd är en vanlig datastruktur för att behandla sådan data, och en vanlig operation man inom neurovetenskapen vill genomföra är sökningar efter element i en given delvolym av modellen man arbetar med. Det är därför viktigt att dessa operationer kan genomföras effektivt. Syftet med denna studie är att jämföra ett urval av konstruktionstekniker (upprepad R*-trädsinsättning, endimensionell sorteringspackning, STR-packning, adaptiv STR-packning, Hilbert-packning, Zordningspackning, Peano-kurvpackning samt binär klyvpackning) för R-träd med avseende på prestanda i konstruktionstid, antal sidinläsningar och exekveringstid för sökningar. Tio datamängder genererades med nervcellsdensiteter mellan 5,000 och 50,000 celler/mm3 i en volym på 300 µm 600 µm 300 µm. Dessa användes sedan för konstruktion av olika R-träd i vilka en sekvens av delvolymssökningar gjordes. Resultaten visar att den lägsta söktiden erhölls med R-träd konstruerade genom STR-packning och adaptiv STR-packning, medan konstruktionstiden var som lägst för packning med Peanokurvan och Z-ordningskurvan.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-279974 |
| Date | January 2020 |
| Creators | Elmarsson, Axel, Grundberg, Johan |
| 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 ; 2020:338 |
Page generated in 0.0014 seconds