Home Bookmarks Search (Re)search Papers

Clustering and Similarity Search in Low Dimensions 

CS 497, Fall 2000
Section SHP, #08943
11:00 - 12:15 TuTh, 106B6 Engineering Hall
Announcement

Course Home page: http://www.uiuc.edu/~sariel/teach/2000/a/
Office hours: 15:00-17:00 on Thursday, DCL 2111. Please email if you plan to come.

In class

1. 8/24 Introduction
2. 8/29 Review of Voronoi Diagrams
3. 8/31 Quadtrees (slides, handout)
4. 9/5 Approximate nearest-neighbor search
5. 9/7 Approximate nearest-neighbor search - cont'
6. 9/12 Clustering and Greedy Clustering
7. 9/14 The fair split tree
8. 9/19 The fair split tree - computing nearest neighbor pair
9. 9/21 Computing k-nearest neighbor
10. 9/26 MST and spanners using Well Separated Pairs Decomposition
11. 9/28 Computing/approximating the diameter of a point-set
12. 10/3 Cont'
13. 10/5 A practical approach for approximating the diameter of a point-set. See here.
14. 10/10 Singular Value Decomposition
15. 10/12 Principal Component Analysis
16. 10/17 Principal Component Analysis - cont
17. 10/19 Convex shape approximation
18. 10/24 Convex shape approximation - cont'd
10/26, 10/31, 11/2 Canceled - would be completed by other means
19. 11/7 Convex Shape Approximation - Cont'd
20. 11/9 Approximating convex shape - using Dudley
21. 11/9 Approx. Extent Approx. Exent II Dimension reduction
22. 11/14 R-Tree, R^*-tree, etc
23. 11/16 Terrain simplification
11/18 - 11/26 Thanks giving vacation
24. 11/28 Shape simplification
25. 11/30
26. 12/5
27. 12/7 Last meeting!!!

Topics to be covered

here is a few of the things I would like to present. Note however that other topics might also be presented.
  1. Approx nearest neighbor search (Arya et al.)
  2. Computing all nearest neighbors
  3. Greedy clustering and Hardness of clustering - Feder and Greene
  4. Well Seperated Pairs Decomposition
  5. (*) Approximating the Diameter
  6. (*) Aproox Min Vol. Bounding Box (Fast Map)
  7. R-tree and its variants: R+, R*, Hilbert tree
  8. DB of moving objects
  9. (*) Apprxoimating the Extent of Moving Objects
  10. Apprximate k-median clustering(?)
  11. Techniques for Dimension Reduction
Last modified: Mon Sep 4 20:23:28 EDT 2000