Approximate selection with guarantees using proxies

Daniel Kang, Edward Gan, Peter Bailis, Tatsunori Hashimoto, Matei Zaharia

Research output: Contribution to journalArticlepeer-review

Abstract

Due to the falling costs of data acquisition and storage, researchers and industry analysts often want to find all instances of rare events in large datasets. For instance, scientists can cheaply capture thousands of hours of video, but are limited by the need to manually inspect long videos to identify relevant objects and events. To reduce this cost, recent work proposes to use cheap proxy models, such as image classifiers, to identify an approximate set of data points satisfying a data selection filter. Unfortunately, this recent work does not provide the statistical accuracy guarantees necessary in scientific and production settings. In this work, we introduce novel algorithms for approximate selection queries with statistical accuracy guarantees. Namely, given a limited number of exact identifications from an oracle, often a human or an expensive machine learning model, our algorithms meet a minimum precision or recall target with high probability. In contrast, existing approaches can catastrophically fail in satisfying these recall and precision targets. We show that our algorithms can improve query result quality by up to 30 x for both the precision and recall targets in both real and synthetic datasets.

Original languageEnglish (US)
Pages (from-to)1990-2003
Number of pages14
JournalProceedings of the VLDB Endowment
Volume13
Issue number11
DOIs
StatePublished - Jul 1 2020
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • General Computer Science

Fingerprint

Dive into the research topics of 'Approximate selection with guarantees using proxies'. Together they form a unique fingerprint.

Cite this