1. Metric Spaces, Nets, Measures, Dimensions, and Search

    Ken Clarkson
    IBM Almaden Research


    Aarhus Summer School
  2. Nearest Neighbor Search: the Problem

  3. Nearest Neighbor Search: Synonyms

  4. The Distance Function as a Metric "Black Box"

  5. Goals for NN Search Data Structures

  6. Metric Spaces: Definition and Repairs

    A metric space `(U,D)` has `D(x,y) \ge 0` and `D(x,x)=0` for all `x,y \in U`, and also:
  7. New Metrics from Old

    Start with uniform metric on finite set, or `(\reals, |x-y|)`;
    Suppose `(U,D)`, and `(U_1,D_1)\ldots(U_m,D_m)` are metric spaces.
  8. New Metrics from Old: Subsets

  9. New Metrics from Old: Numeric Transforms

  10. Numeric Transforms, II

  11. Numeric Transforms, III

  12. The Biotope Transform

  13. Biotope Distance : a.k.a.

  14. Subset Biotope

    For `A\subset U`, $$\hat D(x,y) \equiv \frac{2D(x,y)}{\inf_{a\in A} D(x,a) + D(y,a) + D(x,y)}$$ is a metric.
  15. A Metric Space Scaled to Local Feature Size

  16. So What?

  17. NN Search: Using the Triangle Inequality

  18. Using the Triangle Inequality

  19. Using Distances to `P\subset S`

  20. AESA

  21. Orchard Algorithm

  22. Using Less Space

  23. `\epsilon`-nets and the Greedy Algorithm

  24. Greedy Construction Properties

  25. Approximate Nearest Neighbor Searching

  26. Approximate NN Searching, Correctness

  27. Approximate NN Searching, Analysis

  28. Nets as Roadmaps: Motion Planning

  29. Nets as (Non)-Probabilistic Roadmaps

  30. Nets as Roadmaps, Analysis

  31. Nets as "Beacons" or "Landmarks"

  32. Nets as Vertices in Approximations


  33. What Distance Measure?


    Arc Length
    Turning Angle
    Both
  34. Nets as Vertices of Graded Triangulations

  35. Building a triangulation

  36. `\epsilon`-Nets: Also....

  37. Non-Greedy Construction

  38. Differently Greedy: `\epsilon`-cover with Outliers

  39. Cover with Outliers, Hints

  40. Non-`\epsilon`-Nets: Cover-like

    There are many other `N \subset U` that are well-distributed
  41. Approximation to `k`-means sets

  42. Non-`\epsilon`-Nets: Packing-like

    Min analogs to packing measure `\min_{p,p'\in N} D(p,p')`
  43. Other Energies

  44. Density Nets

  45. Dimension and Approximate Measure

  46. Box Dimension Equivalents

  47. Hausdorff Dimension

  48. Box Dimension: Problems with Finiteness

  49. Box Dimension: Problems with Finiteness

  50. Coping with Finiteness: Extremal Graphs

  51. Energy Dimension

  52. Even More Dimensions: Metric Measure Spaces

  53. Quantization Dimension

  54. Pointwise Dimension

  55. Pointwise Dimension and Others

  56. -->
  57. Doubling Dimension

  58. Doubling Dimension, More About

  59. Doubling Dimension, Embedding, NN Search

  60. Doubling Dimension and Approximate NN

  61. Approximate NN Search, Analysis

  62. Divide-and-Conquer

  63. Doubling Measures

  64. Divide-and-Conquer for Doubling Measures

  65. Doubling Measures: `B_p` is Enough

  66. Divide-and-Conquer

  67. Exchangeable Queries

  68. Exchangeable Queries, Hints: (3)-NNs

  69. Exchangeable Queries, Hints: Dominating Queries

  70. Less Space

  71. Less Space: Preprocessing

  72. Less Space: Examples

  73. Voronoi Grouping

  74. Voronoi Grouping: Ruling Out

  75. Voronoi Grouping: An Example

  76. Voronoi Grouping: Other Work

  77. Barriers to Use in Practice

  78. Thanks for Your Attention!

  79. We got this Far?

  80. Neighbors

  81. Weak Neighbors

  82. Neighborhoods: Analysis

    How many pairs `m` of neighbors can there be?
  83. Interpolation in Metric Spaces

  84. (The Laplacian as Interpolation)

  85. Interpolation in Metric Spaces: Radial Functions