ML System Design Interview Ch 9 · Similar Listings

Machine Learning System Design Interview · Ch 9 · Ali Aminian & Alex Xu · 2023

What is this chapter about?

You open a place to stay on a rental site, scroll down, and there is always a row of "you might also like." This chapter is about how that row gets picked.

A strange thing first

You probably assume it hunts for places that resemble the one you are viewing — same neighborhood, same two bedrooms, same $120 a night. Filter that way and the results mostly go unclicked.

Meanwhile two places whose specs differ quite a bit — one $120 and one $150, one a whole apartment and one a room in the host's home — get compared back and forth by the same crowd of people, who eventually book one of them. Those two are the genuinely similar pair, because in real people's heads they are interchangeable.

So the pivot in this chapter is: what counts as similar is not decided by the property's specs, it is decided by the people looking at it.

Why the old way is hard

Nobody ever wrote down the answer. Across millions of listings there is no table anywhere saying "A and B are similar." Label them by hand? The number of pairs is astronomical; you could label for a lifetime and not finish.

Computing similarity from the specs drops you straight back into the first trap. Two places can both be "two bedrooms, $120, city center" while one opens onto a subway entrance and the other is a twenty-minute climb uphill. How good the photos are, how it actually feels to stay there — none of that fits in a spec sheet, and that is exactly what people decide on.

The core idea: let browsing trails define similarity

The platform is already sitting on an answer — everyone's browsing trail. The seven or eight places one person opened in a single evening are precisely the set they were weighing against each other. A big platform collects hundreds of millions of such trails.

So give every listing a name card: a short string of numbers the machine works out for itself. One rule only: listings that keep showing up in the same shopping trip get cards that sit close together; two listings picked at random get pushed apart. Run hundreds of millions of trails through that, and the cards that end up near each other belong to places real people actually compare.

It is a bit like inferring who is friends with whom from a pile of group photos. You never ask anyone; you just notice who keeps turning up in the same frame.

There is one extra move. If a trail ends in an actual booking, the booked place gets a say over the whole trail — every place seen along the way is nudged toward it. Because "finally chose it" carries far more weight than "clicked on it."

What about brand-new places?

A listing that just went up has no visitors and therefore no card. The fix is crude and effective: take a few nearby places of the same type and price, average their cards, and use that as a stand-in until the new listing has trails of its own.

What it costs

It can only repeat back what people already look at — a great place nobody has clicked is hard for it to surface, so the cold stay cold and the hot get hotter.

One line to remember

Similar listings are not "the ones that look alike," they are "the ones you'd take instead." And that second thing doesn't need defining — it is already sitting in millions of browsing trails. Pour the trails in and similarity surfaces on its own.

Want the mechanisms, notation and diagrams? → Switch to the deep read

In one line

This chapter makes exactly one big decision: don't define "similar" — let user sessions define it. It is the only problem in the book with no human labels. The training signal comes entirely from co-occurrence in the logs: an adapted word2vec skip-gram compresses every listing into a few dozen dimensions, and "similar" simply means "nearby vector." The engineering content is not in the model (the model is from 2013) but in three adaptations: treating the eventually booked listing as global context, adding same-market negatives to survive congregated search, and an attribute fallback for new listings.

Glossary

Listing: one bookable property on the platform. Market: a searchable geographic area, usually a city.
Session: one user's continuous stretch of browsing; a long enough pause ends it and starts a new one.
Co-occurrence: two listings appearing inside the same session. Every training signal in this chapter comes from it.
Embedding: compressing an ID into a short trainable vector. Closeness is measured by cosine similarity — the closer two vectors point, the nearer the value is to 1.
Self-supervised: no human annotation; labels are generated by the structure of the data itself — here, "clicked next to each other in one session."
skip-gram: the word2vec training scheme that uses a center item to predict the items in a window around it. That window is the sliding window.
Negative sampling: instead of scoring all several million candidates each step, draw a handful of random "counter-examples" to contrast against, which keeps training affordable.
ANN (approximate nearest neighbor): finding the closest few vectors among millions fast, trading a little recall for orders of magnitude of speed.
Collaborative filtering: recommending from behavioral co-occurrence ("people who viewed A also viewed B") rather than from item attributes.
Cold start: a new item or user has no history, so the model has nothing to work with.
CTR (click-through rate): clicks ÷ impressions — the headline online metric here.

