Top-k queries have been studied intensively in the database community and they are an important means to reduce query cost when only the “best” or “most interesting” results are needed instead of the full output. However, optimality results for queries involving joins hold only in a fairly limited model of computation that does not account for the cost incurred by large intermediate results. On the other hand, the idea of avoiding large intermediate results is arguably the main goal of recent work on optimal join algorithms, which has created a lot of excitement due to its promise of reducing the time complexity of join queries with cycles, but it has mostly focused on full-output computation. In this talk, I will present the problem of ranked enumeration that lies in the intersection of these two research areas. The goal is to return query results one after the other in order of their importance with theoretical guarantees that are better suited for in-memory computation. I will focus on algorithms that have their roots on the k'th shortest path problem, the properties of the ranking function that allow efficient computation, as well as extensions to join conditions beyond equality.
Based on a VLDB’20 paper, a SIGMOD’20 tutorial, and a preprint.
https://doi.org/10.14778/3397230.3397250
https://doi.org/10.1145/3318464.3383132
https://arxiv.org/abs/2101.12158
BIO:
Nikolaos Tziavelis is a 3rd PhD student at the Khoury College of Computer Sciences of Northeastern University. His research interests lie in algorithms for database query processing and distributed computing. He holds a MEng in Electrical and Computer Engineering from the National Technical University of Athens.
