Fixed-length decision-tree-like feature selection to minimize average search performance
The solution I found (I asked the question) is to use superimposed coding, and more specifically, a variant of Zatocoding which has better support for hierarchical descriptors.

The method I used comes from 'An Efficient Design for Chemical Structure Searching. I. The Screens', Alfred Feldman and Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), pp 147–152.

The non-hierarchical solution is to look at the information density. Each descriptor will be assigned $s_i=-log_2(f_i)$ bits where $f_i$ is the frequency in the data set ($0&lt;$f_i&lt;=1.0). Compute the total number of bits $D$ (the size of the decision tree) using $D=\sum(s_i f_i)/M_c$ where $M_c$ is the Mooers compression factor 0.69 (from $log_e 2$). Once you have determined the total number of bits to use, select $s_i$ bits randomly for each descriptor for bit assignment.

The hierarchical solution from Feldman and Hodes replaces $s_i=-log_2(f_i)$ for descriptors which are a subset of other descriptors. In that case, use $s_i=-log_2(f_i/g_i)$ where $g_i$ is the frequency of the least frequent parent. In addition, when doing the bit assignment do not select bits which are also used by the parent's bit assignment.

There's still a problem of how to come up with the right descriptors, but that will be domain specific.