Please enable JavaScript.
Coggle requires JavaScript to display documents.
Similarity Detection (Scene completion problem (Patch up holes in images…
Similarity Detection
Scene completion
problem
Patch up holes
in images
Find similar image regions
DB of millions of images
Seamless + semantically
valid
Nearest neighbors
Examples
Plagiarism /
Mirror sites
Recommenders
Classification
Entity resolution
Content-based
Similarity Search /
Query by content
Feature
extraction
Document =>
k-shingles
Hashing
k-shingles =>
Set of integers
k-shingles =>
0/1 vector
Similarity
estimation
Distance
Jaccard
Similarity
Intersection / Union
Distance
1 - Similarity
Euclidean
Cosine
Query
Similarity Join
Range Query
Complexity
Duplicate Detection
O(n^2 * d)
All duplicates
N(N-1) / 2
Filter & Refine
/ GEMINI
Algorithm
Approx. distance
function
Candidates
Filter
Quality
Completeness
Efficient
Indexable
Selective
Exact distance
function
Refinement
Result
Query
Quality Criteria
Completeness
Efficiency
Correctness
Hashing
Min-Hashing
Similarity
Hashed Similarity
Exact Similarity
Input Matrix + Permutation
=> Signature Matrix
One-pass
Implementation
Locality-Sensitive
Hashing
Partitioning
b Bands
r Rows
k Buckets
Analysis
Step function
S Curve
Straight Line
LSH Family
Constructions
Cascading
AND-OR
OR-AND
Set Membership
Bloom Filter