What is a linear scan?

A linear scan checks every single item in a collection one at a time, comparing each one individually against whatever’s being searched for, and its cost grows directly in proportion to how many items there are — a pattern that stands in sharp contrast to the logarithmic-like scaling HNSW is built specifically to achieve instead.

Why is a linear scan considered the simplest possible way to search a collection?

A linear scan makes no assumptions about how the data is organized and requires no preparation ahead of time — it simply walks through every item in order, checking each one, until either the target is found or every item has been checked. This simplicity is exactly its appeal: there’s no index to build, no structure to maintain, and no risk of the search producing an approximate or incomplete result, since checking literally everything guarantees that nothing gets missed. The cost of this guarantee is that a linear scan’s running time grows directly in proportion to the size of the collection, doubling the collection roughly doubles the time a linear scan takes, which is a far less favorable growth pattern than the logarithmic time complexity covered elsewhere in this glossary.

How does a linear scan relate directly to the brute-force nearest-neighbor search this site describes HNSW as an alternative to?

Brute-force nearest-neighbor search, covered in this site’s early coverage of why nearest-neighbor search can’t just compare a query against every vector, is precisely a linear scan applied to the specific problem of finding the closest vectors to a query: it computes the distance between the query and every single stored vector, one at a time, guaranteeing an exact answer but at a cost that grows directly with the size of the dataset. HNSW‘s entire layered graph structure, covered throughout this site’s coverage of building the algorithm from scratch, exists specifically to avoid this linear-scan cost, accepting a small amount of approximation in exchange for search times that scale far more favorably as a dataset grows.

Is a linear scan ever still the right choice, even with faster alternatives like HNSW available?

For a genuinely small dataset, a linear scan’s simplicity and exact-answer guarantee can outweigh the benefit of a more complex structure like HNSW, since the actual time cost of scanning a small number of vectors directly may be negligible, and building and maintaining a graph structure introduces real overhead and complexity that isn’t worth paying for such a small workload. A linear scan also remains the standard for computing ground-truth results used to evaluate recall, covered throughout this site’s coverage of evaluation and benchmarking, since its guaranteed exactness is exactly what’s needed to check whether an approximate method like HNSW is actually finding the true nearest neighbors.

Understanding a linear scan’s simple, exact, but slowly-scaling behavior clarifies exactly what trade-off HNSW is making by replacing it with a more complex, approximate, but far faster-scaling structure. From here, the pages on logarithmic time complexity and on approximation algorithms cover the two ideas that explain precisely why that trade-off is usually worthwhile.