NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.
All the Perl that's Practical to Extract and Report
I pour the blue liquid on the red liquid. If it doesn't blow up on my
face, I proceed to turn up the flame under the blue liquid, and so on.
I have very little idea of what I am really doing, I just like the
pretty colors :-)
-- Jarkko Hietaniemi
Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.
How beefy is the database? (Score:1)
Can we assume that it is capable of doing a join like this?
SELECT with1.page_id
, with1.number_of_occurrences
FROM reverse_index with1
LEFT JOIN reverse_index without1
ON with1.word_id = ?
AND without1.word_id = ?
AND with1.page_id = without1.page_id
WHERE without1.page_id IS NULL
ORDER BY with1.number_of_occurrences DESC
If we are forced to assume that this can't work, then the simplest way to proceed is to sort each result set with a merge-sort (doesn't have to be kept in memory), then do a "merge-filter", then do another sort to get it into the order you want.
If you have lots of machines to throw at this (like Google does) then each of these steps can be set up as a parallel algorithm, and the whole algorithm, excepting a final gathering of data at the last step, can run in parallel. But even that final gathering can work off of partially summarized data, with the result that your response time can be kept bounded.
All good stuff to know, but most people won't run into a situation where you can't just shove it down to the database and let the database take care of it.
Reply to This
Re: (Score:1)
Yes, there is a Google's paper about MapReduce algorithm which might be used for the situation.
People whom I asked usually forgot that even to display 10 top links you cannot perform two queries with LIMIT 10 (or 20), one to select pages with most occurences for the word1, and then grep them to exclude those with word2: in this case you can get into multiple queries.
Re: (Score:1)
Heh, that reminds me of an interesting challenge I faced once.
I was creating a basic desktop query tool which would be used to summarize how much money had been spent in, say, a particular area on a particular kind of product. Products were categorized at various levels. For example a specific glass beaker would be classified as the exact item, as a glass beaker, as a laboratory supply made out of glass, and under laboratory supplies.
I had two interesting requirements. The first is that the database ship