Visual Search
dataset
- A query image
- (n-1) negative images
- A positive image, i.e., the image most similar to the query image.
- The index label of the positive image among all the images.
build dataset
- human judgement: humans annotate the most similar image
- user interaction
- noisy
- sparse: may not have click data available for lots of the images
- generate similar images
Offline metrics
Mean reciprocal rank (MRR)
MRR=1/m * sum(1/rank_i)
downside
- considers only the first relevant item and ignores other relevant items in the list, so it does not measure the precision and ranking quality of the full ranked list
Recall@k
recall@k= number of relevant items among the top k items in the output list / total relevant items
downside
- in search engines, the total number of relevant items can be very high, so the denominator ends up being too large.
Precision@k
Precision@k = number of relevant items among the top k items in the output list / k
downside
- This metric measures how precise the output lists are, but it doesn’t consider ranking quality
mAP
AP = sum of Precision@i for every relevant item at rank i / total relevant items
mAP = mean AP across all ranked lists
mAP is designed for binary relevance; in other words, it works well when each item is either relevant or irrelevant. For continuous relevance scores, nDCG is a better choice.
nDCG
rank = the position produced by the model’s ranking
rel = the true relevance of the item at that position
Visual Search at Pinterest
duplicate image
- A new image is uploaded, and we want to know whether it is a duplicate of an existing image
- Once the embedding has been generated, convert the embedding into LSH terms
- embedding = [0.12, -0.44, 0.07, …, 0.31]
- LSH terms = {term_17, term_203, term_881, term_915, …}
- Generate a set of duplicate candidates: use the new image’s LSH terms to fetch a batch of corresponding images, compare which images share the most LSH terms with the new image, and sort them from most to least
- Use a TensorFlow classifier to make the fine-grained decision; images whose score exceeds a certain threshold are considered duplicates and are placed into the existing cluster
cluster
- Each cluster represents a group of duplicate images
- every cluster has a cluster head, i.e., the representative image of the cluster
- Two relationships are maintained: Image → canonical image, and canonical image → cluster members
manas(search basic)
Indexing
- doc: Each manas pin is treated as a doc, which contains matching terms and properties
- matching terms: used for retrieval. E.g., red; dress
- properties: used for filtering and scoring. E.g., language = en; quality_score = 0.9
- posting: Each posting records the internal doc ID and a payload.
- inverted index: term → posting list
- There are two encoding/storage methods
- dense posting list: suitable for very common terms, e.g., red
- split posting list
- Forward index: internal_doc_id → actual document
- Different applications have different pins, i.e., manas docs. For example, regular visual search corresponds to searchable pins, and ads correspond to searchable Ads. They are unified into manas docs
- Each application has its own partitioner, which splits manas docs into different partitions
- The index builder turns the docs in each partition into an index segment
Serving
- A corpus can be understood as the set of images searchable by an application. For example, Corpus A = organic Pins, Corpus B = shopping products, Corpus C = ads
- Query Understanding turns the user query into a detailed, executable search plan
- Blender is responsible for deciding which corpora to search, and hands off to the root of those corpora
- A leaf is a serving machine/node; a leaf can consist of one or more index segments
- The root collects the results returned by each leaf, merges them, and reranks
Leaf
A leaf corresponds to one node. After the Operator layer finishes finding candidates, it hands them off to the Model Runner to perform ML scoring, and then exposes an API to the Root
HNSW: Real-time with Embedding
- Every time an embedding is produced, that event goes into Kafka
- The Leaf shard consumes these write events from Kafka and writes them into its own realtime segment
- The Realtime Segment is a small in-memory index.
- Realtime Embedding Index: stores doc_id → embedding
- Realtime HNSW Graph: inserts the new embedding into the HNSW graph, supporting ANN search
- After some time, the Realtime Segment becomes a sealed realtime segment and no longer accepts writes
- A Flush operation writes the sealed segment in memory to SSD, turning it into a Static Segment. It is no longer modified frequently, making it suitable for serving.
Operation
- deletion: To delete a doc, add an in-memory deletion marker to it. During serving, if this doc is found, it gets filtered out. This is because directly deleting a node in the HNSW graph is fairly troublesome and can break the graph structure.
- update: delete old+add new
- Compaction: If there are too many static segments, multiple small static segments are merged into a larger static segment. This is also when the actual deletion is completed
ANN
Given a query embedding, quickly find the most similar top-K among a massive number of candidate embeddings. Because there are too many candidates, it isn’t feasible to compute the similarity between the query and every candidate, so a bit of accuracy is traded for speed
HNSW
HNSW is an ANN method. It organizes all embeddings into a graph, and then during search it walks along the graph to quickly find nearby points.
The HNSW index is essentially a multiple-layered sparse graph.
Each segment builds one HNSW graph.
- Each embedding is a node, and similar embeddings are connected by edges
- Stored using an adjacency list
- multiple-layered, similar to a skip list
- Upper layers: quickly jump to the approximate region
- Lower layers: finely search for the nearest neighbors
Inserting a new node
- Find the nodes similar to it, and first update the adjacency list
- First insert it into the base layer, connecting it to similar nodes
- Then insert it into the upper layers
Deleting a node Add an in-memory deletion marker; deleted nodes are filtered out during serving, and the actual deletion is left to compaction
HNSW Graph Compaction
Problem: when there are too many segments, retrieval becomes very slow
Add on Merger:
- Select the largest segment and reuse its HNSW graph
- Insert the embeddings of the other, smaller segments into it
- If there is a deleted node, directly modify its embedding to the embedding of the nearest alive node. For example, Node 5 → Embedding 4
- The cost is that deduplication is still needed after retrieval
Online Recall Monitoring
recall@K = |ANN topK ∩ exact KNN topK| / K
This computes global recall: each segment on each Leaf performs an HNSW search, returning a local top K; the root then aggregates the results to obtain a global top K.
ANN and exact KNN are run simultaneously only for a small number of sampled queries, in order to monitor the quality of the current realtime HNSW index.
Filtering
Streaming Filtering
Pinterest blog: hnsw streaming filters
A query is broken down into several parts: HNSW retrieval + Filters + Scorer + Collector
This streaming algorithm runs inside a single Leaf, applied to each of its local HNSW segments.
HNSW Iterator:
- Traverses the segment’s HNSW graph in order of approximate embedding distance. Similar in spirit to Prim’s algorithm
- visited set: which nodes have already been visited
- candidate set: nodes that haven’t been visited yet but are reachable, sorted by distance. dist is the distance from the query embedding to the node embedding
- Outputs a mini-batch each time
- Traverses the segment’s HNSW graph in order of approximate embedding distance. Similar in spirit to Prim’s algorithm
Filter:
- Checks metadata filters against this batch of candidates
- e.g., safe=true, language=en, country=US, category=fashion, is_shoppable=true
- Candidates that don’t pass the filter are discarded
Scorer:
- Scores the candidates that passed the filter
- Can be lightweight scoring, or can plug in a more complex ranking score
Collector:
- Puts the filtered and scored candidates into a result heap
- The heap maintains the current local top results
Repeat:
- If not enough valid results have been collected yet, the HNSW iterator continues traversal
- It fetches the next batch of candidates
- Continue filter → score → collect
Stopping condition:
- Even once the Top K nodes have already been collected, we still compare the dist(query, node) of the nearest unexplored node in the candidate set against the farthest distance in the result heap. If the unexplored nodes can’t improve the current result, we stop.
- Only nodes that satisfy the filter conditions are considered
- Production latency condition: stop once the time budget is reached, and return the current best valid results
- Even once the Top K nodes have already been collected, we still compare the dist(query, node) of the nearest unexplored node in the candidate set against the farthest distance in the result heap. If the unexplored nodes can’t improve the current result, we stop.
Merge:
- Each segment produces local results
- The Leaf merges the results from its own multiple segments
- The Root then merges the results from multiple Leaves
- The Blender then merges the results from multiple corpora
Shop the Look
The Shop the Look task: scene image → detect shoppable objects → retrieve similar products
Amazon
Bringing Multimodality to Amazon Visual Search System
It represents each product in the catalog as a fused vector of product image embedding + product title embedding, and builds a KNN/ANN index offline;
at online serving time, if the query has only an image, the query image embedding is used to search this multimodal catalog index.
- Scene decomposition (detection): given a scene, detect all shoppable regions
- Candidate retrieval (embedding): uses visual embeddings to retrieve visually similar products from a large shopping corpus.
Evaluation
Coverage: scene closeup volume How many scenes containing shoppable objects the user saw
Engagement total: product click-through volume How many products the user clicked on in total
Quality/rate: product click-through rate The proportion of products that get clicked after being shown
Human relevance: E2E Relevance@5 How similar the detected object is to its top-5 matched products
Scene decomposition
ResNeXt101-FasterRCNN + FPN
- The ResNeXt101 backbone extracts multi-level feature maps
- FPN turns these multi-level features into a feature pyramid
- The purpose of FPN is to give the features at every scale relatively strong semantic information
- RPN generates region proposals on the pyramid features
- RoIAlign extracts a fixed-size RoI feature for each proposal from the corresponding pyramid level
- The detection head performs classification + bbox regression on each RoI
- Outputs a category label + bounding box
Candidate Retrieval
Version 1: Pre-filtering: per-category index
Offline:
- Compute a visual embedding for each product image
- Assign a category to each product
- Using an in-house Google Product Taxonomy classifier
- Or using a merchant-provided category label
- Group products by category
- Build a separate nearest-neighbor index for each category
Online:
- The detector outputs the bbox + category label of the query object
- Compute a visual embedding for the query object crop
- Select the corresponding category index based on the predicted category
- Perform ANN retrieval only within that category index
Version 2: LSH ANN + metadata restrictions
- product image → visual embedding
- product embedding → LSH tokens
- inverted index:
- LSH token → product IDs
- metadata value → product IDs
- forward index:
- product ID → original visual embedding
- online:
- query object crop → visual embedding
- query embedding → LSH tokens
- query tokens + metadata restrictions form a tree-structured query
- inverted index retrieves matched-token candidates(ANN)
- exact embedding distance reranks candidates
Complete the Look
Input:
- scene image: a scene photo, e.g., an outfit / a room / a street-style shot
- product image: a candidate product, e.g., a pair of shoes / a bag / a chair
Output:
- A distance / score
- This score represents whether this product goes well with this scene
VPG
- Find real-world scenes that contain the query product / a similar product
- Extract other shoppable objects from the scene
Feature Storage
KV Store
full-image embedding The embedding of the whole image
object coordinates The position of each object in the image, e.g., bbox: x, y, w, h
object embedding The embedding of each detected object crop
Initial Backfill
- Use Spark to do offline batch processing: run all existing images through the object detector to identify objects
- Compute an embedding for each object and put it into the KV Store
Incremental updates
- For new images, use Flink to do near-real-time stream processing
Online Fallback
- Sometimes a user clicks on a new image, but Flink hasn’t finished processing it yet, so the KV Store doesn’t have this image
- The system falls back to online real-time computation
Reverse-STL
Use an object image to perform ANN, find similar objects, and then fetch the original images that those similar objects belong to
Forward-STL
- Perform object detection on top scene images
- Find matching product images for the other objects in the scene