Exploring the Potential of kⁿ-tree for Efficient Representation of n-ary Relations

The objective of this experimental study was to investigate the scalability of -trees, a compact data structure designed for representing -ary relations, compared to a baseline based on a plain representation of adjacency lists. A literature review of compact data structures was conducted, focusing on -trees and their potential for efficient -ary data representation. To assess scalability, experiments comparing -trees performance against the baseline using set intersection as a benchmark were conducted. Results demonstrated superior -trees scalability in terms of time and memory, especially for high-dimensional and clustered datasets. On average, -trees were eight times faster and consumed times less memory than the baseline. The study also analyzed the impact of the order parameter on performance, revealing a trade-off between space efficiency and query time. This study provides valuable insights into the practical applicability of -trees for managing and querying high-dimensional data.