Skip to main content

Carlea Holl-Jensen||cholljen@umd.edu


HCIL-93-16

Jain, V., Shneiderman, B. (revised Sept. 1993)
Data Structures for Dynamic Queries: An Analytical and Experimental Evaluation
Proc. of the Workshop in Advanced Visual Interfaces, AVI 94 ( Bari, Italy, June 1-4, 1994) 1-11. Previous version referenced as CAR-TR-685 CS-TR-3133, ISR-TR-93-73. [Published Version]
HCIL-93-16, CS-TR-3287, CAR-TR-715, ISR-TR-94-47.

Dynamic Queries is a querying technique for doing range search on multi-key data sets. It is a direct manipulation mechanism where the query is formulated using graphical widgets and the result s are displayed graphically preferably within 100 milliseconds. This paper evaluates four data structures, the multilist, the grid file, k-d tree and the quad tree used to organize data in high speed storage for dynamic queries. The effect of factors like size, distribution and dimensionality of data on the storage overhead and the speed of search is explored. Analytical models for estimating the storage and the search overheads are presented, and verified to be correct by empirical data. Results indicate that multilists are suitable for small (few thousand points) data sets irrespective of the data distribution. For large data sets the grid files are excellent for uniformly distributed data, and trees are good for skewed data distributions. There was no significant difference in performance between the tree structures.


Restaurant Food Safety Inspections: Digital disclosure with a nationally standardized database Screenshot

Restaurant Food Safety Inspections
More information

Tech Reports
Video Reports
Annual Symposium

News
Seminars + Events
Calendar
HCIL Seminar Series
Annual Symposium
HCIL Service Grants
Events Archives
Awards
HCIL Conference Travel Award
Job Openings
For the Press
HCIL Overview
Become a Member
Collaborators
Collaborating Groups + People
Academic Visitors
Join our Mailing List
Contact Us
Visit Us
HCIL Store
Give the HCIL a Hand
HCIL T-shirts for Sale
Our Lighter Side
HCIL Memories Page
Faculty/ Staff
Students
Ph.D. Alumni
Past Members
Research Areas
Communities
Design Process
Digital Libraries
Education
Physical Devices
Public Access
Visualization
Research Histories
Faculty Listed by Research
Project Highlights
Project Screenshots
Publications and TRs
Videos
Books
Products
Presentations
Studying HCI
Masters in HCI
PhD in HCI
Visiting Scholars
Class Websites
Sponsor our Research
Sponsor our Annual Symposium
Active Sponsorship
Industrial Visitors