Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Generating geospatial heatmaps: Optimizing point-region quadtrees for window queries
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Generering av geospatiala värmekartor : Optimering av punktområdes-fyrträd för fönsterförfrågningar (Swedish)
Abstract [en]

This study aims to investigate and identify how to effectively generate blurred geospatial heatmaps for use in geo-spatial map engines. We focus on how to store the points in a way that facilitates efficient window querying, with support for zoom-level handling. We decide on primarily using a Morton-ordered variant of the point-region quadtree, which we name a HeatMap Quadtree (HMQ). The nodes of the HMQ each have access to the points they contain, through storing the number of points and the lower bound of where to look at in the input point set, which we also store in Morton order. The HMQ also has the functionality to allow for window querying at different levels of detail. We parallelize the generation of the HMQ as well as the Gaussian blurring of the raster resulting from the window query using CUDA, and compare this implementation with that of two naive solutions as well as a linear point-region quadtree. In conclusion we find that the HMQ provides a significant improvement in window querying time, at the cost of additional construction time.

Abstract [sv]

Denna studie avser att undersöka och identifiera hur man effektivt kan generera Gaussiskt oskarpa geospatiala värmekartor för användning i geospatiala kartmotorer. Vi fokuserar på hur man ska lagra punkterna på ett sätt som underlättar effektiv `window querying', med stöd för zoomnivå-hantering. Vi bestämmer oss för att huvudsakligen använda oss av en Morton-ordnad variant av ett `point-region quadtree', vilket vi döper till `HeatMap Quadtree' (HMQ). Noderna i vårt HMQ har alla tillgång till punkterna dom innehåller, genom att lagra antalet punkter och den lägre gränsen för var man ska leta efter punkterna i den ursprunliga punktlistan, som vi också lagrar i Morton-ordning. Vårt HMQ har också funktionaliteten att tillåta `window querying' på olika detaljnivåer. Vi parallelliserar genererandet av vårt HMQ samt uträknandet av den Gaussiska oskärpan på rastret som resulterar från vår `window query' med hjälp av CUDA, och jämför denna implementation med två naiva lösningar samt ett linjärt `point-region quadtree'. Vår slutsats är att vårt HMQ ger en signifikant förbättring i `window query'-tid, till en kostnad av extra konstruktionstid. 

Place, publisher, year, edition, pages
2015.
Keyword [en]
geospatial, geographic, heatmap, point region, point-region, quadtree, window query
Keyword [sv]
värmekarta, fönsterförfrågning, geografisk
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-172815OAI: oai:DiVA.org:kth-172815DiVA: diva2:849697
External cooperation
Carmenta AB
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2015-09-10 Created: 2015-08-30 Last updated: 2015-09-10Bibliographically approved

Open Access in DiVA

fulltext(1682 kB)175 downloads
File information
File name FULLTEXT01.pdfFile size 1682 kBChecksum SHA-512
aeba83e644984f7ba0817186bd68b51bc3fe3aab35c741f722cdfde2ce28978aa157e6ac9a3b392650ce47c2be1eb032b81e2cf192ad084870aa78cdbc45dd3a
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 175 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: 1212 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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