Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Anton Nov 20 '12 at 20:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.