Question 6
How can data structures be designed for efficiency?
The basic computer science tricks for a data structure are:
lists
tables
files
All sequential in some sense. Sorting helps, but doesn't solve all problems.
Random access depends on knowing how to jump through the structure...
A number of basic data structures provide access:
trees
hash tables
"heaps" (of various kinds)
The "Get" function isn't as direct as it sounds, and may be the
real issue in an application...
Spatial indexing adds many complexities to the linear issues of the simple
data structures:
Spatial objects have different sizes and cover a range of space (rectangle)
In response to this question, pick at least one of the
options below:
- Write your own sorting procedure and try to figure out its complexity.
- Why does it matter if a tree is balanced? How balanced does it need
to be?
- Try some of the spatial index demos
at Maryland. Report what you found out.
- What about quadtrees? (There are many kinds, so be specific...) What
can a quadtree do to provide efficient access (and for what kinds of spatial
data)? The real resource is Hanan
Samet's books
Your answers shouldn't be much longer than one page.
Index from here: Back to 465
Main Page | Ten Questions / Assignments
| Glossary from Exploring GIS
| Schedule | Bibliography
| Course Policies | Resources
Version of 17 February 1999