Footnotes

...Kroeger
  Internet: tmk@ce.ucsc.edu, Telephone (408) 459-4458.

...Long
  Internet: darrell@cs.ucsc.edu, Telephone (408) 459-2616.

...Long
  Supported in part by the Office of Naval Research under Grant N00014--92--J--1807.

...trie
  A trie is commonly used as as a efficient data structure to hold a dictionary of words. It is based on a tree in which each node contains a specific character. Each node then represents the sequence of characters that can be found by traversing the tree from the root to that node.

...one
  Note that since nodes of order m must have children (which will be leafs), a model of order m requires a trie of order m+1.

...megabytes.
  For readability our graphs only show cache sizes up to 128 megabytes.