ResearchEnumeration Algorithms

Overview

Picture of Enumeration Algorithms

The computational complexity of query evaluation in databases is usually measured in terms of “data complexity” and “combined complexity.” Unfortunately, these complexity classes do not encourage the design of efficient algorithms for many interesting query evaluation problems. The main weak spot of these measures is in their failure to take into consideration the size of the output, as well as the speed in which answers are returned to the user. In recent years, various concepts of enumeration have arisen in the fields of Databases, Computational Logic, and Algorithms, motivated by applications of data analysis and query evaluation. Common to all concepts is the desire to compute a stream of items with as small as possible waiting time between consecutive items, referred to as the “delay.” Alongside each concept, there evolved algorithmic techniques for developing solvers, and proof techniques for establishing complexity bounds. In addition to the traditional guarantees of “polynomial delay” and “incremental polynomial,” researchers have been pursuing stronger guarantees such as “constant delay” in the context of logical query evaluation, “dynamic complexity” of incremental maintenance, and “factorized databases.” Our research aims to develop novel algorithms and techniques for enumeration with both complexity and quality guarantees (e.g., ranked order), as well as to understand limitations that preclude the existence of such algorithms (i.e., lower bounds).

People

Selected Publications

Noam Ravid, Dori Medini, Benny Kimelfeld, "Ranked Enumeration of Minimal Triangulations", CoRR abs/1709.10254 (2017). To appear in PODS, 2019   abstractpaper
Nofar Carmeli, Markus Kröll, "Enumeration Complexity of Conjunctive Queries with Functional Dependencies", ICDT 2018: 11:1-11:17   abstractpaper
Dominik D. Freydenberger, Benny Kimelfeld, Liat Peterfreund, "Joining Extractions of Regular Expressions", PODS 2018: 137-149   abstractpaper
Ester Livshits, Benny Kimelfeld, "Counting and Enumerating (Preferred) Database Repairs", PODS 2017: 289-301    abstractpaper
Nofar Carmeli, Batya Kenig, Benny Kimelfeld, "Efficiently Enumerating Minimal Triangulations", PODS 2017: 273-287   abstractpaper