29
$\begingroup$

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding something like this:

The search "x OR y" will result in 105 000 hits, while a search for only x will result in 80 000 hits, and a search for only y will get 35 000 hits. Why does the search "x OR y" give 105 000 hits, when the combined individual searches gives 115 000 hits?

For me this sounded strange, so I tested this myself, using the words bacon and sandwich.

  • Only bacon yielded 179 000 000 results
  • Only sandwich yielded 312 000 000 results
  • bacon OR sandwich gave 491 000 000 results

But for me it adds up: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OR sandwich)

Why could an OR query result in fewer hits than both individual queries combined?

Improve this question
$\endgroup$
10
  • 23
    $\begingroup$ You have a blue dog, blue cat, and red cat. NUMBER OF (BLUE) = 2, NUMBER OF (CAT) = 2, but NUMBER OF (BLUE or CAT) = 3, not 4. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    May 3, 2016 at 22:51
  • 11
    $\begingroup$ I tried this, got 184 million results for bacon. Never made it to searching for sandwiches, as I immediately left to fry myself some bacon. $\endgroup$
    – corsiKa
    May 4, 2016 at 0:57
  • 16
    $\begingroup$ I think the real problem here is that your database has no bacon sandwiches in it. $\endgroup$
    – MooseBoys
    May 4, 2016 at 6:41
  • $\begingroup$ @MooseBoys yeah, this must be why my numbers add up, since they should not, right? $\endgroup$
    – sch
    May 4, 2016 at 7:27
  • 3
    $\begingroup$ @klskl: If you're getting those numbers from google, keep in mind those numbers are very very rough estimates. It could very well be the case that, to get the estimate for "bacon OR sandwich", they just sum the numbers. That only works because the estimate is not required to have any sort of accuracy whatsoever. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    May 5, 2016 at 15:05

5 Answers 5

Reset to default
63
$\begingroup$

Hint: The search x AND y will result in 10 000 hits.

Improve this answer
$\endgroup$
7
  • $\begingroup$ yes, but that's beside the point, the teachers claim their x OR y search gives fewer hits than combining the hits of individually searching x then y $\endgroup$
    – sch
    May 3, 2016 at 15:31
  • 65
    $\begingroup$ No, that's not beside the point. On the contrary, it's the point itself. $\endgroup$
    – Yuval Filmus
    May 3, 2016 at 15:32
  • $\begingroup$ I'm new to this, care to elaborate? From what I understand AND will give results with both words in them, hence fewer results than each individually, but what has that to do with OR? $\endgroup$
    – sch
    May 3, 2016 at 15:36
  • 2
    $\begingroup$ When AND is empty OR works like ADD, otherwise it doesn't. @klskl the information of x AND y is crucial. $\endgroup$
    – Evil
    May 3, 2016 at 15:57
  • $\begingroup$ @YuvalFilmus I see now, it is the point! (I was like, hamburger AND sandwich doesn't give 10 000 hits...) thank you $\endgroup$
    – sch
    May 3, 2016 at 16:05
95
$\begingroup$

The counting principle that applies here is inclusion-exclusion.

$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$

To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.

A Venn diagram may be more convincing to someone who may be intimidated by the notation.

Venn diagram

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ This is really good, will use this to explain to my mother, really clean, thanks! $\endgroup$
    – sch
    May 4, 2016 at 4:51
  • 3
    $\begingroup$ I'll expand on your diagram a little and point out that the reason $|X \cup Y| = |X| + |Y| - |X \cap Y|$ is because $|X \cap Y|$ is a part of both $|X|$ and $|Y|$ already, so when you add $|X| + |Y|$, you've counted it twice. You then subtract it out so that it's only counted once. $\endgroup$
    – Devsman
    May 4, 2016 at 20:23
  • $\begingroup$ The math works out, and it makes sense, but it doesn't match the set algebra right above it. $\endgroup$
    – Kevin Brown-Silva
    May 4, 2016 at 21:59
  • $\begingroup$ I remember doing Venn Diagrams when I was 4-5. They're really underrated. Thank you John Venn. $\endgroup$
    – Pharap
    May 5, 2016 at 14:29
  • 1
    $\begingroup$ @Pharap Indeed, such diagrams deserve our Venn-eration. $\endgroup$
    – Mason Wheeler
    May 6, 2016 at 20:19
13
$\begingroup$

Document 1: The cat is on the table
Document 2: My cat is black
Document 3: The dog is under the table
Document 4: What's the name of your cat?
Document 5: This is a black and white photo

Search for cat: returned documents are 1,2,4 (3 documents returned)
Search for black: returned documents are ...
Search for cat OR black: returned documents are ...

:-D :-D

Improve this answer
$\endgroup$
3
$\begingroup$

In simple words:

Search for X gives you n answers.
Search for Y gives you m answers.
Search for X AND Y gives you p answers.

In searching for X OR Y, the search breaks off as soon as it finds either X or Y. So if there's an X before a Y, that Y will not be counted in searching for X OR Y. Therefore your search for X OR Y will give you n + m - p answers.

It's important to note that the results will be the same, whether you do 2 searches, or just one. It's just that in summing the two searches, some documents are counted twice.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "the search breaks off as soon as it finds either X or Y." Doesn't this depend on implementation? An implementation could obtain all results for X, obtain all results for Y, and then combine the results in a way that eliminates duplicates. $\endgroup$
    – jpmc26
    May 5, 2016 at 0:32
  • $\begingroup$ @ArnabDatta What I described is most definitely not an XOR. "Eliminating duplicates" means eliminating the second copy, not all instances of that element. $\endgroup$
    – jpmc26
    May 6, 2016 at 8:47
  • $\begingroup$ True. I misunderstood. Removed my comment. $\endgroup$
    – Arnab Datta
    May 6, 2016 at 9:22
3
$\begingroup$

Imagine you have only one document. This is Document#1 with this:

X Y

Now imagine you have a search function that can give you all the documents based on one keyword:

search("X") => 1
search("Y") => 1

Notice that the number of documents in both cases is 1. Now if you have a search function that gives you the number of documents that matched one or more of the keywords supplied:

search("X", "Y") => 1

When you add the number of documents containing X to the number of documents containing Y, this causes you to count the same document twice. In your case, this happened 10000 times as pointed out above :)

Improve this answer
$\endgroup$

Your Answer

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

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