[Zurück]

R. Pichler:
"Technical Perspective: Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation";
ACM SIGMOD Record, 49 (2020), 1; S. 51.

Traditionally, by query answering we mean the problem of finding all answers to a given query over a given database. But what happens if the number of answers is prohibitively big - which may easily occur in a Big Data context? In such situations, it seems preferable to have a mechanism that produces one answer after the other with certain guarantees on the time between any two outputs and to let the user decide when to stop. This leads us to the enumeration problem, which has received a lot of interest recently [1]. However, in order for the user to get a "realistic" picture of the entirety of answers, two crucial questions arise: first, how big is the portion of output answers compared with the total number of answers? And second, do the output answers reflect the variety of the complete set of answers? The first question refers to the counting problem, where we are interested in the total number of answers. The second question leads us to the problem of uniform generation, where we request that the answers be uniformly generated and thus form an unbiased sample of the complete set of answers.

http://dx.doi.org/10.1145/3422648.3422660