Comparing locking strategies in large highly mutable loose quadtrees

Master’s Thesis in cooperation with KTH, the Royal Institute of Technology in Stockholm, Sweden.

Using a quadtree to store points or geometrical shapes in two dimensional environments is a well tried-out approach shown to be able to provide both fast updates of the carried data as well as fast intersect-checks for a specified area. These are all useful abilities for a data structure when tracking, for instance, emergency vehicles for operator centrals.

Tweaking this data structure to achieve even better performance can only get you that far and sooner or later other measures will be needed in order to reach higher capacity. For instance it could be the case that the flow of information needs to move quicker to supply the operators with the information they need.

One such measure commonly used in the field is the act of making the data structure concurrent. On a multithreaded machine a program that has been made concurrent can gain a speedup of up to the number of cores used, meaning the total running time can be improved plentiful.

In this thesis the loose quadtree with buckets is evaluated when different kinds of common parallelism approaches are applied. Batching in the form of bunching up incoming calls are done in two different lines of action, simply going through the queue of operations as well as rebuilding the tree with the changes applied to create a new tree.

Other approaches build upon the strategy of handover-hand-locking to try out how the tree works with node-coupled locks as well as to fully lock the data structure upon every interaction. These tactics are compared in different scenarios matching real-world appearances and evaluated both as a whole as well as for each individual scenario.

More information

Nyberg, Per. Comparing Locking Strategies in Large Highly Mutable Loose Quadtrees. 2020, http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-282862.