Colloquium Series 2021 UTFSM Computer Science Department: "Optimal joins in graph databases with almost no additional space".
SUMMARY
The Computer Science Department of the Universidad Técnica Federico Santa María is pleased to invite the University community to its series of colloquiums 2021.
The join operation is one of the most important operations in relational algebra, so its efficient resolution is key to the efficiency of many database search applications. A current application of joins is pattern searching in graph databases (e.g., querying a graph to determine whether it contains triangles, squares, or cliques of a certain size). Recently, worst-case optimal algorithms for solving joins have become popular, since they guarantee a bounded execution time. In this talk we present a data structure that allows to solve worst-case optimal joins in graph databases, using sub-linear space over the space needed to represent the graph. In addition to providing theoretical worst-case and bounded space guarantees, we will show experimental results that indicate that the proposed scheme is competitive when compared to most of the well-known graph database systems. Also, the main lines of research being pursued.
PRESENTS
Diego Arroyuelo, Professor Department of Computer Science USM, IMFD researcher, PhD in Computer Science from the University of Chile. His main areas of interest are the design and analysis of algorithms and data structures, data compression algorithms and compact data structures. His experience includes a postdoctoral stay at the David R. Cheriton School of Computer Science at the University of Waterloo, Canada (2008-2009) and a position as a researcher at Yahoo! Research (2009-2015). He has been a Professor in the Department of Computer Science at USM since 2011 and is currently also a researcher at the Millennium Institute Foundational Research on Data.
WHEN AND WHERE
Tuesday, August 24, starting at 12:15 pm.
This presentation will be transmitted via https://tv.inf.utfsm.cl/coloquio
Participate, without prior registration, by accessing the link on the day and time of the event (link will be updated at the time of the colloquium).
15