Seminer Duyurusu: "How can (worst-case optimal) joins be so interesting ?" by Asst. Prof. Semih Salihoğlu

tarafından Fahrettin Ay | Ara 07, 2018

Başlık
:
"How can (worst-case optimal) joins be so interesting ?"
Konuşmacı : Asst. Prof. Semih Salihoğlu
Tarih : 12 Aralık 2018 (Çarşamba)
Saat : 15:30 - 17:00
Yer : EEB İdris Yamantürk Konferans Salonu (1304)

Abstract:
Worst-case optimality is perhaps the weakest notion of optimality for algorithms. A recent surprising theoretical development in databases has been the realization that the traditional join algorithms, which are based on binary joins, are not even worst-case optimal. Upon this realization, several surprisingly simple join algorithms have been developed that are provably worst-case optimal. Unlike traditional algorithms, which join subsets of tables at a time, worst-case join algorithms perform the join one attribute (or column) at a time. This talk gives an overview of several lines of work that my colleagues and I have been doing on worst-case join algorithms focusing on their application to subgraph queries. I will cover work from both distributed and serial settings. In the distributed setting, worst-case optimality is a yard-stick for two costs of an algorithm: (i) the load, i.e., amount of data per machine; and (ii) the total communication. Both load and communication complexity are at a trade-off with number of rounds an algorithm runs. I will describe how to achieve worst-case optimality in total communication and the performance of this algorithm on subgraph queries. It is an open theoretical problem to design constant-round algorithms with worst-case optimal load. In the serial setting, I will describe the optimizer of a prototype graph database called Graphflow that we are building at University of Waterloo. Graphflow's optimizer for subgraph queries mixes worst-case optimal join-style column-at-a-time processing seamlessly with traditional binary joins. 

Short Biography:
semih_salihogluSemih Salihoglu is an Assistant Professor at University of Waterloo. His research focuses on graph databases, distributed systems for processing graphs, and algorithms and theories for distributed evaluation of database queries. He holds a PhD from Stanford University and is a recipient of the 2018 VLDB best paper award. 
07
Ara 2018
Seminer Duyurusu: "How can (worst-case optimal) joins be so interesting ?" by Asst. Prof. Semih Salihoğlu


Başlık
:
"How can (worst-case optimal) joins be so interesting ?"
Konuşmacı : Asst. Prof. Semih Salihoğlu
Tarih : 12 Aralık 2018 (Çarşamba)
Saat : 15:30 - 17:00
Yer : EEB İdris Yamantürk Konferans Salonu (1304)

Abstract:
Worst-case optimality is perhaps the weakest notion of optimality for algorithms. A recent surprising theoretical development in databases has been the realization that the traditional join algorithms, which are based on binary joins, are not even worst-case optimal. Upon this realization, several surprisingly simple join algorithms have been developed that are provably worst-case optimal. Unlike traditional algorithms, which join subsets of tables at a time, worst-case join algorithms perform the join one attribute (or column) at a time. This talk gives an overview of several lines of work that my colleagues and I have been doing on worst-case join algorithms focusing on their application to subgraph queries. I will cover work from both distributed and serial settings. In the distributed setting, worst-case optimality is a yard-stick for two costs of an algorithm: (i) the load, i.e., amount of data per machine; and (ii) the total communication. Both load and communication complexity are at a trade-off with number of rounds an algorithm runs. I will describe how to achieve worst-case optimality in total communication and the performance of this algorithm on subgraph queries. It is an open theoretical problem to design constant-round algorithms with worst-case optimal load. In the serial setting, I will describe the optimizer of a prototype graph database called Graphflow that we are building at University of Waterloo. Graphflow's optimizer for subgraph queries mixes worst-case optimal join-style column-at-a-time processing seamlessly with traditional binary joins. 

Short Biography:
semih_salihogluSemih Salihoglu is an Assistant Professor at University of Waterloo. His research focuses on graph databases, distributed systems for processing graphs, and algorithms and theories for distributed evaluation of database queries. He holds a PhD from Stanford University and is a recipient of the 2018 VLDB best paper award. 

Hakkımızda


bb-about

İstanbul Teknik Üniversitesi'nde Bilgisayar Mühendisliği eğitimi, 1980 yılında Elektrik-Elektronik Fakültesi bünyesinde kurulan Kontrol ve Bilgisayar Mühendisliği Bölümü ile başlamıştır. Çağın gereklerine daha uygun bir eğitim verebilmek amacıyla, 1997 yılında Bilgisayar Mühendisliği aynı fakültenin bir bölümü olarak yeniden yapılanmıştır. 2010 yılında Bilgisayar ve Bilişim Fakültesi'nin kurulmasıyla ilgili program ve bölümler yeni fakülteye aktarılmıştır.

İTÜ Bilgisayar ve Bilişim Fakültesi'nin öğrencilerine ve çalışanlarına yönelik belgeleri, iş-staj ilanlarını ve duyuruları barındıran portal'a erişim için tıklayınız

Fakültemizin öğrencilerine ve mezunlarına yönelik iş, staj, etkinlik v.b. ilanlar yapmak isteyen kuruluşlar portaldaki yeni ilan formunu kullanabilirler. 

Fakülteden yapılan duyuruları ve kuruluşların ilanlarını izlemek isteyen öğrencilerimiz portalın RSS beslemesine abone olabilirler.


abet-akreditasyonu
İTÜ Bilgisayar Mühendisliği Lisans Programı

ABET  Mühendislik Akreditasyon Komisyonu (EAC) tarafından akredite edilmiş bir programdır, www.abet.org