Here is a list of data structures that we
discussed in class as well as the overall page numbers.  This is sort
of like a list of buzz words or topics with which you should have some
familiarity.  They are covered in the pages of the book that I gave 
you and am listing again below as I thought that this may serve as a
useful checklist to at least jog your mind on some concepts that we
discussed during the semester.  Of course, you should be aware of the
data structures in the appendices such as B-trees, AVL trees, linear
hashing, and spiral hashing as I figured that by now they should at
least be familiar to you.

Good luck.  
Prof. Hanan Samet

--------  page numbers and topics for CMSC 828M Spring 2008  -------- 

Chapter 1:  point data
pp. 1-116, 130-164, 184-190

inverted files
multilist
reduced combined indexes
doubly-chained tree (DCT)
multidimensional B-tree (MDBT)
multidimensional directory (MDD)
range tree
two-dimensional range tree
priority search tree
range tree
point quadtree
pseudo quadtree
MX quadtree
PR quadtree
k-d tree
adaptive k-d tree
fair-split tree
BSP tree
PR k-d tree
sliding midpoint k-d tree
bucket PR k-d tree
PMR k-d tree
path-compressed PR k-d tree
path-level compressed PR k-d tree
BD-tree
Balanced box-decomposition tree (BBD-tree)
k-d-B-tree
hybrid tree
LSD tree
hB-tree
k-d-B-trie
multilevel grid file
buddy-tree
BANG file
grid file
EXCELL
linear hashing
order preserving linear hashing (OPLH)
multidimensional extendible hashing (MDEH)
dynamic z hashing
quantile hashing
piecewise linear order preserving (PLOP) hashing
spiral hashing

Chapter 2:  image representations
pp. 191-160, 264-312, 355-362, 365-370, 374-377, 382-388, 399-408

tilings
space ordering methods
medial axis transformation
skeletons
irregular grid
region quadtree
region octree
ATree
bintree
XY-tree, treemap, and puzzletree
BSP tree
K-structure
separating chain
gap tree
layered dag
MX-CIF quadtree
cover fieldtree (loose quadtree, loose octree)
partition fieldtree
pyramid
R-tree
packed R-tree
R*-tree
R+-tree
k-d-B-tree
line quadtree
MX quadtree for regions
MX octree
quadtree complexity theorem
edge quadtree
PM1 quadtree
PM2 quadtree
PM3 quadtree
PM octree
bucket PM quadtree
PMR quadtree
strip tree
arc tree
BSPR
prism tree
restricted quadtree

Chapter 3:  intervals and small rectangles
pp. 427-439, 453-459, 466-483

plane-sweep method
segment tree
interval tree
representative point method
MX-CIF quadtree
bucket PR-CIF k-d tree
R-file
expanded MX-CIF quadtree

Chapter 4:  high dimensional data
pp. 485-499, 502-508, 508-517, 557-565, 567-571, 580-584, 585-591,
598-607, 608-609, 613-621, 637-641, 65-662

curse of dimensionality
best-first nearest neighbor finding
nearest neighbor finding in a spatial network
approximate nearest neighbor finding
sphere tree, SS-tree, balltree, SR-tree
approximate Voronoi diagram (AVD)
pyramid technique
vp-tree
mvp-tree
gh-tree
GNAT
bisector tree
mb-tree
kNN graph
Delaunay graph
SASH

Appendix B:  linear hashing
pp. 729-734

Appendix C:  spiral hashing
pp. 735-742