An Experimental Evaluation of <i>k</i> ² ‐Tree on External Memory

ABSTRACT Background Managing huge amount of data can benefit from the use of compact data structures (like the k 2 ‐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 2 ‐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 2 ‐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 2 ‐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 2 ‐tree, or different data structures).