advanced practice · coding problem
Cost a disk-resident search by I/O
Implement queryCost({hops, neighboursPerHop, cachedFraction, readLatencyUs, compareLatencyNs}) returning { randomReads, totalUs } rounded to 2 decimals. Every hop fetches neighboursPerHop nodes; a cachedFraction of them avoid the SSD. Comparisons cost compareLatencyNs each and happen for every fetched neighbour.
The mechanism
An in-memory graph index like HNSW is bounded by RAM, so at billion scale the index has to live on SSD — and then the cost model inverts: what matters is not comparisons but the number of random reads, because each one costs a hundred microseconds. DiskANN's answer is to keep compressed vectors in memory to guide the search and touch the SSD only for the few full-precision neighbourhoods it actually needs, so a query costs a handful of reads rather than a traversal's worth.
Expected evidence
With SSD reads at 100us, I/O dominates comparisons by orders of magnitude.
Try this drill in the practice workspace →
Hints when you need them
- randomReads = hops * neighboursPerHop * (1 - cachedFraction); do not round it away before costing it.
- Convert nanoseconds to microseconds before adding, or the comparison term vanishes.
Watch for these mistakes
- Carrying over in-memory intuition and optimising comparison count instead of I/O count
- Ignoring that SSD random-read latency, not bandwidth, sets the query floor
- Rebuilding the whole index for small update volumes rather than maintaining a delta
- Benchmarking with a warm page cache, which hides the disk cost entirely