  Unstructured data (e.g., video or text) is now commonly queried by using
computationally expensive deep neural networks or human labelers to produce
structured information, e.g., object types and positions in video. To
accelerate queries, many recent systems (e.g., BlazeIt, NoScope, Tahoma, SUPG,
etc.) train a query-specific proxy model to approximate a large target labelers
(i.e., these expensive neural networks or human labelers). These models return
proxy scores that are then used in query processing algorithms. Unfortunately,
proxy models usually have to be trained per query and require large amounts of
annotations from the target labelers.
  In this work, we develop an index (trainable semantic index, TASTI) that
simultaneously removes the need for per-query proxies and is more efficient to
construct than prior indexes. TASTI accomplishes this by leveraging semantic
similarity across records in a given dataset. Specifically, it produces
embeddings for each record such that records with close embeddings have similar
target labeler outputs. TASTI then generates high-quality proxy scores via
embeddings without needing to train a per-query proxy. These scores can be used
in existing proxy-based query processing algorithms (e.g., for aggregation,
selection, etc.). We theoretically analyze TASTI and show that a low embedding
training error guarantees downstream query accuracy for a natural class of
queries. We evaluate TASTI on five video, text, and speech datasets, and three
query types. We show that TASTI's indexes can be 10$\times$ less expensive to
construct than generating annotations for current proxy-based methods, and
accelerate queries by up to 24$\times$.
