Efficient Multi-Object Dynamic Query Histograms

Mark Derthick, James Harrison, Andrew Moore, and Steven F. Roth
Proceedings of the IEEE Information Visualization Conference (InfoVis '99), 1999.


Download
  • Adobe portable document format (pdf) (284KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Dynamic Queries offer continuous feedback during range queries, and have been shown to be effective and satisfying. Recent work has extended them to datasets of 100,000 objects and, separately, to queries involving relations among multiple objects. The latter work enables filtering houses by properties of their owners, for instance. Our primary concern is providing feedback from histograms during Dynamic Query. The height of each histogram bar shows the count of selected objects whose attribute value falls into a given range. Unfortunately, previous efficient algorithms for single object queries overcount in the case of multiple objects if, for instance, a house has multiple owners. This paper presents an efficient algorithm that with high probability closely approximates the true counts.

Notes

Text Reference
Mark Derthick, James Harrison, Andrew Moore, and Steven F. Roth, "Efficient Multi-Object Dynamic Query Histograms," Proceedings of the IEEE Information Visualization Conference (InfoVis '99), 1999.

BibTeX Reference
@inproceedings{Derthick_1999_2813,
   author = "Mark Derthick and James Harrison and Andrew Moore and Steven F Roth",
   title = "Efficient Multi-Object Dynamic Query Histograms",
   booktitle = "Proceedings of the IEEE Information Visualization Conference (InfoVis '99)",
   year = "1999",
}