MAVANN: Metadata-Aware Vector Approximate Nearest Neighbor

1. Introduction

2. Comparison with Traditional Filtering Approaches

2.1 Pre-Filtering

2.2 Post-Filtering

2.3 MAVANN's Novel Approach

3. Vector Structure in MAVANN

4. Phased Distance Metric Computation

4.1 Step 1: Metadata Segment Evaluation

4.2 Step 2: Full Vector Similarity Computation

5. Index Structure

5.1 Base Vector Representation

5.2 Metadata Segment Encoding

Dimension Allocation

5.3 Metadata Schema

Updating Metadata Schema

5.4 Hierarchical Metadata Routing Structure

Pseudo-metadata Nodes

Pseudo-root Node

5.5 Vector Extension and Indexing Process

Phase 1: Pseudo-metadata Structure Creation

Phase 2: Metadata Node Insertion

6. Query Processing

6.1 Pure Similarity Search

6.2 Metadata Filtering Queries

6.3 Query Vector Encoding Details

Equality Filter Encoding

Inequality Filter Encoding

7. Performance Considerations

8. Trade-offs and Considerations

9. Conclusion