Counting Distance Permutations (SISAP version)

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).