Evènement pour le groupe Séminaire Méthodes Formelles


Date 2021-11-30  14:00-15:00
TitreEfficiently Simulating a Sorted Array with Conjunctive Query Answers 
RésuméA sorted list of query answers may be much larger than the size of the input database. If its use-case does not entail going over this list one-by-one, but rather it is needed in order to compute the median, a boxplot, or another task that requires jumping arbitrarily to answers by their indices, computing this entire list is unnecessary and inefficient. In this talk, we inspect the question of when a sorted array of query answers can be efficiently simulated. We call this task ranked direct access and focus on near-optimal time guarantees. We ask in which cases ranked direct access can be achieved with only logarithmic factors as overhead on top of the linear time required to determine whether there is an answer, and the constant time required per accessed answer. Thus, we ask which CQs and orders can be answered with quasilinear preprocessing and polylogarithmic access time. We show algorithms for lexicographic and sum-of-weight orders, and prove conditional lower bounds implying that (under some complexity assumptions) our algorithms capture all tractable cases for self-join-free CQs. 
LieuSalle 178 (Hybride) 
OrateurNofar Carmeli 
Emailhttps://nofar.carme.li/ 
UrlÉcole Normale Supérieure, Paris 



Aucun document lié à cet événement.

Retour
Retour à l'index