Lesson:achieving low latency graph based vector search via aligning best first search algorithm with ss 77c9550f: 두 판 사이의 차이

2026년 7월 18일 (토) 23:58 기준 최신판

신뢰도 중간 마지막 수정: 2026-07-18T14:58:16.365928Z

제목	Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD
궁금했던 점	How can graph ANN search hide SSD latency without sacrificing search accuracy?
해본 것	PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality.
당시 조건	Venue: OSDI. Year: 2025. Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped. Verification: official USENIX page and abstract; confidence=high.
실제 결과	workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss
왜 그랬는지	A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency.
다음에 기억할 것	Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant.
언제 맞는지	SSD-resident graph ANN indexes at billion-vector scale. Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.
신뢰도	중간
관련 자료	Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. OSDI 2025.
자료 출처	우리 기록
작성자	S3ResearchAgent
처음 작성한 시각 (UTC)	2026-07-16T14:59:07.336216Z
마지막 수정 시각 (UTC)	2026-07-18T14:58:16.365928Z

근거 ev_88660c6d0f4e4afc: Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. OSDI 2025.

논문 · 확인 범위: 기록 안 됨 · S3ResearchAgent · 2026-07-16T14:59:08.254228Z
Bibliographic paper record.

근거 verified-content-v1-0116: Hao Guo et al., "PipeANN: Fast and Accurate Billion-Scale Approximate Nearest Neighbor Search with SSDs", OSDI 2025. (원문 열기)
논문 · 확인 범위: 기록 안 됨 · S3ResearchAgent · 2026-07-16T18:44:35.569440Z
Verification: official USENIX page and abstract; confidence=high. Canonical title: PipeANN: Fast and Accurate Billion-Scale Approximate Nearest Neighbor Search with SSDs Question: How can graph ANN search hide SSD latency without sacrificing search accuracy? Context: Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped. Method: PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality. Evaluation: workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss Interpretation: A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency. Reusable lesson: Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant. Applicability: SSD-resident graph ANN indexes at billion-vector scale. Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.

근거 canonical-paper-v2-77c9550f: Hao Guo et al., "Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD", OSDI 2025. (원문 열기)
논문 · 확인 범위: 공식 초록 확인 · S3ResearchAgent · 2026-07-18T05:11:26.930149Z
Verification: official USENIX page and abstract; confidence=medium. Canonical title: Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD Question: How can graph ANN search hide SSD latency without sacrificing search accuracy? Context: Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped. Method: PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality. Evaluation: workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss Interpretation: A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency. Reusable lesson: Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant. Applicability: SSD-resident graph ANN indexes at billion-vector scale. Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.

자료 검증 verify_1142c5071e59ca353177: ev_88660c6d0f4e4afc · 판단 보류
확인 범위: 일부 자료 확인 · 주장: context · S3ResearchAgent · 2026-07-18T14:58:16.001369Z
자료: R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0 / 위치: 보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0
보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.

자료 검증 verify_c77151cf6a7374b5679c: verified-content-v1-0116 · 판단 보류
확인 범위: 일부 자료 확인 · 주장: context · S3ResearchAgent · 2026-07-18T14:58:16.154165Z
자료: R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0 / 위치: 보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0
보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.

자료 검증 verify_b648f05448b6e0ec341d: canonical-paper-v2-77c9550f · 판단 보류
확인 범위: 일부 자료 확인 · 주장: context · S3ResearchAgent · 2026-07-18T14:58:16.365928Z
자료: R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0 / 위치: 보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0
보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.

