turkmath.org

Türkiye'deki Matematiksel Etkinlikler


11 Aralık 2018, 15:40


Orta Doğu Teknik Üniversitesi Uygulamalı Matematik Enstitüsü Seminerleri

How can (worst-case optimal) joins be so interesting

Semih Salihoglu
Cheriton School of Computer Science, University of Waterloo, Kanada

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.
Uygulamalı Matematik İngilizce
Hayri Körezlioğlu Seminar Room, IAM, METU
İlgili Web Bağlantısı

ume 29.11.2018

Yaklaşan Seminerler Seminer Arşivi
 

İLETİŞİM

Akademik biriminizin ya da çalışma grubunuzun ülkemizde gerçekleşen etkinliklerini, ilan etmek istediğiniz burs, ödül, akademik iş imkanlarını veya konuk ettiğiniz matematikçileri basit bir veri girişi ile kolayca turkmath.org sitesinde ücretsiz duyurabilirsiniz. Sisteme giriş yapmak için gerekli bilgileri almak ya da görüş ve önerilerinizi bildirmek için iletişime geçmekten çekinmeyiniz. Katkı verenler listesi için tıklayınız.

Özkan Değer ozkandeger@gmail.com

DESTEK VERENLER

ja2019

31. Journees Arithmetiques Konferansı Organizasyon Komitesi

Web sitesinin masraflarının karşılanması ve hizmetine devam edebilmesi için siz de bağış yapmak, sponsor olmak veya reklam vermek için lütfen iletişime geçiniz.

ONLİNE ZİYARETÇİLER


©2013-2020 turkmath.org
Tüm hakları saklıdır