IBM's Apriori mined what shoppers buy together by pruning impossible candidates

Retailers wanted to know which products are bought together, but the number of possible item combinations exploded exponentially with the number of SKUs.

Apriori, published in 1994, exploits a property: any superset of an infrequent item-set must itself be infrequent. It counts single items, keeps frequent ones, grows them into pairs, and repeats, so it never counts a candidate whose parent already failed.

The trick converts a search that quickly becomes unmanageable into one that touches only the small frontier of frequent sets. It turned market-basket analysis into a practical database query.

If a set is rare, every superset of it is too

Downward closure prunes the search before it grows, so run time tracks frequent sets, not all sets.

A database scan per level keeps memory bounded to candidate sets.

It gives exact frequent sets, not a heuristic or a sampled approximation.

The same pruning generalises to sequence and pattern mining beyond baskets.

Before searching a huge space, look for a monotonic property that lets you discard whole branches at once. A rule that rules out a region shrinks the hunt from exponential to linear.

Apriori became the canonical association-rule algorithm and a standard lesson in data mining. It seeded the field that powers recommendation, assortment and cross-sell analysis, and later fpgrowth and other methods that cut its scans.