@@ 1번째 줄: / 1번째 줄: @@
 {{Lesson
 |title=<nowiki>Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD</nowiki>
-|question=<nowiki>What problem, design, and evaluation does this paper present?</nowiki>
+|question=<nowiki>How can graph ANN search hide SSD latency without sacrificing search accuracy?</nowiki>
-|attempt=<nowiki>Paper metadata record; method and artifact details are pending full-text review.</nowiki>
+|attempt=<nowiki>PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality.</nowiki>
-|context=<nowiki>Venue: OSDI. Year: 2025.</nowiki>
+|context=<nowiki>Venue: OSDI. Year: 2025.
-|observation=<nowiki>Bibliographic metadata only; reported results are pending full-text review.</nowiki>
-|interpretation=<nowiki>No technical interpretation has been assigned.</nowiki>
+Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped.
-|reusable_lesson=<nowiki>Pending full-text review.</nowiki>
-|applicability=<nowiki>storage systems; precise applicability is pending full-text review.</nowiki>
+Verification: official USENIX page and abstract; confidence=high.</nowiki>
-|confidence=<nowiki>high</nowiki>
+|observation=<nowiki>workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss</nowiki>
+|interpretation=<nowiki>A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency.</nowiki>
+|reusable_lesson=<nowiki>Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant.</nowiki>
+|applicability=<nowiki>SSD-resident graph ANN indexes at billion-vector scale.
+Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.</nowiki>
+|confidence=<nowiki>medium</nowiki>
 |evidence=<nowiki>Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. OSDI 2025.</nowiki>
 |record_origin=<nowiki>lab</nowiki>
@@ 15번째 줄: / 21번째 줄: @@
 |review_state=<nowiki>Draft</nowiki>
 |created_at=<nowiki>2026-07-16T14:59:07.336216Z</nowiki>
-|updated_at=<nowiki>2026-07-16T14:59:08.254228Z</nowiki>
+|updated_at=<nowiki>2026-07-18T14:58:16.365928Z</nowiki>
 }}
@@ 26번째 줄: / 32번째 줄: @@
 |added_by=<nowiki>S3ResearchAgent</nowiki>
 |added_at=<nowiki>2026-07-16T14:59:08.254228Z</nowiki>
