Top all-time · #736
Nick
Personal blog · blog.notdot.netprogramminghardware
Nick's personal blog at blog.notdot.net covers programming and hardware. Since 2007, 88 different Hacker News readers have linked it 117 times, most often “Damn Cool Algorithms: Quadtrees and Hilbert Curves”. The last post was in 2013, but the archive is still widely read.
Sometimes recommended · 13 of 40 sampled comments recommend it?
Why HN links it
HN readers link Nick Johnson's blog mainly for its Damn Cool Algorithms series, which explains algorithms such as fountain codes, HyperLogLog, BK-trees and spatial indexing, and for some App Engine posts.
- Recommended for · 13 comments
- Algorithm posts called must read, very good, incredible and really good explanations; blog called cool
Summarised by Claude from a sample of 40 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Most-linked posts?
- Damn Cool Algorithms: Quadtrees and Hilbert Curves11 people · 11 mentions · first linked 2009-11-09
- Damn Cool Algorithms: Levenshtein Automata10 people · 11 mentions · first linked 2010-07-28
- Build Your Own FPGA (2012)9 people · 10 mentions · first linked 2012-11-01
- Damn Cool Algorithms, Part 1: BK-Trees9 people · 9 mentions · first linked 2010-01-29
- Damn Cool Algorithms: Fountain Codes8 people · 8 mentions · first linked 2012-01-06
- Damn Cool Algorithms: Cardinality Estimation7 people · 7 mentions · first linked 2012-09-07
- Damn Cool Algorithms: Log structured storage (2009)6 people · 15 mentions · first linked 2009-12-15
- Damn Cool Algorithms6 people · 9 mentions · first linked 2012-12-23
- Damn Cool Algorithms: Secure permutations with block ciphers3 people · 3 mentions · first linked 2012-08-31
- Modeling relationships in App Engine3 people · 3 mentions · first linked 2010-10-01
What Hacker News says?
The BK-Tree, which allows fast querying of "close" matches, such as Hamming distance (number of bits different). http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK... I wrote a Python library implementing them a number of years ago: https://github.com/benhoyt/pybktree
Comment linking /2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
on “Ask HN: What are some cool but obscure data structures you know about?”- nl · 2012-01-06
Submitted Damn Cool Algorithms: Fountain Codes as a story · 306 points
HN discussion Just for fun: http://blog.notdot.net/2012/10/Build-your-own-FPGA
Comment linking /2012/10/Build-your-own-FPGA
on “I decided to make a graphics card for my Amiga 2000”Submitted Damn Cool Algorithms: Log structured storage (2009) as a story · 296 points
HN discussionThere is a very clever and beautiful algorithm that only uses the xor operation. It's the Luby Transform code, the simplest implementation of a Fountain Code. A Fountain Code lets you transmit a file over an unreliable connection (packets can be unordered, and even lost), with just a unidirectional communication. And this can be done just by xoring a random number of blocks from the file over and over! A very good e…
Comment linking /2012/01/Damn-Cool-Algorithms-Fountain-Codes
on “That XOR Trick (2020)”Submitted Damn Cool Algorithms: Homomorphic Hashing as a story · 234 points
HN discussionNick's blog is a must read for these sort of algorithms. See his original writeup on the HLL here: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
Comment linking /2012/09/Dam-Cool-Algorithms-Cardinality-Estimation
on “Redis new data structure: the HyperLogLog”Submitted Damn Cool Algorithms: Cardinality Estimation as a story · 233 points
HN discussionSo 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…
Comment linking /2012/09/Dam-Cool-Algorithms-Cardinality-Estimation
on “Redis new data structure: the HyperLogLog”Submitted Build Your Own FPGA (2012) as a story · 216 points
HN discussionIf 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 retri…
Comment linking /2012/01/Damn-Cool-Algorithms-Fountain-Codes
on “Harvard cracks DNA storage, crams 700 terabytes of data into a single gram”Submitted Damn Cool Algorithms: Levenshtein Automata as a story · 208 points
HN discussionHere are a couple of articles about a homebrew FPGA (only one logic cell, but it's step in your direction). https://hackaday.com/2012/09/20/homebrew-fpgas/ http://blog.notdot.net/2012/10/Build-your-own-FPGA
Comment linking /2012/10/Build-your-own-FPGA
on “IBM scientists say radical new ‘in-memory’ architecture will speed up computers”Submitted Damn Cool Algorithms, Part 1: BK-Trees as a story · 177 points
HN discussionRead up on fountain codes. A good starting point is the previous post on the same blog [1], actually linked in the first sentence of the article. The basic idea is that, instead of sending N blocks in the content file f, you have a block generator gen_block(f) which can create an infinite number of blocks as random combinations of input blocks (plus a little "magic"). A peer who downloads any 1.01N or so blocks can…
Comment linking /2012/01/Damn-Cool-Algorithms-Fountain-Codes
on “Damn Cool Algorithms: Homomorphic Hashing”Submitted Levenshtein Automata (2010) as a story · 172 points
HN discussionYes, you're right. We're not using SQL queries at the moment as that would be very inefficient, it was just as an example for a small dataset. I'm currently researching MVP's and reading on VP-trees, BK-trees [1], GNAT [2] and HEngine [3]. Do you have any advice? [1] http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK... [2] http://www.vldb.org/conf/1995/P574.PDF [3] https://www.cse.msu.edu/~alexliu/publica…
Comment linking /2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
on “Detecting duplicate images with Python”Submitted Damn Cool Algorithms: Quadtrees and Hilbert Curves as a story · 137 points
HN discussionLevenshtein distance is a metric [1] and discrete metrics can be indexed with BK trees, taking advantage of the triangle inequality. For a detailed explanation, see [2]. I know of no real world implementation of this, however. [1] https://en.wikipedia.org/wiki/Metric_(mathematics) [2] http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK...
Comment linking /2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
on “Levenshtein Distance”Submitted Damn Cool Algorithms: Levenshtein Automata as a story · 118 points
HN discussionAgreed 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 hel…
Comment linking /2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
on “One trillion edges: graph processing at Facebook scale [pdf]”Submitted Build your own FPGA as a story · 112 points
HN discussionVaguely related technique with similar goals (but I love the one posted here) http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Se...
Comment linking /2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers
on “UUIDv47: Store UUIDv7 in DB, emit UUIDv4 outside (SipHash-masked timestamp)”Submitted Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves as a story · 107 points
HN discussionSpace-filling curves can also be used for spatial indexing. Nick Johnson wrote a nice introduction to the technique on his blog: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...
Comment linking /2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
on “A practical use for space-filling curves”Submitted Damn Cool Algorithms: Levenshtein Automata as a story · 99 points
HN discussionEveryone this cool website gets posted I point them to this - http://blog.notdot.net/tag/damn-cool-algorithms
Comment linking /tag/damn-cool-algorithms
on “Levenshtein Automata (2010)”Submitted Damn Cool Algoritms: BK-Trees as a story · 96 points
HN discussionThere are a couple: http://blog.notdot.net/2012/10/Build-your-own-FPGA https://news.ycombinator.com/item?id=24252737 https://github.com/haojunliu/OpenFPGA https://www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-4...
Comment linking /2012/10/Build-your-own-FPGA
on “AMD Is in Advanced Talks to Buy Xilinx”Submitted Build your own FPGA (2012) as a story · 95 points
HN discussion
