This page gathers together resources and links on my paper Counting Distance Permutations, which appeared in SISAP '08. There is also an extended journal version, which see; this page is about the conference version. First, the abstract:

A distance permutation index supports fast proximity searching in a high-dimensional metric space. Given some fixed reference sites, for each point in a database the index stores a permutation naming the closest site, the second-closest, and so on. We examine how many distinct permutations can occur as a function of the number of sites and the size of the space. We give theoretical results for tree metrics and vector spaces with $L_1$, $L_2$, and $L_\infty$ metrics, improving on the previous best known storage space in the vector case. We also give experimental results and commentary on the number of distance permutations that actually occur in a variety of vector, string, and document spaces.

The actual paper is available through the publishers, but requires a payment. If you're located at a university you may be covered by a site license allowing you to download it at no further charge. Here are the slides from my talk; and here's my BIBTeX database of references (not all of which are necessarily used in the actual paper).