Exam

• Start: Karhunen-Loeve-Transformation (PCA)
  • Basis rotation / Decomposition of the covariance matrix
  • Dimension Reduction by removing small eigenvalues (variances)
  • Requires a Euclidean space
• Edit distances
  • Some data has no Euclidean space
  • Expensive, use GEMINI
  • Prune data and then compute the distance
  • Levenshtein distance
    • Computation
    • Dynamic programming
    • What metrics work? –> Additive metrics (comparable to Markov property; the way we got to the result does not matter)
  • Indexing using M-Trees
• M-Trees
  • Idea
  • Spherical geometry using the Triangle Inequality
  • Explain pruning criterion