Kyori
Every autocomplete box does two jobs. It filters the catalogue down to what begins with the typed text, and then it orders what is left — the job people notice, because the right suggestion either comes first or it does not. Kyori, our open-source JavaScript string library, carries a ranking cost built for that second job: four ordered rules and a tie-break, with no popularity data, no model and no index. This page is where Kyori 0.7.0 stands: how well it orders real searches, measured against the libraries applications already use.
On 11,607 AmazonQAC prefixes the design never saw. Level with Fuse.js, fuzzysort and sorting by length: no gap between them survives a significance test.
Among equal costs, the shorter completion first. It cuts tied cases from 85% to 47%, and the gain holds on the split it was not chosen from.
Ordering by how often people search for a completion beats every string method. It is the one signal that separates candidates of equal length.
Measured on 0.6.0, which prepares each string once; 0.5.0 took 120 µs, normalising the same strings again on every comparison. 0.7.0 changed only the last rule, which a filtered list rarely reaches, and was not timed again. Still behind fuzzysort (19 µs) and a plain prefix sort (27 µs).
Distance counts, similarity measures, rank orders.
Every method in the library answers three questions, and Kyori keeps the three answers apart on purpose. This is the statement every version is held to, the one below and the ones after it; the rules and the tables further down are what it looks like in one release.
- distance(a, b)How many operations turn one string into the other?
A count, in characters: insertions, deletions, substitutions, and for Damerau a swap of two neighbours. Lower is better, 0 is identity, and a pair the metric does not define (Hamming on unequal lengths) returns −1. It knows nothing about proportion; three edits are three edits in a word of four letters and in a title of forty.
Kyori’s own distance() is the ranking cost below. It is asymmetric and reads 0 for every candidate that starts with what was typed, so it is a cost, not a metric, and no resemblance can be read off it.
- similarity(a, b)What share of the two agrees?
A proportion between 0 and 1, higher is better. For the edit metrics it is the distance scaled by the longer string (1 − d / max); Jaro–Winkler is a similarity natively and its distance is 1 − s. There the two are duals, and each derives the other.
Kyori’s similarity() is the Jaccard index of the two folded word sets: the share of words in common. It never looks at characters and does not know which string was typed.
- rank(query, candidates)Which candidate comes first for this query?
An order, not a measure. It owes nothing to the metric axioms: it may be asymmetric, it is not bounded, and a tie-break by length is a legitimate part of it though no distance or similarity would contain one. Every method ranks by the function its contract gives, distances ascending and similarities descending.
Kyori ranks by its cost, then by length, shorter first; rankKey() is that order as one number. Nothing is learned and nothing counts popularity. That is left to the caller, who has the logs.
What this commits a version to. Three things, and every version from 0.5.0 on is measured against them. The three functions stay separate: no version derives Kyori’s similarity from its cost or its cost from its similarity, because a cost that is 0 for every prefix match has no resemblance in it to read. 0.7.0’s last rule reads words too, but from the typed side only, with a typo tolerance, and below every prefix match; it is not the similarity, and neither is derived from the other. Each is evaluated on its own task, with its own corpora and its own leaders; ranking on filtered autocomplete pools, resemblance on product titles, distance on misspellings. A number from one task is never quoted for another, and the table below is the ranking task alone. And the names stay uniform across methods, which means the mistake stays possible: a caller can sort an autocomplete list by similarity(), so the evaluation keeps that mistake as a row (it loses 0.133 against the cost on the held-out pools) rather than hiding it.
The split is a design choice with a precedent, not a taxonomy the field agreed on. RapidFuzz ships a distance and a similarity for each of its metrics and leaves ranking to a helper; Kyori makes the third a contract, because a sort key is not a measure and should not be asked to behave like one.
Four rules, tried in order, and a tie-break.
The cost compares what was typed with one candidate: 0 is a perfect match, lower is better, and the first rule that applies decides. There are no weights, nothing learned and no frequency data, so the same pair costs the same everywhere. Each rule has a precedent in error-tolerant search; what is Kyori’s own is the arrangement, the constants and the last rule’s formula.
- R1Identicalreturns 0
Equal as typed, or equal once both strings are folded: accents stripped, lowercase, dashes read as spaces.
- R2Same words, another orderreturns 1
The same words as a bag, reordered: "hotel bel-air" against "bel-air hotel".
- R3A typed prefixreturns its edits
The fewest edits between what was typed and any start of the candidate, first letter fixed; the unread rest is free. No typo below three typed characters, one for 3–5, two for 6–8.
- R4Everything elsereturns a sum
Since 0.7.0: for each typed word, the fewest edits from it to the start of any word of the candidate. A word no candidate word starts with costs more than any edit count can, the nearest such word's edits are added, and the whole sits one tier above every typed-prefix result. The candidate's length never counts. Until 0.6.0 this rule charged the length difference and how far each typed word had moved.
- TieShorter firstorders equal costs
rank() sorts by the cost, then by the candidate's length, then alphabetically; rankKey() is that order as one number.
These rules are distance() alone. similarity() is a different function on purpose, the share of words two strings have in common (the statement above), and the table below keeps the mistake of sorting an autocomplete list by it as a row.
Level with the best libraries, below popularity.
The data is AmazonQAC, the query-autocomplete dataset Amazon published at EMNLP 2024: real prefixes people typed into a search box, each with the search it ended in. Each candidate list is exactly what a typo-tolerant prefix filter returns from the catalogue, and ties are reported rather than broken by the alphabet. Kyori was designed on the test split, so the figures that count come from a sample of the train split drawn afterwards and never consulted — and every comparison is tested case by case, corrected across all 19.
Mean reciprocal rank is 1 when the answer comes first, ½ when it comes second, and so on, averaged over every case. The band is how far a tie policy alone could move each score: a narrow band means the method decided the order itself. Every figure was measured on the code released as Kyori 0.7.0.
| Method | Test split | Held out | Band | Tied | In top 10 |
|---|---|---|---|---|---|
Most popular completion Prefix matches, most searched first | — | 0.422 | 0.413–0.448 | 18% | 0.638 |
Kyori 0.7.0 The cost, then shorter first | 0.409 | 0.404 | 0.393–0.416 | 47% | 0.616 |
ORDER BY length The zero-library rule | 0.408 | 0.403 | 0.385–0.441 | 50% | 0.615 |
fuzzysort 4 Subsequence match | 0.409 | 0.403 | 0.390–0.421 | 47% | 0.617 |
Fuse.js 7 Bitap match, weighted by length | 0.408 | 0.402 | 0.355–0.499 | 66% | 0.612 |
match-sorter 8 Match tiers | 0.389 | 0.376 | 0.276–0.942 | 82% | 0.582 |
Kyori, cost alone No tie-break | 0.381 | 0.368 | 0.257–0.988 | 85% | 0.577 |
Character trigrams Trigram cosine | 0.369 | 0.365 | 0.364–0.411 | 15% | 0.591 |
Jaro–Winkler Name-matching similarity | 0.357 | 0.353 | 0.343–0.365 | 48% | 0.594 |
Kyori similarity as a key Word overlap | 0.279 | 0.271 | 0.210–0.706 | 82% | 0.460 |
Damerau–Levenshtein Edit distance | 0.267 | 0.257 | 0.245–0.272 | 64% | 0.459 |
Expected values under a random order inside ties. Most-popular-completion needs Amazon’s search counts, which only the train split carries, so it has no test-split score. “In top 10” is the share of cases where the answer is among the first ten suggestions.
Kyori over sorting by length, the same on both splits and significant on neither once corrected (p = 0.21 and 0.24). Level, not ahead.
Kyori over match-sorter, whose tiers leave 82% of cases tied. A real gap: p < 0.01 after correction.
The cost over the library’s own similarity used as a key — the case for keeping ranking and resemblance as separate functions.
Where the tie-break helps, and where popularity does.
The same held-out cases, split by how many candidates the filter returned. Ordering nine completions of a long prefix and ordering a thousand completions of one letter are different jobs, and the three rankers below tell them apart.
Show the numbers
| Candidates | Cases | Kyori, cost alone | Kyori 0.7.0 | Most popular completion |
|---|---|---|---|---|
| 2–9 | 3,172 | 0.759 | 0.787 | 0.787 |
| 10–49 | 2,259 | 0.454 | 0.499 | 0.519 |
| 50–199 | 2,428 | 0.202 | 0.248 | 0.273 |
| 200–999 | 2,869 | 0.115 | 0.151 | 0.185 |
| 1000+ | 879 | 0.014 | 0.032 | 0.036 |
As good as the libraries in use, not better.
The question was whether a cost assembled from known parts could order a filtered list better than what applications already use. It orders it as well, not better — and the evaluation shows where the order of such a list actually comes from.
- The order comes from a length prior
- The four string methods at the top share one idea. Sorting by length has nothing else, Fuse.js weighs field length, fuzzysort subtracts the candidate's length from its score, and Kyori breaks its ties that way. Once a list already starts with what was typed, "shorter first" is most of what a string can say.
- Popularity is the signal strings lack
- Most-popular-completion leads by 0.018 (interval 0.013–0.022) and is the only method that separates candidates of equal length. It is level with Kyori on lists of 2–9 and ahead from ten candidates up — and still below 0.04 past a thousand.
- Other jobs have other leaders
- As a measure of resemblance, Kyori's word-overlap similarity trails the methods that weigh rare words up: character trigrams lead it by 0.172 on Abt–Buy's product titles. On 400 real misspellings the cost is 0.039 behind Jaro–Winkler and 0.008 ahead of Damerau–Levenshtein; 0.7.0's last rule took it from 0.863 to 0.882, since a misspelling that changes its first letter falls to that rule. Its strength is still the typed prefix and the reordered phrase, not spelling correction.
- Where the rules decide, 0.7.0 moved
- On a filtered list every candidate already extends what was typed, so the last rule never orders the answer: 0.404 before and after. Four held-out groups built so the rules decide tell the versions apart. Ranking the whole catalogue, 0.7.0 goes from 0.567 to 0.597 and passes Fuse.js at 0.579; where the prefix filter had lost the answer to a typo, from 0.365 to 0.583, 0.03 behind character trigrams instead of 0.25. Each gap was confirmed once on the test split.
- Preparing each string once halved the time
- On 0.5.0, 95% of Kyori's queries finished within 2 ms, and a profile put 76% of the ranking key's time into normalising strings, folded again on every comparison, while the rules themselves were cheap. 0.6.0 prepares each string once: 52 µs a query at the median instead of 120, 95% within 0.8 ms, and folding down to 37%, with every result identical to 0.5.0. 0.7.0 was not timed again; its last rule costs about the same per pair, and a filtered list rarely reaches it.
- What this evidence does not cover
- One catalogue: US product searches on Amazon from September and October 2023. The catalogue is built from the evaluated searches themselves, so every answer is in it; a real catalogue is larger and sometimes lacks the answer. Amazon’s counts bound that from below — 1.8% of held-out answers were searched only once that month, and scoring them as misses costs every method about 0.008. The filter admits a typo in only 8% of cases, so typo handling is lightly exercised. There is no session or user signal, the timings come from one machine, and the misspellings are set against random words rather than near ones. Read the direction of the results and the tested gaps, not the third decimal.
It is on npm, and it is free.