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 tree of foods, which I'd like to search to find relevant nodes. What's the best way to rank the results?

Here's an example sub-set after a search for "apple":

|-- apple pie
|-+ apples
| |-- cooking
| |-+ eating
|   |-- average
|   |-- Granny Smith
|   |-- Golden Delicious
|-- pork and apple casserole

Currently, I'm ranking based on which results come earliest in the full name of each leaf, so a result set would look like:

0 Apple pie
0 Apples, cooking
0 Apples, eating, average
0 Apples, eating, Granny Smith
0 Apples, eating, Golden Delicious
2 Pork and apple casserole

Where the rank is the index of the first token match, lower the rank the better.

I'd like to aggregate the matches, so that I don't display the full sub-tree on the initial search, for example:

Apples... (4)
Apple pie
Pork and apple casserole

The obvious way to rank these is to count the number of matching leaves, then the higher the rank, the better the match.

But, I'm not sure how to combine these rankings, since one is larger-is-better and one is smaller-is-better. Are there standard ways to combine rankings like this? (I'm not sure what to search for, so Google is giving me results about search engine optimisation, and searching web pages, which doesn't seem to apply.)

share|improve this question
    
I don't understand what do you mean with "one is larger-is-better and one is smaller-is-better"? –  Anton Jan 9 '13 at 11:27
add comment

1 Answer

up vote 1 down vote accepted

Although i dont really know how a result is better. I guess what you are doing is fine (And perhaps the best possibly you can get). Just one note to be more precise, you should be ranking a node $u$ based on the size of the subtree rooted at $u$ (not on the number of leaves in that subtree, or children of $u$). This is better (and more general).

But one way to solve issues like this in general is to give score to each node in your tree (a weight). The higher the score, the more it will be ranked above. Then, you will be looking for the subtree with highest weights. You compute this by summing the weights of all nodes in a subtree.

Example of weights (just to help you a bet):

  • closeness to search term (use hamming distance for example, or other metrics [e.g. look how spelling suggestion algorithms work.]
  • If this is a website of recipes for example, the nodes may be recipes and the weight of a node is how many "likes" it received from the website.

In conclusion, I guess what you are doing is the best approximation to have. Adding the weights is a heuristic to give you perhaps better results.

share|improve this answer
add comment

Your Answer

 
discard

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

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