An analysis of query-agnostic sampling for interactive data exploration

Data analysts often explore a large database to identify the data of interest, but may not be able to specify the exact query to send to the database. A manual data exploration process is labor intensive and time-consuming. In the new paradigm of system-aided interactive data exploration, the Database Management System presents the samples to the user and engages the user in an interactive exploration process to identify the user interest. In this article, we examine a number of initial sampling techniques to identify at least one positive (i.e., interesting) sample and compare them both theoretically and empirically.