Data structures for Dynamic Queries: An analytical and experimental evaluation

Simple item page
dc.contributor.authorJain, Viniten_US
dc.contributor.authorShneiderman, Benen_US
dc.date.accessioned2004-05-31T21:02:20Z
dc.date.available2004-05-31T21:02:20Z
dc.date.created0000-01en_US
dc.date.issued1998-10-15en_US
dc.description.abstractDynamic 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 millisec onds. 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 o verhead 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 distriubuted data, and trees are good for skewed data distributions. There was not significant difference in performance between the tree st ructures.%X additional reference numbers in the format of the next line Also cross-referenced as CAR-TR-715 Also cross-referenced as ISR-TR-94-47 Also cross-referenced as CS-TR-3133 Also cross-referenced as CAR-TR-685 Also cross-referenced as ISR-TR-93-73en_US
dc.format.extent998908 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/412
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtComputer Science Department Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3287en_US
dc.relation.ispartofseriesCAR-TR-715en_US
dc.relation.ispartofseriesISR-TR-94-47en_US
dc.relation.ispartofseriesCS-TR-3133en_US
dc.relation.ispartofseriesCAR-TR-685en_US
dc.relation.ispartofseriesISR-TR-93-73en_US
dc.titleData structures for Dynamic Queries: An analytical and experimental evaluationen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3287.ps
Size:
975.5 KB
Format:
Postscript Files
Download
Thumbnail Image
Name:
CS-TR-3287.pdf
Size:
195.35 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3287.ps
Download

Collections

Technical Reports of the Computer Science Department