Where it sits

This is the 8th of the ten case studies in Part II, and it mirrors the previous one. Ch8, ad click prediction, had labels ready-made and spent its effort on feature crossing and probability calibration; here there are no labels and almost no feature engineering, and all the effort goes into turning raw logs into training samples. Ch10, personalized news feed, returns to multi-objective supervised ranking. In the real world this is Airbnb's similar-listings carousel and e-commerce's "customers also viewed."

What the chapter is solving

The setting is concrete: a horizontal "similar listings" row on the listing detail page. A user who opened this listing is interested in the category but has not decided — this row determines whether they keep shopping on your site or bounce back to search and out. On a rental platform it is the second-biggest discovery surface after search itself.

Three constraints separate it from every earlier problem.

One: there are no labels. No table anywhere says "A is similar to B." Hand annotation fails on sheer count: pairing millions of listings is on the order of 10¹³ pairs — the notation just means "tens of trillions," which puts annotation out of reach entirely.

Two: attribute similarity is systematically wrong. Cosine over "same city + same price band + same room type" is ten lines of code, but it surfaces listings with nearby specs when the user wants listings that are substitutable. Same "two bedrooms, $120, city center," yet one is next to a subway entrance and the other is a twenty-minute climb. Photo quality, decor, the felt sense of value for money — the things people actually trade off mostly cannot be encoded in the attribute table.

Three: the scale forbids brute force. Airbnb has publicly described millions of active listings, while the render budget for this block of the detail page is typically tens of milliseconds — exact cosine against millions of vectors per request is hundreds of millions of multiply-adds, so it is off the table.

What happens if you skip it? The row fills with spec twins, its CTR looks like random placement, and users go back to search and start over.

The core, explained

1. Framing it as ML: representation learning, not classification

The chapter does not train a binary classifier that takes A and B and outputs "alike or not." It learns one vector per listing and measures similarity by cosine. Two payoffs: compute the vectors once and any pair on the site becomes queryable, and several downstream surfaces (detail-page recommendations, search retrieval) reuse the same representation.

Where does the training signal come from? One assumption carries the whole chapter: listings clicked within the same session are, in the user's head, interchangeable candidates. That hands the definition of "similar" from the product manager to user behavior, so what gets learned is behavioral substitutability, not attribute resemblance.

2. Cutting logs into training samples (this is the real work)

This step looks like plumbing and is the easiest place to ruin the model. The book's treatment:

Segment sessions: split a user's click stream wherever inactivity exceeds about 30 minutes.
Drop misclicks: clicks with very short dwell time (say under 30 seconds) are treated as slips and removed.
Drop trivial sessions: a session with a single click carries no co-occurrence at all.
Drop bot traffic: crawlers string together completely unrelated listings into long sequences.

Why do these thresholds matter? A session that wasn't cut cleanly splices "I browsed Paris, then two hours later switched to Tokyo" into one sentence, and the model duly learns that Paris resembles Tokyo. Garbage in, garbage out is literal here.

The scale is worth remembering: in the KDD 2018 paper, Airbnb reports training 32-dimensional listing embeddings for roughly 4.5 million listings from over 800 million search click sessions. 32 dimensions — not 512, not 1024 — because what's wanted is the coarse substitutability structure; more dimensions overfit to noise on long-tail listings and multiply memory and query cost.

3. Running skip-gram over listings

Swap words for listings and sentences for sessions and word2vec's skip-gram transfers unchanged: a sliding window takes a center listing plus the context listings around it, and training pushes the dot product of same-window vectors up and the dot product with randomly drawn listings down.

In plain terms, two motions: pull the same window together, push random draws apart. Why "random draws" instead of comparing against all 4.5 million listings? Because that would require a 4.5-million-term normalization at every step, which blows up training cost — that is the only reason negative sampling exists.

Sessions are cut into sliding windows; center and context vectors are pulled together while random negatives are pushed apart. If the session ends in a booking, the booked listing appears as context in every window.

