A study of the kinetic data structure paradigm with focus on kinetic kd-tree and kinetic range trees – Københavns Universitet

A study of the kinetic data structure paradigm with focus on kinetic kd-tree and kinetic range trees

Master's Defence by Søren Erling Lynnerup

Supervisor Pawel Winter and external evaluator Gerth Stølting Brodal

Abstract

The most common type of data structures we see in text books are static data structures. They operate on objects which are static over the time of the execution. In many problems, e.g. regarding GPS-devices, we are interested in objects whose value evolves over time. Data structures which work on objects as a function of time are called kinetic data structures. In this thesis I present the kinetic framework, explain what kinetization is and give multiple examples of kinetizations and kinetic data structures.

The task of performing orthogonal range searching is, given a set of points in d dimensions, to find the points inside a given d-dimensional query window. Data structures like range trees and kd-trees can be used to perform this task and my focus is mainly on kinetic range trees. I present a kinetization of range trees based on alpha trees and discuss how the concept of fractional cascading could be applied onto this kinetized data structure. I implement the kinetic range tree and measure the performance compared to rebuilding static range trees. This shows that you will need to perform many queries to compensate for the overhead of maintaining the kinetic range tree. I also shortly test if the kinetic range tree can be used as a tool for energy contribution calculations when performing protein structure prediction, by benchmarking a proof-of-concept example, with the result that other solutions might be a more efficient choice.