Join Processing for Graph Patterns: An Old Dog with New Tricks
RelationalAI
01 January 2015
less than a minute read
Join Processing for Graph Patterns: An Old Dog with New Tricks
This paper asks if new join algorithms allow relational engines to close the performance gap with graph engines?
Dung Nguyen, Molham Aref, Martin Bravenboer, George Kollias, Hung Q. Ngo, Christopher Re´, Atri Rudra. 2015.
In Proceedings of the GRADES ‘15 (GRADES ‘15).
Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal for applications in graphic analytics. This suboptimality is one of the reasons that many have advocated supplementing relational engines with specialized graph processing engines. Recently, new join algorithms have been discovered that achieve optimal worst-case run times for any join or even so-called beyond worst-case (or instance optimal) run time guarantees for specialized classes of joins. These new algorithms match or improve on those used in specialized graph-processing systems. This paper asks can these new join algorithms allow relational engines to close the performance gap with graph engines?
Related Posts
Building a Named Entity Recognition Model for the Legal Domain
We defined named entity recognition (NER) in the legal domain and presented our approach towards generating ground truth data. In what follows, we go over the state-of-the-art in the NER domain and elaborate on the experiments we ran and the lessons we learned.
Read More
Named Entity Recognition in the Legal Domain
Named entity recognition is a difficult challenge to solve, particularly in the legal domain. Extracting ground truth labels from long, hierarchical documents is often slow and prone to error. RelationalAI proposes a new, scalable algorithm based on the principles of data-centric AI, designed to meet this challenge and generate high-quality annotations with minimal supervision.
Read More
Deep Learning with Relations, NeurIPS 2021
Molham shares some history of relational databases, trends in modern cloud-native database systems, and the innovations pioneered at RelationalAI to bring deep learning with relations from idea to reality.
Read More