Concurrent Updates and Queries on a Graph-Based Vector Index

Hao Zhang, Hongyi Zhang

Summary

We will build an in-memory graph-based approximate nearest neighbor index from scratch in C++ that supports concurrent inserts, deletes, and searches on a single shared Vamana graph, and study how these operations scale on multicore shared-memory CPUs. We will compare synchronization schemes of different granularity and three published ways of repairing the graph after a delete, taken from FreshDiskANN, IP-DiskANN, and CleANN, measuring both recall and throughput.

Reports

• Proposal (Nov 9)
• Milestone report (Nov 23)
• Final report (Dec 10)

Schedule

• Week 1 (Nov 9-15): datasets, ground truth, sequential index
• Week 2 (Nov 16-22): global and per-node locks, workload generator, first deletion strategy, milestone report
• Week 3 (Nov 23-29): remaining two deletion strategies
• Week 4 (Nov 30-Dec 6): scaling experiments and analysis
• Week 5 (Dec 7-11): final report and poster