4. The two adaptations you cannot skip

Port word2vec over unchanged and you get a model that runs but is useless. The two adaptations in the book are the most valuable part of the chapter — and the part interviewers push on.

Adaptation one: treat the booking as global context. A click is a weak signal — it only means "took a look." A booking is a strong one: real money changed hands. So for any session that ends in a booking, the booked listing is added to every sliding window of that session, wherever the window happens to be. The effect is that every vector along the trail leans toward the listing that actually converted, encoding not just "seen together" but "seen together, and this one won."

Adaptation two: add same-market negatives. This one is subtler. Search is congregated: a session basically stays inside one city. So positives in a window are automatically same-city, while site-wide random negatives almost certainly come from other cities. The model spots a shortcut: just learn to tell cities apart and the loss goes down. What you get is a geographic clustering map with each city an undifferentiated blob — and "which listing inside this city substitutes for which" is the only thing the product needed.

The fix is plain: on top of the site-wide random negatives, draw a second set of negatives from the same market. Now "same city" no longer lowers the loss, and the model is forced to find structure inside the city.

Left: with site-wide negatives, separating cities is the cheapest solution and the embedding degenerates into geographic clusters. Right: same-market negatives remove that shortcut, forcing the model to learn substitutability inside a city.

5. Cold start and online serving

Cold start is the structural weakness here: a listing that just went live has no sessions and therefore no co-occurrence. The book adopts Airbnb's attribute fallback — take the geographically nearest few listings (say 3) of the same room type and price bucket and average their vectors as the initial value, replacing it once the listing accumulates sessions of its own.

Serving is the classic "heavy offline, light online" shape: embeddings are retrained offline daily (substitutability does not drift hourly the way ad inventory does), and online you either look up a precomputed top-k or query an ANN index.

Training runs as a daily offline batch. Online there are two paths: precomputed top-k for the lowest possible latency, or an ANN index for the flexibility of filtering by dates and price at query time.

6. Evaluating a model with no right answer

With no ground truth, offline metrics can only be proxies you invent. The book's move is to use converted sessions as the yardstick: for a session that ended in booking listing X, at every click use the current listing's vector to retrieve candidates and check X's rank — if the embedding is good, the closer to booking, the higher X ranks. That curve compares training configurations without shipping. It remains a proxy, though; the real verdict is an online A/B on the row's CTR and on conversions that start from it.

Key trade-offs

Table 1 · How to define "similar" — the last column is what interviews are listening for

Approach	Signal	Captures substitutability?	Cold start	When to pick it
Attribute rules	hand-written filters	No — returns spec twins	Not an issue	v1, or as a fallback and filter layer
Content-feature cosine	attributes / image-text vectors	Weak, only "looks alike"	Good	New platforms with thin behavioral data
Collaborative filtering	long-run user×item interaction	Yes, but skews to long-term taste	Poor	Dense interaction with returning users
Session co-occurrence embeddings	click sequence within one session	Yes — it captures this comparison	Poor, needs attribute fallback	This chapter: in-session decisions, short-lived intent, huge logs
Supervised two-tower	constructed positive/negative pairs	Yes, and business goals can be injected	Medium	Mature labels and training infra, multi-objective needs

Table 2 · How to query online: latency, freshness and flexibility

Approach	Latency	Freshness / flexibility	Cost	Fits
Precomputed top-k	Lowest, one KV lookup	Poor: new vectors force a full recompute; no query-time filters	Storage for compute, predictable	Fixed modules whose results don't vary per request
Online ANN index	Low, milliseconds	Good: incremental inserts, filter by date / price	Index resident in memory	This chapter and most production systems
Exact brute force	Unacceptable	Best	Hundreds of millions of multiply-adds per request	Offline evaluation and small canaries only

One more question interviewers like: the mix of negatives. Site-wide random negatives give global separation, same-market negatives give local resolution, and you want both — keep only the same-market ones and vectors across markets lose comparability.

Why it matters / in real systems

