This is a Rust project which aims to test the performance of the K2-Tree data structure in terms of memory usage and query speed in comparison to traditional bit matrices.
The original paper used as baseline for this project can be found here. Within it, the authors describe the K2-Tree data structure and its applications in the context of web graph representation.
To compile the project, simply run the following command:
cargo build --releaseOnce built, you may run the executable directly. The program will output the results to csv files into a directory
named data/. These results are then used to generate plots with R. If you want to generate the plots, simply open
K2Tree.Rproj with RStudio and run the script. The generated plots will look as follows:
This project was written as part of the Masters in Computer Science course "Advanced Data Structures and Algorithms" at the University of the Bío-Bío.