I/O efficient cutting trees

Abstract

This thesis is focused on the cutting tree data structure, which can be used for simplex range searching problems. The cutting tree is a data structure that allows for fast query times, but this comes at the cost of memory. The memory cost of using the cutting tree is O(n^2), which is unsuited for practical implementations. To overcome this problem we have analysed the data structure from an I/O efficiency standpoint since memory cost is less of a problem in external memory. We also constructed an implementation of the cutting tree to better analyse the bottlenecks of using the data structure.