Speaker: Nikolaos (Nikos) Tziavelis
Location: Soda 380
Date: December 13, 2023
Time: 11AM – 12PM PST
Title: “Efficient Ranked Access over Joins”
Abstract:
Join queries over multiple tables can produce a huge output that is infeasible to compute. Even when it is feasible, it is often not efficient when users have particular preferences over the answers in the output and are interested in accessing only a small subset according to that ranking; either to retrieve the most important answers or the quantiles for a statistics summary. We show that for many such queries, access patterns, and ranking functions over the answers, ranked access can be performed efficiently, without first computing the entire join output. This is captured theoretically by non-trivial complexity guarantees and shown in practice with efficient implementations that avoid the cost of expensive join operations. Besides addressing fundamental questions regarding the limits of query processing, this work opens up unexplored possibilities for the design of database systems. We clearly demonstrate how existing systems fall short in handling ranking over joins efficiently, with our algorithms outperforming them by orders of magnitude.
Bio:
Nikolaos (Nikos) Tziavelis is a PhD candidate at Northeastern University, advised by Mirek Riedewald and Wolfgang Gatterbauer, and before that, he
received a Diploma in Electrical and Computer Engineering from the National Technical University of Athens. His research interests lie in the design and implementation of novel practical algorithms for query processing in data systems. His work has been awarded with a Google PhD fellowship, a VLDB 2023 PhD Workshop Best Paper Award, and a PODS 2021 “Best of” recognition.