The shape generalizes well beyond rentals: anywhere you have no similarity labels but plenty of behavioral logs — "customers also viewed" in e-commerce, "similar artists" in music, "similar jobs" on job boards. The test is one sentence: is the similarity you want attribute resemblance, or behavioral substitutability? Only the second needs this chapter.

Three near-certain interview probes: why not attribute cosine, why congregated search wrecks the embedding and how to fix it (the question that separates "read it" from "understood it"), and what to do about cold start.

Industry evidence · these claims are the companies' and projects' own, not the book's

Airbnb is the prototype for this chapter. In the KDD 2018 paper Real-time Personalization using Embeddings for Search Ranking at Airbnb, Grbovic and Cheng report training 32-dimensional listing embeddings for roughly 4.5 million listings from over 800 million search click sessions, with adaptations for treating the booked listing as global context and for same-market negative sampling; Airbnb's engineering blog subsequently reported roughly a 21% CTR lift on the similar-listings module. (Source: Grbovic & Cheng, KDD 2018; Airbnb engineering blog — those domains are unreachable from this site's build environment, so the citation is text-only.)
Spotify · Annoy (open-source ANN library) states the case for approximate retrieval in its own README: it is "a C++ library with Python bindings to search for points in space that are close to a given query point," and on motivation — "We use it at Spotify for music recommendations. After running matrix factorization algorithms, every user/item can be represented as a vector in f-dimensional space," where "We have many millions of tracks in a high-dimensional space, so memory usage is a prime concern." The index is a read-only memory-mapped file "so that many processes may share the same data." spotify/annoy · README ↗
Meta · Faiss states the accuracy-for-scale trade most bluntly: it is "a library for efficient similarity search and clustering of dense vectors," and the compressed-code methods do not keep the original vectors, which "generally comes at the cost of a less precise search but these methods can scale to billions of vectors in main memory on a single server." That sentence is the engineering basis for "brute force is off the table" in Table 2. facebookresearch/faiss · README ↗

Pitfalls and debates

Treating "similar" as "looks alike." The chapter's first lesson and the most common product misreading: nobody compares two spec twins.
Sessions cut badly. Cross-city, cross-date and bot traffic merged into one sequence produce absurd neighbors — and offline metrics barely show it.
Forgetting same-market negatives. The sneakiest trap: the embedding looks sensible (cities do cluster) while online clicks don't move, because the within-city ordering the module needs was never learned.
Popularity bias. Hot listings appear in countless sessions, get dragged toward the center of the space and become everyone's neighbor. Downsample by frequency.
The cold-start fallback's side effect. A new listing's vector is the mean of its neighbors, so it permanently resembles its neighbors and never acquires character — it's a temporary value to retire fast, not a resting state.
The feedback loop. Whatever the module shows is what users see, and the next round of training data looks more like it. Without exploration traffic, long-tail listings never enter anyone's session.
Taking offline metrics as the verdict. On a task with no ground truth, "better offline, worse online" is routine.
Period limits. This is 2018 engineering around a 2013 model; the field has since moved to sequence models, two-tower retrieval and graph embeddings. But "use session co-occurrence as the label" was never overturned — it became the default starting point for retrieval layers everywhere.

Takeaways

1. The pivot is not defining "similar" and letting sessions define it: listings clicked in one session are each other's substitutes.

2. That makes it the book's only self-supervised problem — labels come free from co-occurrence, with almost no feature engineering.

3. The framing is representation learning, not classification: one vector per listing (Airbnb used 32 dims), similarity by cosine.

4. The mechanism is skip-gram with negative sampling: pull the same window together, push random negatives apart; negative sampling exists only to avoid normalizing over millions of candidates.

5. Adaptation one: make the booked listing global context, so the whole trail leans toward the real conversion — clicks are weak, bookings are strong.

6. Adaptation two: add same-market negatives, or "tell cities apart" becomes the shortcut and the embedding degenerates into geographic clusters with no within-city structure.

7. Cold start uses an attribute fallback — the mean vector of the nearest same-type, same-price listings; serving is daily offline retraining plus online ANN retrieval.

8. Evaluation has no right answer: offline, use "does the booked listing rank higher as the session progresses" as a proxy; the verdict is still online A/B on CTR and conversion.