Parent

• Parent issue: Milestone 1 - Shardlake Post-Prototype Roadmap #5

Goal

Improve vector partitioning to reduce query fan-out and improve latency.

Detailed tasks

• 2.1 Implement vector clustering
  • Use k-means clustering to partition vectors.
  • Train centroids on a sample subset.
  • Store centroid metadata.
• 2.2 Centroid routing logic
  • Compute nearest centroids at query time.
  • Route the query to the top-N shards.
• 2.3 Shard metadata format
  • Ensure each shard includes:
    • centroid_id
    • vector_count
    • index_type
    • file_location
• 2.4 Query fan-out policy
  • Implement configurable parameters for:
    • candidate_centroids
    • candidate_shards
    • max_vectors_per_shard
• 2.5 Partition evaluation harness
  • Add the CLI command shardlake evaluate-partitioning.
  • Report:
    • shard size distribution
    • routing accuracy
    • recall impact
    • shard hotness

Definition of done

• Shards are assigned by a repeatable clustering strategy.
• Query routing targets the most relevant shards instead of broadcasting everywhere.
• Partition quality can be measured through a dedicated evaluation command.

Child issue breakdown

• 2.1 - Implement repeatable vector clustering #38 2.1 - Implement repeatable vector clustering
• 2.2 - Implement query-time centroid shard routing #40 2.2 - Implement query-time centroid shard routing
• 2.3 - Define shard routing metadata format #39 2.3 - Define shard routing metadata format
• 2.4 - Add configurable query fan-out policy #41 2.4 - Add configurable query fan-out policy
• 2.5 - Add partition evaluation CLI and reporting #42 2.5 - Add partition evaluation CLI and reporting

Dependency summary

• 2.2 - Implement query-time centroid shard routing #40 depends on 2.1 - Implement repeatable vector clustering #38 and 2.3 - Define shard routing metadata format #39.
• 2.4 - Add configurable query fan-out policy #41 depends on 2.2 - Implement query-time centroid shard routing #40.
• 2.5 - Add partition evaluation CLI and reporting #42 depends on 2.2 - Implement query-time centroid shard routing #40.

Dependency graph

#38   #39
  \   /
   #40
   /   \\
#41   #42