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

Diego Arroyuelo is an Assistant Professor at Universidad Técnica Federico Santa María, Chile. He obtained his PhD at University of Chile and afterwards did a postdoctoral stay at the David Cheriton School of Computer Science, University of Waterloo, Canada. He also worked for Yahoo! Research. His main areas of research are succinct and compressed data structures, with several contributions on compressed data structures for text searching, compressed data structures for information retrieval, succinct and compressed data structures for graphs, trees, and sets, and succinct data structures for join processing in databases. In 2020, Communications of the ACM [63(11), 64-65] included Diego’s research among the 8 hot topics in computer science research in Latin America.