microsoft / microsoft/DiskANN

[Question] StreamingMerge Entrypoint

Open
#355 3 comments 0 reactions 0 assignees View on GitHub
question
Dominant language
Rust
Stars
1.9k
Forks
454
Avg merge
3d 22h
Merged PRs (30d)
35

Description

Hi!

The FreshDiskANN paper outlines the StreamingMerge procedure. In combing through the codebase (main @ f8ef303), there doesn't appear to be a singular entrypoint that allows a caller to utilize the FreshDiskANN API contract without being aware of all the types of indices.

- `test_streaming_scenario.cpp` outlines how to build an in-memory index that supports inserts and deletes.
- `build_stitched_index.cpp` outlines how to merge indices
- `search_disk_index.cpp` demonstrates how to run a search across an index that is stored on disk.

Given a client that provides a memory budget and _no starting list of vectors_, my reading of the paper would indicate the following needs to be done in a wrapping class:

1. create an empty, streaming enabled, in-memory index that holds writes - this is outlined in `test_streaming_scenario.cpp` and is the only sink for insertions.
2. create an empty, SSD resident index, which is demonstrated by `build_disk_index.cpp`... this index would not have a true build phase as there is nothing to add.
3. once the mutable index in [1] is full, merge [1] and [2] using the routine outlined in `merge_shards` within disk_utils.h - during the merge process, we would have already created a new mutable in-memory index for any in-flight writes + deletes.
4. separately, maintain a list of deletions that are used for filtering within all live indices.

I would be happy to submit a patch that unifies the above in such a way that a caller can just create an Index and not have to worry about RO-TempIndex, RW-TempIndex and the SSD-Resident Index; however, I would like to confirm that my read on the current codebase is correct in that there is no singular entrypoint for this.

Contributor guide

Open the contributing guide

Research direction

Start by reading test_streaming_scenario.cpp, build_stitched_index.cpp, build_disk_index.cpp, search_disk_index.cpp, and the merge_shards routine in disk_utils.h. Trace how the mutable, SSD-resident, and deletion-filtering pieces interact, then confirm whether the existing code lacks a unified entrypoint and define the wrapper's completion criteria with maintainers.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
api, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.