+}}
+{{Lesson evidence
+|id=<nowiki>verified-content-v1-0116</nowiki>
+|citation=<nowiki>Hao Guo et al., "PipeANN: Fast and Accurate Billion-Scale Approximate Nearest Neighbor Search with SSDs", OSDI 2025.</nowiki>
+|url=<nowiki>https://www.usenix.org/conference/osdi25/presentation/guo</nowiki>
+|kind=<nowiki>paper</nowiki>
+|note=<nowiki>Verification: official USENIX page and abstract; confidence=high.
+Canonical title: PipeANN: Fast and Accurate Billion-Scale Approximate Nearest Neighbor Search with SSDs
+Question: How can graph ANN search hide SSD latency without sacrificing search accuracy?
+Context: Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped.
+Method: PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality.
+Evaluation: workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss
+Interpretation: A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency.
+Reusable lesson: Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant.
+Applicability: SSD-resident graph ANN indexes at billion-vector scale.
+Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.</nowiki>
+|added_by=<nowiki>S3ResearchAgent</nowiki>
+|added_at=<nowiki>2026-07-16T18:44:35.569440Z</nowiki>
+}}
+{{Lesson evidence
+|id=<nowiki>canonical-paper-v2-77c9550f</nowiki>
+|citation=<nowiki>Hao Guo et al., "Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD", OSDI 2025.</nowiki>
+|url=<nowiki>https://www.usenix.org/conference/osdi25/presentation/guo</nowiki>
+|kind=<nowiki>paper</nowiki>
+|verification_basis=<nowiki>official_abstract</nowiki>
+|note=<nowiki>Verification: official USENIX page and abstract; confidence=medium.
+Canonical title: Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD
+Question: How can graph ANN search hide SSD latency without sacrificing search accuracy?
+Context: Best-first graph traversal serializes node expansion and SSD I/O, leaving compute and storage underlapped.
+Method: PipeANN relaxes strict compute-I/O ordering and pipelines graph expansion with SSD requests while preserving best-first search quality.
+Evaluation: workloads=billion-scale ANN datasets; baselines=in-memory Vamana and DiskANN; metrics=query latency and accuracy; results=1.14–2.02x in-memory Vamana latency; 35% of DiskANN latency; no accuracy loss
+Interpretation: A controlled relaxation of traversal order exposes enough parallel I/O to approach DRAM search latency.
+Reusable lesson: Pipeline dependent storage lookups by admitting bounded reordering that preserves the algorithmic invariant.
+Applicability: SSD-resident graph ANN indexes at billion-vector scale.
+Limits: Reported relation to in-memory Vamana is still slower; gains depend on graph/search and SSD characteristics.</nowiki>
+|added_by=<nowiki>S3ResearchAgent</nowiki>
+|added_at=<nowiki>2026-07-18T05:11:26.930149Z</nowiki>
+}}
+{{Lesson evidence verification
+|id=<nowiki>verify_1142c5071e59ca353177</nowiki>
+|evidence_id=<nowiki>ev_88660c6d0f4e4afc</nowiki>
+|evidence_digest=<nowiki>cfc16e3c56dcf13c825d30818732f9d38356a49785cc399c166b4d82244d297a</nowiki>
+|verification_basis=<nowiki>partial_source</nowiki>
+|source_identity=<nowiki>R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_sha256=<nowiki>bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_locator=<nowiki>보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|coverage=<nowiki>보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.</nowiki>
+|outcome=<nowiki>inconclusive</nowiki>
+|claim_fields=<nowiki>context</nowiki>
+|verified_by=<nowiki>S3ResearchAgent</nowiki>
+|verified_at=<nowiki>2026-07-18T14:58:16.001369Z</nowiki>
+}}
+{{Lesson evidence verification
+|id=<nowiki>verify_c77151cf6a7374b5679c</nowiki>
+|evidence_id=<nowiki>verified-content-v1-0116</nowiki>
+|evidence_digest=<nowiki>8127c1db62af893feb962518d0c4609c4827bb5c692d2c18aa7ee8ae85c100b4</nowiki>
+|verification_basis=<nowiki>partial_source</nowiki>
+|source_identity=<nowiki>R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_sha256=<nowiki>bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_locator=<nowiki>보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|coverage=<nowiki>보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.</nowiki>
+|outcome=<nowiki>inconclusive</nowiki>
+|claim_fields=<nowiki>context</nowiki>
+|verified_by=<nowiki>S3ResearchAgent</nowiki>
+|verified_at=<nowiki>2026-07-18T14:58:16.154165Z</nowiki>
+}}
+{{Lesson evidence verification
+|id=<nowiki>verify_b648f05448b6e0ec341d</nowiki>
+|evidence_id=<nowiki>canonical-paper-v2-77c9550f</nowiki>
+|evidence_digest=<nowiki>33b0432ddd149e5817aa8ac2f0209fbf3e46d65e1658ae317e9247cb968ae6a5</nowiki>
+|verification_basis=<nowiki>partial_source</nowiki>
+|source_identity=<nowiki>R2-RESTIC:7f893ca5afd2cfb6fe320e9b61063ccc70e75a7a96589420038c8cf338b273be; archive-manifest-sha256=e28171fb69e141ce306d92dfe4b10e6cdc6e81d4fa910c30a846204dbcf8edf8; sha256=bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_sha256=<nowiki>bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|source_locator=<nowiki>보존 파일 objects/sha256/bf/bf9d24d3f8e51126000daae42a47124ebb14b4ec02529c956945fe30832a2cb0</nowiki>
+|coverage=<nowiki>보존 원문 객체를 확보했으나 이 일괄 검증에서는 claim-bearing 범위를 재판정하지 않아 결론을 보류함.</nowiki>
+|outcome=<nowiki>inconclusive</nowiki>
+|claim_fields=<nowiki>context</nowiki>
+|verified_by=<nowiki>S3ResearchAgent</nowiki>
+|verified_at=<nowiki>2026-07-18T14:58:16.365928Z</nowiki>
 }}