Vi utbildar för framtiden och skapar samhällsnytta genom vår forskning som levandegörs i nära samarbete med näringslivet. Vi bedriver forskning inom computer science, datateknik, software engineering och interaktionsdesign - från grundforskning till direkta tillämpningar. Institutionen har en stark internationell prägel och är delad mellan Chalmers och Göteborgs universitet.
We are engaged in research and education across the full spectrum of computer science, computer engineering, software engineering, and interaction design, from foundations to applications. We educate for the future, conduct research with high international visibility, and create societal benefits through close cooperation with businesses and industry. The department is joint between Chalmers and the University of Gothenburg.
(2019) Aasa, Jakob; Lundberg, Marcus; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Assarsson, Ulf; Stintorn, Erik
Spatial indexes are data structures which store objects in the form of points or geometry in two or more dimensions in such a way that subsets can be queried with high performance. However, good query performance is no guarantee for a corresponding update performance. There is currently little research of spatial indexing for non-point geometry which receive frequent updates. This thesis studies and compares diﬀerent spatial indexes for this kind of data. The evaluated data structures are the simple quadtree, the loose quadtree, theloose-linear quadtree, and the R*-tree. A dynamic array is also implemented to represent a naïve approach. Where applicable, we augment the spatial indexes with two update techniques: bottom-up updating and update memo, to assess if these improve performance. Evaluation is performed by a benchmark suite, where a scenario of objects sampled from diﬀerent data distributions is used to quantify query and update performance of the spatial indexes. This evaluation is divided into two steps. First, parameters speciﬁc to each data structure is chosen, with 10 million objects in the scenario. Then, we compare the data structures, the update techniques, and the memory usage of the selection. We ﬁnd that the loose quadtree performs best for all measured scenarios in both updates and queries, while the R*-tree is worst, if not counting the query performance of the dynamic array. Bottom-up updating and update memo yielded unsatisfactory performance given the extra memory that is needed. The contribution of this thesis is twofold. First, we perform a thorough performance comparison for spatial indexes that support moving non-point geometry. To our knowledge, there exist no such survey at the time of writing. Secondly, we present novel query algorithms for the loose-linear quadtree which perform at least an order of magnitude better than other existing approaches.