13 citations · 60 across the 31 of their papers we have counts for
34 papers
Optimal Convergence of Iterative Methods for Datalogo
Simon Frisk, Sungjin Im, Paraschos Koutris +4
has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization technique…
Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
Sungjin Im, Benjamin Moseley, Hung Q. Ngo +1
Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robu…
Binary Search with Distributional Predictions
Michael Dinitz, Sungjin Im, Thomas Lavastida +3
Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of wo…
Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
Sungjin Im, Benjamin Moseley, Hung Q. Ngo +1
Datalogo is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natur…
On the Convergence Rate of Linear Datalogo over Stable Semirings
Sungjin Im, Benjamin Moseley, Hung Ngo +1
Datalogo is an extension of Datalog, where instead of a program being a collection of union of conjunctive queries over the standard Boolean semiring, a program may now be a collec…
Controlling Tail Risk in Online Ski-Rental
Michael Dinitz, Sungjin Im, Thomas Lavastida +2
The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is -competitive in expectation. The…