I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear search is $t\cdot |S|$. I can break a query down into simpler sub-queries q_i and find $H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$ and where $H_\text{exact}\subseteq H_\text{approx}$. Each subquery $q_i$ is much faster to compute, so overall it is faster to find $H_\text{approx}$ and then use $Q$ to find $H_\text{exact}$.

Each $Q$ has many $q_i$. The overlap between different $Q$ is high. I'm looking for a way to determine a decision-tree-like set of fixed questions $q_j$ which minimize the average time to find a H_exact, based on a large sample of search queries.

To make this more concrete, suppose the data set contains the 7 billion people in the world, and the complex queries are things like "the woman who lives in the red house on the corner of 5th and Lexington in a city starting with B."

The obvious solution is to check every person in world and see who matches the query. There may be more than one such person. This method takes a long time.

I could pre-compute this query exactly, in which case it would be very fast .. but only for this question. However, I know that other queries are for the woman who lives on the blue house on the same corner, the man who lives on the same corner, the same question but in a city starting with C, or something totally different, like 'the king of Sweden.'

Instead, I can break the complex question down into a set of easier but more general sets. For example, all of the above questions have a gender-role based query, so I can precompute the set of all people in the world who consider themselves a 'woman.' This sub-query takes essentially no time, so the overall search time decreases by roughly 1/2. (Assuming that by other knowledge we know that a Swedish "king" cannot be a "woman." Hatshepsut was an Egyptian woman who was king.)

However, there are sometimes queries which aren't gender-based, like "the person who lives on 8th street in a red house in a city starting with A." I can see that the subquery "lives in a red house" is common, and pre-compute a list of all those people who live in a red house.

This gives me a decision tree. In the usual case, each branch of the decision tree contains different questions, and the methods to select the optimal terms for the decision tree are well known. However, I'm building on an existing system which requires that all branches must ask the same questions.

Here's an example of a possible final decision set: question 1 is 'is the person a woman?', question 2 is 'does the person live in a red house?', question 3 is 'does the person live in a city starting with A or does the person live in a city starting with B?', and question 4 is 'does the person live on a numbered street?'.

When a query $Q$ comes in, I see if its $q_i$ match any of the pre-computed questions $q_j$ I've determined. If so, then I get the intersection of those answers, and ask the question $Q$ on that intersection subset. Eg, if the question is "people who live in a red house on an island" then find that "person lives in a red house" is already precomputed, so it's only matter of finding the subset of those who also live on an island.

I can get a cost model by looking at a set of many $Q$ and check to see the size of the corresponding $H_\text{approx}$. I want to minimize the average size of $H_\text{approx}$.

The question is, how do I optimize the selection of possible $q_j$ to make this fixed decision tree? I tried a GA but it was slow to converge. Probably because my feature space has a few million possible $q_j$. I've come up with a greedy method, but I'm not happy with the result. It too is very slow, and I think I'm optimizing the wrong thing.

What existing research should I be looking at for ideas?

  • $\begingroup$ Is your data fixed-are you going to add more examples? If not- better try building descision tree by starting with the subquery with highest information entropy.You can also choose some minimum entropy where to stop the tree based descisions and search with |S|.t time when S is small enough. $\endgroup$
    – Anton
    Commented Nov 20, 2012 at 20:01

1 Answer 1


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<$f_i<=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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.