Concept

Van emde boas layout — where it appears

A recursive arrangement of a tree in memory that is efficient at every block size at once, without the block size being named anywhere. It is efficient at every block size at once without the block size being named, which is what the word oblivious means in this setting.

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

The layout that is told nothing

A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.

applied · Transfer

Two searches, one comparison count

Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.

machine · Machine

Named alongside it

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

Block transfer Cost model B-tree Binary search Cache oblivious Comparison count External-memory model Locality Memory hierarchy Memory layout Parameter choice Tree height

All concepts