Title: Searching by Similarity on a Very Large Scale

Lecturer: Giuseppe Amato, CNR Pisa

Period: 4 - 15 July 2016, 11.00 - 13.00

  • Foundation of Metric Space Searching
    • Distance Searching Problem
    • Metric Distance Measures
    • Similarity Queries
    • Basic Partitioning Principles
    • Principles of Similarity Query Execution
    • Policies for avoiding Distance Computations
    • Metric Space Transformations
    • Priciples of Approximate Similarity Search
    • Advanced issues: Statistics, Proximity, Performance Prediction, Tree quality measures
    • Advanced issues: Choosing reference points
  • Exact Similarity Search
    • Vantage Point Trees
    • AESA/LAESA
    • GNAT
  • The M-Tree Family
    • The M-Tree
    • Bulk-Loading Algorithm
    • Multy-Way Insertion Algorithms
    • The Slim Tree
    • Slim-Down Algorithm
    • Pivoting M-Tree
  • Hash Based Methods
    • D-Index
    • Approximate Similarity Search with M-Tree
      • Relative Error Approximation
      • Good Fraction Approximation
      • Small Chance Improvement Approximation
      • Proximity-Based Approximation
      • PAC Nearest Neighbor Searching
      • Performance tests
    • Other Approximate Similarity Search Methods
    • Permutation Based Methods
      • Permutation Spearman Rho
      • PP-Index
      • MI-File
    • Locality Sensitive Hashing (LSH)
      • LSH based on p-stable distributions
      • LSH with Hamming Distance