Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is a pretty standard problem for which there is a well-known solution. You simply sort the log files on each computer by URL and then merge them through a priority queue of size k (the number of items you want) on the "master" computer. This technique has been around since the 1960s, and is still in use today (although slightly modified) in the form of <a href="http://en.wikipedia.org/wiki/MapReduce">MapReduce</a>.</p> <p>On each computer, extract the URL and the count from the log file, and sort by URL. Because the log files are larger than will fit into memory, you need to do an on-disk merge. That entails reading a chunk of the log file, sorting by URL, writing the chunk to disk. Reading the next chunk, sorting, writing to disk, etc. At some point, you have M log file chunks, each sorted. You can then do an M-way merge. But instead of writing items to disk, you present them, in sorted order (sorted by URL, that is), to the "master".</p> <p>Each machine sorts its own log.</p> <p>The "master" computer merges the data from the separate computers and does the top K selection. This is actually two problems, but can be combined into one.</p> <p>The master creates two priority queues: one for the merge, and one for the top K selection. The first is of size N, where N is the number of computers it's merging data from. The second is of size K: the number of items you want to select. I use a min heap for this, as it's easy and reasonably fast.</p> <p>To set up the merge queue, initialize the queue and get the first item from each of the "worker" computers. In the pseudo-code below, "get lowest item from merge queue" means getting the root item from the merge queue and then getting the next item from whichever working computer presented that item. So if the queue contains <code>[1, 2, 3]</code>, and the items came from computers B, C, A (in that order), then taking the lowest item would mean getting the next item from computer B and adding it to the priority queue.</p> <p>The master then does the following:</p> <pre><code>working = get lowest item from merge queue while (items left to merge) { temp = get lowest item from merge queue while (temp.url == working.url) { working.count += temp.count temp = get lowest item from merge queue } // Now have merged counts for one url. if (topK.Count &lt; desired_count) { // topK queue doesn't have enough items yet. // so add this one. topK.Add(working); } else if (topK.Peek().count &lt; working.count) { // the count for this url is larger // than the smallest item on the heap // replace smallest on the heap with this one topK.RemoveRoot() topK.Add(working) } working = temp; } // Here you need to check the last item: if (topK.Peek().count &lt; working.count) { // the count for this url is larger // than the smallest item on the heap // replace smallest on the heap with this one topK.RemoveRoot() topK.Add(working) } </code></pre> <p>At this point, the <code>topK</code> queue has the K items with the highest counts.</p> <p>So each computer has to do a merge sort, which is O(n log n), where <code>n</code> is the number of items in that computer's log. The merge on the master is O(n), where <code>n</code> is the sum of all the items from the individual computers. Picking the top k items is O(n log k), where <code>n</code> is the number of <em>unique</em> urls.</p> <p>The sorts are done in parallel, of course, with each computer preparing its own sorted list. But the "merge" part of the sort is done at the same time the master computer is merging, so there is some coordination, and all machines are involved at that stage.</p>
    singulars
    1. This table or related slice is empty.
    1. POParallel top ten algorithm for distributed data
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJim Mischel
    1. USJim Mischel
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POParallel top ten algorithm for distributed data
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CODid you make any assumptions with regard to the contents of the log files? You state: *But instead of writing items to disk, you present them, in sorted order (sorted by URL, that is), to the "master".* If the URLs in a log file are all unique, then this basically means that you send the whole file over the the master. But the question states: *The log files are too large to fit in RAM and copy them by network.*
      singulars
      1. PO
      1. USReinier Torenbeek
    2. CO@ReinierTorenbeek: First, we don't send the entire file: just the URL and count. The log file presumably contains much more information. Second, the master has to see the count for every URL, otherwise it can't reliably know the counts. There are some other ways to tackle this (assign ranges of urls to individual machines, for example), but all include a lot of network traffic and more complex communication among the several computers.
      singulars
      1. PO
      1. USJim Mischel
    3. COYour presumption on the size of the log file sounds rather random to me. If you think it is valid to say that "The log file presumably contains much more information than just the URLs so we can send all URLs over the network", you might as well state that "The log file presumably contains much more information than just the URLs so we can store all URLs in memory". Yet you go through the lengths of an on-disk merge.
      singulars
      1. PO
      1. USReinier Torenbeek
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload