StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Karl's approach works just fine, but we can greatly reduce the amount of data produced by the mappers.</p> <p>Let <em>K</em> the number of samples you want. We'll assume that this is small enough to hold in memory on one of your nodes. We'll assign a random value to each matching row, and then use a modification of the <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements" rel="noreferrer">selection algorithm</a> to find the <em>K</em> smallest values.</p> <p>At the setup part of each mapper, create a <a href="http://en.wikipedia.org/wiki/Priority_queue" rel="noreferrer">priority queue</a>; a <a href="http://en.wikipedia.org/wiki/Fibonacci_heap" rel="noreferrer">Fibonnacci heap</a> is a good choice for this. We'll be using floats as the priorities; if you have a huge amount of data, doubles may be more appropriate to avoid there being ties. For each row that matches your condition, insert that row into the priority queue with a randomly chosen float between 0 and 1 as the priority. If you have more than <em>K</em> things in your queue, remove the highest valued item (this is opposite of the terminology of a standard Fibonnacci heap).</p> <p>Finally, at the end of the mapper, emit everything in your queue. For each item you emit, use as the key the priority as a <code>FloatWritable</code> and some representation of the corresponding row as the value (the row ID, or perhaps the entire row contents). You will emit only <em>K</em> values per mapper (or less if there were fewer than <em>K</em> matching rows in that mapper).</p> <p>In your single reducer, Hadoop will automatically scan through the keys in order from lowest to highest. Emit the rows corresponding to the first <em>K</em> keys you see (the <em>K</em> lowest), then quit.</p> <p>This works because each matching row has the same probability of having one of the <em>K</em> smallest float values. We keep track of the <em>K</em> smallest floats for each mapper to make sure we don't miss any, and then send them to the reducer to find the <em>K</em> smallest overall.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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