Data Structures for Dynamic Queries: An Analytical and Experimantal Evaluation.
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
Abstract
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 results 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 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.
(Also cross-referenced as CAR-TR-685)
(Also cross-referenced as ISR-TR-93-73)