A Critical Review and Performance Evaluation of New Compressed Indices for Multi-Way Join Operations on Graph Databases

Graph databases have become the essential instrument of choice for effectively modeling related and interconnected data, in particular in knowledge graphs and network analysis applications. However, their efficient execution remains a challenging task due to the stringent requirements on both execution time and memory consumption when performing complex queries such as multi-way join (multijoin) operations. To address this challenge, Worst-Case Optimal (WCO) algorithms have been recently proposed, including Leapfrog Triejoin (LTJ). Nonetheless, their practical applicability is often limited by the massive amount of index structures that they require. The paper titled "New Compressed Indices for Multijoins on Graph Databases" presents a novel suite of compressed indices that are integrated with adaptive execution techniques to achieve a favorable trade-off between query performance and storage overhead. The proposed method uses static, memory-resident indexes, for example the rdfcsa index, together with an Adaptive VEO (Vertex/Edge Ordering) strategy. Experimental results from the paper demonstrate substantially improved early result rates and significant storage compression when compared to conventional high-performance methods. This method provides a practical solution for multijoin processing on graph databases with limited memory.

کلیدواژه ها:

Multijoins ، Worst-Case Optimal Joins (WCO) ، Leapfrog Triejoin (LTJ) ، Compressed Indices ، RDF Data Management ، Knowledge Graphs ، Space–Time Trade-offs ، In-Memory Indexing