The design of multi-dimensional access methods is difficult as compared to those of one-dimensional case because of no total ordering that preserves spatial locality. One way is to look for the total order that preserves spatial proximity at least to some extent. A space-filling curve is a continuous path which passes through every point in a space once so giving a one-to-one correspondence between the coordinates of the points and the 1D-sequence numbers of points on the curve. The Hilbert curve is a famous space filling curve, since it has been shown to have strong locality preserving properties; that is, it is the best space-filling curve in minimizing the number of clusters. Hence, it has been extensively used to maintain spatial locality of multidimensional data in a wide variety of applications. A window query is an important query operation in spatial (image) databases. Given a Hilbert curve, a window query reports its corresponding orders without the need to decode all the points inside this window into the corresponding Hilbert orders. Chung et al. have proposed an algorithm for decomposing a window into the corresponding Hilbert orders. However, the Hilbert curve requires that the region is of size 2^k x 2^k, where k∈N. The intuitive method such as Chung et al.¡¦s algorithm is to directly use Hilbert curves in the decomposed areas and then connect them. They must generate a sequence of the scanned quadrants additionally before encoding and decoding the Hilbert order of one pixel and scan this sequence one time while encoding and decoding one pixel. In this dissertation, on the design of methods for window queries on a Hilbert curve, we propose an efficient algorithm, named as Quad-Splitting, for decomposing a window into the corresponding Hilbert orders on a Hilbert curve without individual sorting and merging steps. The proposed algorithm does not perform individual sorting and merging steps which are needed in Chung et al.¡¦s algorithm. From our experimental results, we show that the Quad-Splitting algorithm outperforms Chung et al.¡¦s algorithm. On the design of the methods for generating the Hilbert curve of an arbitrary-sized image, we propose approximately even partition approach to generate a pseudo Hilbert curve of an arbitrary-sized image. From our experimental results, we show that our proposed pseudo Hilbert curve preserves the similar strong locality property to the Hilbert curve. On the design of the methods for coding Hilbert curve of an arbitrary-sized image, we propose encoding and decoding algorithms. From our experimental results, we show that our encoding and decoding algorithms outperform the Chung et al.¡¦s algorithms.

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. / 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.