Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Triangle inequality — where it appears

That going directly never costs more than going by way of a third point, which every structure indexing by distance prunes on and a log-odds score need not obey. Every structure indexing by distance prunes on it, so where it fails the index returns fewer answers than there are and reports no error at all.

Named by 8 essays across 3 fields — each of them below, with the objects they name alongside it.

acgtacgtseen ->0313303113033130a gap of k characters costs 2krows: expected · columns: seen · unit: bitslinear gaps

A cost that is not one

The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.

tables · Cost pairs where the two disagreerestricted · unrestrictedab → bca3 against 2ac → cba3 against 2ba → acb3 against 2bc → cab3 against 2ca → abc3 against 2triples the restricted rule breaksab → bca costs 3, but by way of ba it costs 2ac → cba costs 3, but by way of ca it costs 2ba → acb costs 3, but by way of ab it costs 240 strings, 1,600 pairs, 64,000 triplesunrestricted: 0 triples broken

The edit that reaches back two rows

Swapping two adjacent characters is one keystroke and costs two edits. Adding it as a fourth transition is four lines, it is what nearly everything ships, and the function those four lines compute is not the one they are named after. Over 1,600 pairs of short strings the two definitions differ on twelve, and the shipped one breaks the triangle inequality on twelve triples where the other breaks it on none.

tables · Cost cells expandedreads building the estimateNo estimate1,572 expanded · path 356Straight-line estimate1,550 expanded · path 356A*, landmarks252 expanded · path 356 · 6,328 reads to buildV = 2,500, steps cost one to nine, seed 20260910shortest path 356

An estimate borrowed from an easier problem

On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.

graphs · Graph unit cost — triples broken0.02%unit cost — pivot bound failed0.02%log-odds on a keyboard walk — triples broken6.61%log-odds on a keyboard walk — pivot bound failed13.22%42,840 triples per model, enumerated0.02% shown where the true rate is zero

A distance that is not a distance

Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.

wrong · Cost steps cost one to ninesteps cost one01,0002,0003,000cells expanded, mean over the gridsA* from one endalways shortestalways shortesttwo-ended Dijkstraalways shortestalways shortesttwo A*, separate estimateswrong on 12always shortesttwo A*, stop on either keyalways shortestalways shortesttwo A*, averaged potentialalways shortestalways shortest40 grids a bar, 2,500 cellsestimate: straight-line cells

Two estimates that must agree

Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.

graphs · Graph 24816326412825510⁶10⁷average out-degreecounted workBellman–Ford from every sourceJohnson's reweightingFloyd–Warshall256 vertices, every answer comparedwork: relaxations + heap comparisons

One Bellman–Ford buys every Dijkstra

A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.

graphs · Graph 0200400600800cells expanded per query, meanno landmarks897four near the centre423four at random209farthest-first141the corners1268 maps × 150 queriesdots: each map's mean

Where the landmarks stand

Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.

graphs · Graph 125102050100200100observed queries the selection sawcells expanded, meanon fresh querieson the sample it was chosen fromthe cornersfarthest-first8 maps × 150 fresh queriesflat lines read no queries

What the queries know that the map does not

A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Shortest pathHeuristic searchPotential functionAdmissibilityBreak-evenCost modelDijkstra's algorithmEdit distanceHonest limitLandmarkPreprocessingSearch frontier

All concepts