Filtered ANN

The metadata filter is applied first to restrict the candidate set, and the ANN search is then executed only over the qualifying vectors.

• Mechanism: A bitmap or list of valid IDs is generated from the metadata index before the vector index is traversed.
• Primary Risk: If the filter is highly selective, the ANN graph may become disconnected, causing the greedy search to get trapped in local minima and miss true neighbors.
• Best For: Broad filters that still leave a large, well-connected candidate pool.

The ANN search is executed first to retrieve a candidate set based purely on vector similarity, and the metadata filter is applied afterward to remove non-qualifying results.

• Mechanism: The system over-fetches a larger topK of ANN results and then discards those failing the predicate.
• Primary Risk: If the filter is highly restrictive, the final result set may contain fewer than K items, or even zero results, because the ANN search was blind to the metadata.
• Best For: Scenarios where vector similarity is the dominant signal and the filter is a loose refinement.

A graph traversal modification where the search algorithm skips nodes that fail the metadata predicate during the greedy walk, rather than applying the filter before or after.

• Mechanism: The search maintains the standard candidate and visited lists but only expands neighbors that satisfy the filter condition.
• Advantage: Avoids the disconnected graph problem of pre-filtering by allowing the search to route through invalid nodes to reach valid ones.
• Tradeoff: Requires the filter evaluation to be extremely fast, as it is called on every visited node during the traversal.

A multi-part index that partitions the vector space by a high-cardinality metadata field, creating separate sub-indices that are searched in parallel.

• Mechanism: A top-level mapping routes the query to only the relevant partitions based on the filter key, and a standard ANN search runs within each selected partition.
• Advantage: Provides strong isolation and predictable performance when the filter key is known at query time.
• Tradeoff: Memory overhead increases linearly with the number of partitions, and cross-partition queries require a scatter-gather pattern.

A hybrid acceleration technique that uses compressed bitmaps to represent set membership for metadata attributes, enabling fast intersection with ANN candidate sets.

• Mechanism: Roaring Bitmaps or similar compressed data structures store the document IDs for each filter value. The ANN search produces a candidate ID set, and a bitwise AND operation applies the filter.
• Advantage: CPU-efficient filtering that operates in milliseconds even on massive datasets.
• Best For: Combining multiple discrete filters (tags, categories, status) with vector search.

A dynamic strategy that analyzes the selectivity of the incoming filter at query time and chooses between pre-filtering and post-filtering to optimize the recall-latency tradeoff.

• Mechanism: A cost-based optimizer estimates the cardinality of the filter. If the filter matches >X% of the dataset, pre-filtering is used; otherwise, the system falls back to post-filtering with an adjusted topK.
• Advantage: Prevents the worst-case failure modes of both pure strategies.
• Requirement: Accurate cardinality estimation statistics on the metadata index.

A constrained search strategy where metadata filters are applied before the ANN search. The candidate set is restricted to only vectors matching the filter criteria, and then a standard ANN algorithm runs on this subset.

• Pros: Guarantees all results match the filter; simple to implement.
• Cons: Catastrophic recall loss if the filter is highly selective, as the graph may become disconnected or the search may have too few candidates.
• Best for: Low-selectivity filters (e.g., region=US).

A strategy where the ANN search runs first on the full dataset, retrieving a top-K candidate set, and then metadata filters are applied afterward to remove non-matching vectors.

• Pros: Preserves graph connectivity and high recall from the ANN index.
• Cons: May return fewer than K results if the filter is highly selective, as many top candidates are discarded.
• Mitigation: Oversample by fetching K * overshoot_factor candidates before filtering.

An advanced approach that integrates the vector index and the metadata filter into a single unified data structure. The search traversal respects both vector similarity and filter constraints simultaneously.

• Mechanism: Often implemented by storing metadata in graph nodes and pruning edges that violate the filter during greedy traversal.
• Benefit: Avoids the recall cliff of pre-filtering and the result starvation of post-filtering.
• Tradeoff: Increased index complexity and memory overhead.

The fraction of the total dataset that matches a given metadata predicate. It is the critical variable determining which filtering strategy is viable.

• High Selectivity (<1% match): Pre-filtering risks disconnected graphs. Post-filtering with aggressive oversampling is often safer.
• Low Selectivity (>10% match): Pre-filtering works well, as the remaining subgraph is large enough for effective ANN traversal.
• Measurement: selectivity = |filtered_set| / |total_dataset|

A secondary data structure used alongside the vector index to accelerate pre-filtering. A bitmap represents set membership for each filterable attribute value, enabling fast intersection of multiple filter conditions.

• Usage: Compute the bitmap of matching IDs from metadata, then restrict ANN search to only those IDs.
• Optimization: Roaring Bitmaps provide compressed, cache-friendly set operations.
• Limitation: Still suffers from the disconnected graph problem in high-selectivity scenarios.

An extension of the HNSW algorithm that incorporates metadata directly into the graph traversal. Each node stores its filter attributes, and the search only follows edges to nodes satisfying the query filter.

• Advantage: Maintains graph connectivity because edges to filtered-out nodes are simply not traversed, rather than removing nodes entirely.
• Implementation: Available in vector databases like Weaviate and Milvus as a native filtered search capability.
• Tradeoff: Slightly slower traversal due to per-hop filter evaluation.