# Queer Coders Meetup!

---
# From grep to Google

---
### Note on historical accuracy
I'm presenting somewhat related concepts in a way that builds on each other, but this is not the way this was built at the time. Lots of these techniques exist in parallel, and were (and still are) used in different domains to solve different problems. 

---
## Grep: Exact Matches
- "Find all documents containing this word"
- Strictly boolean, a document matches or it doesn't

---
### Basic Text Matching
- Library search (or at least, 90's library search)
- Field structure (Author, abstract, dates, etc)
- Boolean queries
---
## Bag of Words Model
- Ignore structure (document structure, grammar, etc)
- Just map the document to a (multi)set of words
---
### Text Analysis
- Stemming 
- Stopwords
- N-grams
- ...And More
---
### What is an Inverted Index
- Inverse of bag of words
    - BoW: Doc => Token Set
    - Inverted Index: Token => Doc Set
- Map of terms to list of documents, usually with counts and positions
- One of several core search engine data structures

---
### Ranking
- We don't want "all matches" we want "the best matches"
- There are lots of ways to rank
    - Time sorting (e.g. News search)
    - Relevance (e.g. Google circa 2002)
    - Paid positioning (e.g Google circa 2026)
    - etc

---
### TF-IDF
- Term frequency: how often does the term appear in the doc (scaled and normalized to minimize gaming)
- Inverse Document Frequency: how many documents include this word (also scaled and normalized)
- Essentially, "how common is this term in this document" divided by "how many documents use this term"
---
### Link Analysis
- To a degree, this is what separates "web search" from all other search use cases
- Use the link graph to rank pages
- Several algorithms, and lots of math.  Google called theirs Page Rank, and 25 years ago it was a revolution.

---
# Questions?
Thanks for listening!