Knowledge Discovery
Session 06

A Common Quest: Finding Similarities

4 hours · Week 6 · the motivating question of Part 3

Conceptual position: This chapter starts from a question that recurs across data science: which things are alike? Near-duplicates, nearest neighbors, recommendations, clusters, and communities are all answers to it. We introduce the lightweight representations needed to begin — sets, shingles, MinHash — and let the pressure of harder questions motivate Session 07: Creating Useful Representations.

Learning Objectives

  • Frame “finding similar things” as a recurring data-science quest and recognise how the question forces a representation choice
  • Use shingling and MinHash as the first concrete representations — just enough to define overlap between documents
  • Use distance metrics such as Jaccard, cosine, and Euclidean distance appropriately
  • Explain why exact all-pairs similarity is expensive at scale
  • Use Locality-Sensitive Hashing as an approximate candidate-generation method
  • Connect similarity search with preference modeling and recommender systems
  • Apply clustering methods such as K-means and DBSCAN and understand their assumptions
  • Connect ordinary clustering with graph clustering and community detection

Preferences and Recommendations

Similarity is often a proxy for preference

In recommender systems, we often represent users and items so that nearby objects predict likely preferences: similar users, similar products, co-watched movies, or items that complete the same task.

But preference is not just similarity

A user may prefer novelty, diversity, price constraints, or complementary items. This is why recommendation combines representations, similarity search, ranking, constraints, and evaluation.

Core Story

Start with the question, let it force the representation

Finding similar things — near-duplicate articles, neighbouring users, co-watched movies, dense regions in a feature space, communities in a graph — is one of the most common problems in data science. Asking it forces a choice: what should count as alike? That choice is already a representation decision.

The central tradeoff
Exact similarity search and all-pairs clustering are often too expensive. Practical systems use indexes, approximations, candidate generation, and second-stage verification.

Similarity Search

Nearest neighbors

Given a query object, find the most similar objects in the collection. The answer depends on the representation and metric: Jaccard for sets, cosine for many embeddings, and Euclidean distance for geometric vectors with meaningful scale.

Near-duplicate detection

For copied or lightly edited text, we can represent documents with shingles, estimate overlap using MinHash signatures, and use LSH banding to avoid comparing every pair exactly.

Guided lab

The lab walks slowly through raw documents, shingles, exact Jaccard, MinHash, LSH banding, tuning, and a comparison with document embeddings.

Open LSH step by step →

Materials

Readings

Labs & exercises