An Experimental Evaluation of k²-Tree on External Memory

Background: Managing huge amount of data can benefit from the use of compact data structures (like the k²-tree) that store the information in compressed form (usually in main memory), and can manipulate it without having to decompress it. However, as the amount of data is continuously increasing, it will be common that the compact data structures do not entirely fit into main memory, thus they will have to use disk. Aims: To provide an implementation of the k²-tree on external memory (disk). It will be a first approach that may serve as a baseline for future work. Materials and Methods: The data structure was implemented. A formal evaluation of the time complexity of the main operations was given, as well as an extensive experimental evaluation, comparing it to a Linear Quat Tree on disk. Results: The k²-tree was competitive of clearly surpassed the other structure in almost all cases. The memory footprint was always much lower. Discussion: The experiments compared the behavior of the k²-tree with the Linear Quadtree, showing the k2-tree as a better approach in general, in terms of efficiency and memory use. Conclusion: The proposed implementation was successful, and it will serve as a baseline for future implementation of compact data structures on disk (either different implementation of the k²-tree, or different data structures).