Joins are not only one of the most important operations of the relational algebra, but also are expensive to compute. Nowadays, joins play a fundamental role in, e.g., searching for patterns in graphs, which is crucial for finding communities and recommending friends/followers in social networks, and finding fraudulent activities in transaction networks, among others. A relatively recent line of research studies worst-case optimal (WCO) join algorithms, with the aim of guaranteeing the worst-case running time of join processing. This talk presents a space-efficient indexing scheme known as the Ring Index, which (1) supports the WCO Leapfrog trie join algorithm; (2) uses space close to that of the plain representation of the graph; and (3) allows one to retrieve the input graph, so the index replaces the graph. We will present experimental results on Wikidata benchmarks showing that the Ring Index is competitive in practice with several state-of-the-art systems and algorithms.

Please email for a
Zoom link