How it works

Cool tricks

This project uses many nice algorithms and technologies. The rest of the page explains them in detail; here are my favorites.

• Meet-in-the-middle: the page looks for anagrams in all the pairs of a first name and a last name, 1.7 million × 3.5 million = 6 trillion pairs. To find the pairs of two lists that match a target is a classic algorithmic problem, and a nice example of the meet-in-the-middle technique: for each first name that fits in your letters, the letters that stay give the last names.
• Tries: the first and last names go in two tries. The 5.2 million names fit in one file of 9.2 MB, which the browser keeps in memory and searches in a few milliseconds. The letters go from the rarest to the most common, so that the search cuts most branches at the top.
• Quantized ranking model: to keep the synthetic anagranames interesting, a simple machine learning model inspired by factorization machines ranks them. We train it with MLX in less than 3 minutes on my MacBook Pro, on 353 million people. Then we quantize its vectors to 4 bits per number, so that the full model takes only 11 MB.
• Permutation-invariant hashing: the real anagranames come from the list of the 155 million real full names, 465 MB in gzip: too much for a browser. So we put the full names in 4,096 buckets by a checksum that stays the same when the letters change order. All the anagrams of your name are in one bucket, and the page downloads only this bucket (113 KB on average).

The full code is on GitHub, with the MIT license.

What data do you use?

• Names: name_dataset (the full data, 3.3 GB): 491,655,925 Facebook accounts (first name, last name, country) in 105 countries, from the leak of 2021.
• Names in France: INSEE, the first names given to the children born from 1900 to 2022 (33,234 names), and the last names of the people born from 1891 to 2000 (215,906 names). INSEE counts each name alone, not the full names. For France, the model uses these counts instead of the Facebook counts.
• Population: World Bank, 2023, and for Taiwan its Ministry of the Interior.
• Globe: the countries of Natural Earth (1:50m), simplified.

Cleaning: we keep a person only if the two names are in Latin script, with letters, spaces, hyphens, apostrophes and periods only. Then we remove the names that fewer than 5 people have in the world: most are typing errors or fake names. This keeps 352,931,936 people, 1,724,039 first names, 3,456,059 last names and 154,775,215 different full names. From INSEE, we remove the lines that put the rare names together.

How do you find anagranames?

A name becomes its letters A to Z, without accents, spaces or hyphens: Jean-Paul becomes JEANPAUL. Two full names are anagrams when they have the same letters.

1. We sort the letters of each name, the rarest letters (Q, X, Z…) first. The first names go in a trie of these sorted letters: a tree where each node adds one letter, and each name is at the node of its last letter. The last names go in a second trie.
2. The search goes down the trie of the first names. It enters a node only if your name has one more of its letter, and if 2 letters at least stay for the last name.
3. At each first name, the letters that stay give one path in the trie of the last names. All the last names at the end of this path make anagranames with this first name.

The rare letters at the top cut most branches early: a search takes a few milliseconds. In a country, the search keeps the names seen in this country. The list of the real anagranames is in order of accounts. The list of the synthetic anagranames is in order of probability.

How do you rank the synthetic anagranames?

A model gives the probability that a person of the country $c$ has the first name $f$ and the last name $l$. It starts from the two names alone:

with $N_{fc}$ the people of $c$ with the first name $f$, $N_c$ the people of $c$, $\pi_f$ the share of $f$ in the world and $\alpha=10^5$ (the same for $p(l\mid c)$). For France, $N_{fc}$ is the people with $f$ in INSEE, scaled to the people of France in name_dataset. Then the model corrects the pair. Each name has a vector of 16 numbers: $u_f$ for a first name, $v_l$ for a last name. Each country has 16 weights $g_c$, a scale $\beta_c$ and an offset $b_c$:

$S_c$ contains the pairs whose two names occur in $c$ (for France: in INSEE), and $Z_c$ makes the probabilities sum to 1. For the world, the page mixes the countries by their population $P_c$, with $P=\sum_c P_c$:

The page ranks by $p(f,l)$, and shows $P\,p(f,l)$ as the people expected. In a country, it uses $p(f,l\mid c)$ and $P_c\,p(f,l\mid c)$. The correction learns which names go together. Four names in the United States, with the last names swapped:

Training. We split the people at random: 80% to train, 10% to calibrate, 10% to test. In France, we keep only the people whose two names are in INSEE (71.5%). This gives 278 million people to train, 35 million to calibrate and 35 million to test. Only the 1,339,826 names of 20 people or more get a vector; the vector of the other names is 0. The training uses $\beta_c=1$, $b_c=0$, and minimizes the negative log-likelihood of the train people. The base does not change, thus

with $w_c$ the share of the train people in $c$ and $\rho_c=p_0(S_c\mid c)$. The sets $S_c$ have 3 million million pairs in all, so each step estimates the expectation by self-normalized importance sampling, as in Bengio and Senécal: $J=4096$ pairs $x_j$ per country, from a mix $q_c$ of the train people of $c$, of $p_0$ on $S_c$, and of the names of $c$ in proportion to their pairs:

The optimizer is AdamW: $10^4$ steps, batches of 65,536 people, learning rate $10^{-2}$, weight decay 0.1. This takes 2.3 minutes on a laptop GPU (Apple M4 Max). Then the GPU computes the exact $Z_c$.

Calibration. As with the neural networks of Guo et al., the trained correction is too strong. For each country, $\beta_c$ and $b_c$ maximize the gain on the calibration people:

with $E_c$ the mean of $\mathbb 1_{S_c}s_c$ and $Q_c$ the share in $S_c$ of these people. The best offset is $e^{b^\star}=Q_c(1-\rho_c)/\bigl((1-Q_c)M_c(\beta)\bigr)$, and a search on $\beta\in\{0,0.01,\dots,2\}$ gives the scale. The median $\beta_c$ is 0.88. $\beta=0$ gives the base, so no country gets worse than the base. France keeps $\beta=1$ and $b=0$: its calibration people all have their two names in INSEE, so they are not a sample of France.

Result. On the 35 million test people, the model needs 25.117 bits per person, against 25.572 for the two names alone: 0.454 bits less. All 105 countries are better, from 0.03 bits (Uruguay) to 3.3 bits (Burkina Faso).

How do the data and the model fit in a browser?

• Vectors: the 1.34 million vectors take 86 MB in 32-bit numbers. With product quantization, each pair of numbers becomes one byte: the index of the nearest of 256 learned pairs. They take 11 MB, and the model needs less than 0.01 bits per person more.
• Normalization: $\log Z_c$ is computed once, before the export. The browser only adds the terms.
• Tries: one letter per node, in preorder, with the size of each subtree. The file of the world has the two tries and the people of each name: 9.2 MB in gzip, downloaded once.
• Names: the spellings, the people per country and the vectors are in files of 1,024 names. A search downloads only the files of the names it finds (a typical search: 85 files, 1.5 MB).
• Real full names: 155 million, in 4,096 files. Each letter has a random number, and the file of a full name is the sum of the numbers of its letters, modulo 4,096. Thus all your anagranames are in one file (113 KB on average).

The browser keeps the files for the next searches. The search and the model run in your browser: the page does not send your name.