Nick Johnson writes about algorithms and hardware, including his Damn Cool Algorithms series and a build-your-own FPGA project.
HN commenters link it as a great reference for the algorithm posts, such as quadtrees and Hilbert curves, and for the 7400 FPGA project.
Agreed re: the quality of Frank McSherry's posts - they're all great fun and push the technical envelope!
I'm glad you brought up Hilbert ordering. It's fascinating but I rarely see it. I usually see Z-order curves in their place - simpler and more intuitive but also less effective. Does anyone know of large scale databases with Hilbert ordering out of the box?
For anyone who hasn't seen them before, or why they help in ordering, I highly recommend "Portrait of the Hilbert curve"[1] and "Spatial indexing with Quadtrees and Hilbert Curves"[2]. The tldr is that they enable efficient multi-dimensional indexing. Given a request like "X < 40 and Y > 80", most databases need to run "X < 40" and then filter over the results for "Y > 80" - Hilbert curves allow you to find the query's intersection and only then perform minor filtering.
As far as large scale use of Hilbert ordering, Google use it internally for much of their geographical work. They even open sourced a Java library specialised in multi-dimensional indexing based on Hilbert curves called Uzaygezen[3].
[1]: http://corte.si/%2Fposts/code/hilbert/portrait/index.html
[2]: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
[3]: http://google-opensource.blogspot.com/2008/08/uzaygezen-multi-dimensional-indexing.html
If you store data onto 50 DNA strands, can you always read back all the data from all 50 strands, or does one need to store multiple copies of each in case the sequencer can't "find" a particular strand?
If one does need multiple copies, it would seem that this method suffers from the coupon collector's problem [1] (i.e. to collect all 50 strands requires collecting 225 random strands on average), and that the retrieval rate could be improved by using a fountain code [2], which allows each strand to simultaneously encode data at multiple addresses, which would decrease the number of strands required to be sampled to only slightly more than the number of strands worth of data requested.
[1] http://en.wikipedia.org/wiki/Coupon_collectors_problem
[2] http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes
So I think this is roughly what antirez is talking about with 'registers' for a counter.
From the article:
The standard error of HyperLogLog is 1.04/sqrt(m), where “m” is the number of registers used.
Redis uses 16384 registers, so the standard error is 0.81%.
My understanding is that the error is very small because you're averaging over 16,000 registers.
Edit: also, I think you want the mean because it'll give you back a precise/fractional power of 2 that is pretty close to the actual count.
The median would give you the nearest integer power of two, which is probably not a good estimate of the real count.
Double edit: looks like there's some research around improving averaging by throwing away outliers: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation
I'm a bit confused about the "hash" part of this... wouldn't you want to be able to go back from the hashed string to the original location? I can't think of much of a use for only being able to test locations to see if they match a proximity hash.
Internally, the space-filling curves are super interesting. I highly recommend this writeup [1] on how they're used in things like planet-sized maps. I've heard rumors that Google adjusts the offset of their space-filling curves to minimize large discontinuities near land and push them over the ocean instead.
[1] - http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
It could see cases where there is an impedance mismatch between the guest FPGA running on the host FPGA. The idea of the genetic algorithm to map out the search space is to find some identity function HDL that allows for a clean 1:1 or 2:1 mapping of resources without incurring some combinatorial inefficiency.
Maybe c-slowing could help with the timings, even if the area used was 4x it would still be a great research platform for reconfigurable computing since the bitstreams are proprietary, not documented and not portable.
http://blog.notdot.net/2012/10/Build-your-own-FPGA
this is all new to me and i'm struggling to find a friendly, simple introduction to the field. does anyone have a good link to, say, an introductory article on fountain codes? i'm starting to get a feel for the idea from reading various wikipedia pages, paper abstracts, powerpoints, etc, but a good "layman's" article would be great...
[update] huh. just after posting i started searching for "fountain codes" and found this - http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes (previously had been searching for luby, raptor, etc).