We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
EntropyDB: a probabilistic approach to approximate query processing.
- Authors
Orr, Laurel; Balazinska, Magdalena; Suciu, Dan
- Abstract
We present, an interactive data exploration system that uses a probabilistic approach to generate a small, query-able summary of a dataset. Departing from traditional summarization techniques, we use the Principle of Maximum Entropy to generate a probabilistic representation of the data that can be used to give approximate query answers. We develop the theoretical framework and formulation of our probabilistic representation and show how to use it to answer queries. We then present solving techniques, give two critical optimizations to improve preprocessing time and query execution time, and explore methods to reduce query error. Lastly, we experimentally evaluate our work using a 5 GB dataset of flights within the USA and a 210 GB dataset from an astronomy particle simulation. While our current work only supports linear queries, we show that our technique can successfully answer queries faster than sampling while introducing, on average, no more error than sampling and can better distinguish between rare and nonexistent values. We also discuss extensions that can allow for data updates and linear queries over joins.
- Subjects
MAXIMUM entropy method; PROBABILISTIC databases
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2020, Vol 29, Issue 1, p539
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-019-00582-9