Would this work :

A trick is to know which questions should you ask first. If you ask first those questions that''ll cut the most ''no'' answers, you save lots of time. For start, you can simply know how many no answers are there for each question. Simply ask first the question in your query with most nos. Then the next, and so on.

This can not work very good sometimes. This is an example :

1)YYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNN
2)NNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYY
3)NNNNNNNNNNNNNNNNYNNNYYYYYYYYYYYYY
4)NNNNNNNNNNNNNNNNYNNNYYYYYYYYYYYYY
5)NNNNNNNNNNNNNNNNYNNNYYYYYYYYYYYYY
6)NNNNNNNNNNNNNNNNYNNNYYYYYYYYYYYYY
7)NNNNNNNNNNNNNNNNYNNNYYYYYYYYYYYYY


The algorithm should ask the 1th and 2th questions first. If it did it only one item would remain. Instead, it asks the 3th, 4th, 5th, 6th, 7th questions first, cause they have more No answers.

So, you could be funky and know how many items would remain when asking 2 questions for each pair of two elements.

In this example :
1) and 2) : 1 item remains
1) and 3) : 1 item remains
1) and 4) : 1
....
2,3 : lots of them
2,4 : lots
....
3,4 : lots
...
4,5 :lots
.........

So, when you get your query, assuming you have more than 1 question, you ask first those two questions that are in your query and TOGETHER have the most NO answers.

You can experiment and know 3 or 4 questions, dont know how much will it improve the speed, guess it depends on what your database looks like.



For a fast intersection, for each question, I''d store the set of item indexes that answer Yes/Maybe/Na for that question. You can store these indexes in a sorted tree thingie (b-tree works best for reading stuff from hard disk). When you have to intersect two such sets, you take all elements from the set with the least number of elements, and for each element, check if you can find it in the other set. If the two sets have m and n number of elements, with m > n, the complexity of the intersection will be
O(n * log m) (n cause you take all the n elements from the small set, log m is the time for a check in a tree). This means that if you can reduce the set of items that can match your query early on, when you have to intersect this remaining set with a big set of a "mostly yes answers" question, the size of that set isnt all that important.


Dont know how much my English helped me either

Sorry about the last message being anonymous poster. It was in fact me. I forgot that I had erase my browsers cache. Sorry again...




"And that''s the bottom line cause I said so!"

Cyberdrek
Headhunter Soft
A division of DLC Multimedia

Well look at come.to/20q this is an interesting approach to something similar. You think of something and it asks you 20 questions about it and then guesses what you''ve thought of. Maybe it helps.

Quick sort is (on average) O(N log N), worst case is O(N^2)
Radix sort/histogram sort are both O(N), but may have a large memory overhead (if implemented naively, anyway)

Hi,

Diodor, that is a great algorithm and this is definitely the way I''m going to start. The only problem is that in my case the most answers are ''not defined = na'' because I enter something like "being cold = yes to fever, yes to headache, no to bleeding, maybe dizzines...etc'' and I don''t enter for each symptom yes/no/maybe. I guess it will be a pain to get this system accurate by having as few na answers as possible.
Thanks.

Regards,
Horia

Of all the things I''''ve lost I miss my mind the most