The Luleå algorithm of computer science, designed by Degermark et al. (1997), is a technique for storing and searching internet routing tables efficiently.
This prefix matching problem may be solved by a trie, but trie structures use a significant amount of space (a node for each bit of each address) and searching them requires traversing a sequence of nodes with length proportional to the number of bits in the address.
This small memory footprint often allows the entire data structure to fit into the routing processor's cache, speeding operations.
However, it has the disadvantage that it cannot be modified easily: small changes to the routing table may require most or all of the data structure to be reconstructed.
The first level of the data structure consists of To look up the datum for a given address x in the first level of the data structure, the Luleå algorithm computes three values: The sum of these three values provides the index to use for x in the array of items.