Stories
Slash Boxes
Comments
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

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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.

    • 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.

      • 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