kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comparison of different R-tree construction techniques for range queries on neuromorphological data
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2020 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförelse av R-trädskonstruktions tekniker för sökningar i neuronal morfologidata (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2020. , p. 60
Series
TRITA-EECS-EX ; 2020:338
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:kth:diva-279974OAI: oai:DiVA.org:kth-279974DiVA, id: diva2:1463267
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2020-09-01 Created: 2020-09-01 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

fulltext(2993 kB)2716 downloads
File information
File name FULLTEXT01.pdfFile size 2993 kBChecksum SHA-512
d6b9f2cbac520f71bf7c6edd5b170efb3814958a540d03866b92efe280a164c6d0696bebb565246177e34a80f8ef6f24b5b77ccbedc078304d0577186625d473
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 2722 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 757 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf