Graphs, Ranking & Search

Search Engine

Thirty tiny pages, one search box. Type a few words and see exactly which words pushed each page up the list.

Try searching for cat. Rare words count for more than common ones, and I will show you the maths.

Search the library

    Challenges

    Word endings: search something like "running dogs" so that matching endings changes which pages are found.
    Tiny words: search "the of a" so that ignoring tiny words changes the results.
    Popularity shuffle: mix in PageRank until a different page becomes number one. Try "park".

    What just happened?

    For grown-ups: what's really going on

    This is a miniature vector space model retrieval system. Each document is a sparse vector of TF-IDF weights and the query is scored by cosine similarity.

    • Term frequency: tf = 1 + ln(count) (sublinear, so repeating a word 10 times is not 10 times better).
    • Inverse document frequency: idf = ln((N + 1) / (df + 1)) + 1. A word in nearly every document says little; a rare word is a strong clue.
    • Both vectors are L2-normalised, so the cosine is just the dot product. It is the sum over query words of qw · dw, which is exactly the chip shown for each word. That is why this model is easy to explain.
    • Stop words are dropped, and a crude stemmer strips endings (real engines use Porter or lemmatisers, and it makes mistakes such as merging unrelated words).
    • The final score is (1 − m) · cosine + m · popularity, where popularity is PageRank (scaled to 0 to 1) over invisible "see also" links between the pages. Only pages that match at least one query word are ranked.
    • Real engines add inverted indexes for speed, BM25 (a refined TF-IDF), hundreds of other signals, and learned neural re-rankers. They also match meaning, not just words, which this model cannot do: "puppy" will never find "dog".

    Further reading: Manning, Raghavan and Schütze, Introduction to Information Retrieval, ch. 6 · Robertson and Zaragoza, The probabilistic relevance framework: BM25 and beyond.