visualization + design
Hilbert Curve Art, Hilbertonians and Monkeys
I collaborated with Scientific American to create a data graphic for the September 2014 issue. The graphic compared the genomes of the Denisovan, bonobo, chimp and gorilla, showing how our own genomes are almost identical to the Denisovan and closer to that of the bonobo and chimp than the gorilla.
Here you'll find Hilbert curve art, a introduction to Hilbertonians, the creatures that live on the curve, an explanation of the Scientific American graphic and downloadable SVG/EPS Hilbert curve files.
Hilbert curve
There are wheels within wheels in this village and fires within fires!
— Arthur Miller (The Crucible)
The Hilbert curve is one of many space-filling curves. It is a mapping between one dimension (e.g. a line) and multiple dimensions (e.g. a square, a cube, etc). It's useful because it preserves locality—points that are nearby on the line are usually mapped onto nearby points on the curve.
It's a pretty strange mapping, to be sure. Although a point on a line maps uniquely onto the curve this is not the case in reverse. At infinite order the curve intersects itself infinitely many times! This shouldn't be a surprise if you consider that the unit square has the same number of points as the unit line. Now that's the real surprise! So surprising in fact that it apparently destabilized Cantor's mind, who made the initial discovery.
Bryan Hayes has a great introduction (Crinkly Curves) to the Hilbert curve at American Scientist.
If manipulated so that its ends are adjacent, the Hilbert curve becomes the Moore curve.
constructing the hilbert curve
The order 1 curve is generated by dividing a square into quadrants and connecting the centers of the quadrants with three lines. Which three connections are made is arbitrary—different choices result in rotations of the curve.
The order 6 curve is the highest order whose structure can be discerned at this figure resolution. Though just barely. The length of this curve is about 64 times the width of the square, so about 9,216 pixels! That's tight packing.
By order 7 the structure in the 620 pixel wide image (each square is 144 px wide) cannot be discerned. By order 8 the curve has 65,536 points, which exceeds the number of pixels its square in the figure. A square of 256 x 256 would be required to show all the points without downsampling.
Two order 10 curves have 1,048,576 points each and would approximately map onto all the pixels on an average monitor (1920 x 1200 pixels).
A curve of order 33 has `7.38 * 10^19` points and if drawn as a square of average body height would have points that are an atom's distance from one another (`10^{-10}` m).
mapping the line onto the square
By mapping the familiar rainbow onto the curve you can see how higher order curves "crinkle" (to borrow Bryan's term) around the square.
properties of the first 23 orders of the Hilbert curve
| order | points | segments | length |
| `n` | `4^n` | `4^{n-1}` | `2^n-2^{-n}` |
| 1 | 4 | 3 | 1.5 |
| 2 | 16 | 15 | 3.75 |
| 3 | 64 | 63 | 7.875 |
| 4 | 256 | 255 | 15.9375 |
| 5 | 1,024 | 1,023 | 31.96875 |
| 6 | 4,096 | 4,095 | 63.984375 |
| 7 | 16,384 | 16,383 | 127.9921875 |
| 8 | 65,536 | 65,535 | 255.99609375 |
| 9 | 262,144 | 262,143 | 511.998046875 |
| 10 | 1,048,576 | 1,048,575 | 1023.9990234375 |
| 11 | 4,194,304 | 4,194,303 | 2047.99951171875 |
| 12 | 16,777,216 | 16,777,215 | 4095.99975585938 |
| 13 | 67,108,864 | 67,108,863 | 8191.99987792969 |
| 14 | 268,435,456 | 268,435,455 | 16383.9999389648 |
| 15 | 1,073,741,824 | 1,073,741,823 | 32767.9999694824 |
| 16 | 4,294,967,296 | 4,294,967,295 | 65535.9999847412 |
| 17 | 17,179,869,184 | 17,179,869,183 | 131071.999992371 |
| 18 | 68,719,476,736 | 68,719,476,735 | 262143.999996185 |
| 19 | 274,877,906,944 | 274,877,906,943 | 524287.999998093 |
| 20 | 1,099,511,627,776 | 1,099,511,627,775 | 1048575.99999905 |
| 21 | 4,398,046,511,104 | 4,398,046,511,103 | 2097151.99999952 |
| 22 | 17,592,186,044,416 | 17,592,186,044,415 | 4194303.99999976 |
| 23 | 70,368,744,177,664 | 70,368,744,177,663 | 8388607.99999988 |
You can download the basic curve shapes for orders 1 to 10 and experiment yourself. Both square and circular forms are available.
Propensity score matching
I don’t have good luck in the match points. —Rafael Nadal, Spanish tennis player
In many experimental designs, we need to keep in mind the possibility of confounding variables, which may give rise to bias in the estimate of the treatment effect.
If the control and experimental groups aren't matched (or, roughly, similar enough), this bias can arise.
Sometimes this can be dealt with by randomizing, which on average can balance this effect out. When randomization is not possible, propensity score matching is an excellent strategy to match control and experimental groups.
Kurz, C.F., Krzywinski, M. & Altman, N. (2024) Points of significance: Propensity score matching. Nat. Methods 21:1770–1772.
Nasa to send our human genome discs to the Moon
We'd like to say a ‘cosmic hello’: mathematics, culture, palaeontology, art and science, and ... human genomes.
Comparing classifier performance with baselines
All animals are equal, but some animals are more equal than others. —George Orwell
This month, we will illustrate the importance of establishing a baseline performance level.
Baselines are typically generated independently for each dataset using very simple models. Their role is to set the minimum level of acceptable performance and help with comparing relative improvements in performance of other models.
Unfortunately, baselines are often overlooked and, in the presence of a class imbalance, must be established with care.
Megahed, F.M, Chen, Y-J., Jones-Farmer, A., Rigdon, S.E., Krzywinski, M. & Altman, N. (2024) Points of significance: Comparing classifier performance with baselines. Nat. Methods 21:546–548.
Happy 2024 π Day—
sunflowers ho!
Celebrate π Day (March 14th) and dig into the digit garden. Let's grow something.
How Analyzing Cosmic Nothing Might Explain Everything
Huge empty areas of the universe called voids could help solve the greatest mysteries in the cosmos.
My graphic accompanying How Analyzing Cosmic Nothing Might Explain Everything in the January 2024 issue of Scientific American depicts the entire Universe in a two-page spread — full of nothing.
The graphic uses the latest data from SDSS 12 and is an update to my Superclusters and Voids poster.
Michael Lemonick (editor) explains on the graphic:
“Regions of relatively empty space called cosmic voids are everywhere in the universe, and scientists believe studying their size, shape and spread across the cosmos could help them understand dark matter, dark energy and other big mysteries.
To use voids in this way, astronomers must map these regions in detail—a project that is just beginning.
Shown here are voids discovered by the Sloan Digital Sky Survey (SDSS), along with a selection of 16 previously named voids. Scientists expect voids to be evenly distributed throughout space—the lack of voids in some regions on the globe simply reflects SDSS’s sky coverage.”
voids
Sofia Contarini, Alice Pisani, Nico Hamaus, Federico Marulli Lauro Moscardini & Marco Baldi (2023) Cosmological Constraints from the BOSS DR12 Void Size Function Astrophysical Journal 953:46.
Nico Hamaus, Alice Pisani, Jin-Ah Choi, Guilhem Lavaux, Benjamin D. Wandelt & Jochen Weller (2020) Journal of Cosmology and Astroparticle Physics 2020:023.
Sloan Digital Sky Survey Data Release 12
Alan MacRobert (Sky & Telescope), Paulina Rowicka/Martin Krzywinski (revisions & Microscopium)
Hoffleit & Warren Jr. (1991) The Bright Star Catalog, 5th Revised Edition (Preliminary Version).
H0 = 67.4 km/(Mpc·s), Ωm = 0.315, Ωv = 0.685. Planck collaboration Planck 2018 results. VI. Cosmological parameters (2018).
constellation figures
stars
cosmology
Error in predictor variables
It is the mark of an educated mind to rest satisfied with the degree of precision that the nature of the subject admits and not to seek exactness where only an approximation is possible. —Aristotle
In regression, the predictors are (typically) assumed to have known values that are measured without error.
Practically, however, predictors are often measured with error. This has a profound (but predictable) effect on the estimates of relationships among variables – the so-called “error in variables” problem.
Error in measuring the predictors is often ignored. In this column, we discuss when ignoring this error is harmless and when it can lead to large bias that can leads us to miss important effects.
Altman, N. & Krzywinski, M. (2024) Points of significance: Error in predictor variables. Nat. Methods 21:4–6.
Background reading
Altman, N. & Krzywinski, M. (2015) Points of significance: Simple linear regression. Nat. Methods 12:999–1000.
Lever, J., Krzywinski, M. & Altman, N. (2016) Points of significance: Logistic regression. Nat. Methods 13:541–542 (2016).
Das, K., Krzywinski, M. & Altman, N. (2019) Points of significance: Quantile regression. Nat. Methods 16:451–452.