Dynamic query interfaces (DQIs) are a recently developed
database access mechanism that provides continuous real-time feedback
to the user during query formulation. Previous work shows that DQIs
are an elegant and powerful interface to small databases.
Unfortunately, when applied to large databases, previous DQI
algorithms slow to a crawl. We present a new incremental approach to
DQI algorithms that works well with large databases, both in theory
and in practice.