Dynamic query interfaces (DQIs) are a recently developed mechanism for specifying queries and visualizing their results [1, 2, 5, 6, 7, 8, 9, 12, 14]. Unlike textual query languages such as SQL, DQIs are graphical. A great advantage of DQIs is that they provide continuous feedback to the user as the query is being formulated. Experiments showed that querying with DQIs is faster, easier, more pleasant, and less error-prone than with the other querying interfaces [2, 14]. A sample DQI is presented in Figure 1 (created by ).
Figure 1: Spotfire: a sample DQI (www.ivee.com). The user specifies a query using the widgets along the left, bottom, and right of the screen. The hit set for the current query is displayed as a starfield in the large square. (This example does not contain a preview bar or chart with aggregate information about the database but shows the hit set size by a count at the bottom of the screen).
Queries are made using widgets, such as range sliders (for continuous data attributes), alphanumeric sliders (for textual attributes), toggles (for binary attributes), and check boxes (for discrete multi-valued attributes), to specify each attribute (dimension) of the data. Output is provided via a starfield display (a 2-dimensional projection of the set of hits), bars (such as a preview bar that displays the number of hits), and charts (which provide other aggregate information). The widgets are tightly coupled: as the hit set varies all the widgets are updated to show the hit set's bounding rectangle, so the widgets provide a limited form of output as well. If desired, we can even display a histogram on each widget to show the distribution of data in its dimension. The user may click on an individual point on the starfield for details-on-demand.
Range sliders are used for continuous attributes. See Figure 2 for a sample range slider. A range slider contains a pair of arrows, one at each end. The user selects a range slider by clicking on it, and the user adjusts the range by dragging either arrow with a mouse. As the range is being adjusted, the starfield, bars, and charts are updated. Histograms and states of the other widgets can also be updated. Thus, for each tiny increment of the range slider, much information must be computed rapidly.
Toggles allow the user to specify a binary attribute of the data. On the screen they look like boxes. Internally they can be implemented directly without much trouble or treated as a nearly trivial special case of range sliders. List boxes and radio buttons (and some other similar widgets) can be handled with similar ease.
Alphanumeric sliders allow the users to specify a range of strings. Although our auxiliary data structures apply to them as well, the fine granularity of alphanumeric data seems to necessitate additional implementation ideas that are best described in a separate paper.
Figure 2: A sample range slider. By moving the arrows, the user specifies a range, which is represented by the white rectangle. The numbers above the arrows give the current range. The numbers on the far ends of the range slider are the extreme values that the attribute can take.
We propose a new approach to DQI algorithms that can handle larger databases than the previous implementations. This paper expands our previous work  by providing a detailed explanation and evaluation of our DQI algorithms. We present our approach in general in Section 2. We give a detailed explanation of the data structures and algorithms in Section 3. We present theoretical complexities in Section 4. We give the evaluation of our approach (with a specific implementation that uses range sliders) in Section 5. We state our conclusions and future plans in Sections 6 and 7.