What is with this article, or is it me? Caption 'BDD' then some examples leading to 'how can we solve this efficiently' great, now I expect something about BDD but I get 'Families and ZDD' with an extremely short explanation what ZDDs are. Then references. Then the statement BDDs are better than ZDDs. Then end.
> ZDD stands for zero-suppressed binary decision diagram but this is unimportant
It's not just you. This article is written in the "terse yet barely comprehensible" fashion of someone wanting to cut to the chase, but leaving out so many details that the point or flow of it goes missing for anyone not in the author's head.
If you look at the sidebar and the URL, you'll see this is one page out of a set of notes on ZDDs. That is why BDD's are just touched upon.
The real question is why was this particular link submitted as newsworthy and why did it get to the front page of HN? It is just a sidebar on the thing the author was actually writing about.
Thank you for posting this. I often go though HN stories and think "Wait what does this have to do with X?" and I often assume that I just don't understand the topic well enough for the article to make sense... because hey folks on HN up-voted it so it must make some sense. And I'm not wrong about that sometimes, sometimes I just don't grok.
True. But does it get better? As far as I understand the next two pages dont mention BDD and then it is all ZDD (the complete article seems to be really about ZDD, whatever this may be)
When I first learned about BDDs I found the original paper by Randal Bryant from 1986 surprisingly accessible: "Graph-Based Algorithms for Boolean Function Manipulation" https://doi.org/10.1109/TC.1986.1676819
Binary decision diagrams (BDDs) have been a big deal in electronic design automation (EDA); many of the BDD developments have happened as a result of the applications in EDA.
For a recent and comprehensive coverage, you can check out D. Knuth's fascicle as part of his well-known book. The BDD fascicle and other fascicles are available at http://www.cs.utsa.edu/~wagner/knuth/ .
Where's the title from? The actual title of the linked page is just "Binary Decision Diagrams" and the rest of the title does not even appear on that page.
Decision diagrams in general are really neat (and approachable in many contexts).
My current employer, nextmv (YC W20), has built our solver in Go and it uses decision diagrams[2].
Just today we launched our free cloud platform[0][1] which exposes our fleet routing model via an API. So if you’re curious about modern uses / systems around decision diagrams take a look at our site, app and blog[2].
Another fundamentally new data structure developed in the last 20 years is the blockchain. Yes, it's overhyped in many ways, and the word "blockchain" itself is often used in a nonsensical way, but the fundamental principle of a chain of blocks with proof-of-work included really is a data structure that solves the problem of untrusted coordination in a novel way.
Blockchains are glorified Merkle Trees (and in the case of Bitcoin, with proof-of-work added for zero-trust distributed operation). The data structure is not new. The name is.
The parent said 20 years, which is just barely long enough to to be the time for which reasonably secure hash functions have been available. If they had said 30 years, they'd have an excellent argument.
Chains of blocks and merkle trees are distinguishable from linked lists and binary trees purely by the use of hash functions instead of pointers. But that turns out to be really powerful in a way that the pointer versions aren't, if those hash functions are cryptographically secure.
Being “cryptographically secure” is a relative thing: during the 90s, md5 was cryptographically secure, until it wasn't in the early 2000s. What we take for granted in terms of cryptographic security could collapse after one breakthrough (that's why SHA-3 was designed completely different from SHA-2, to have a replacement handy when the later will be broken).
The difference is that with MD5, attacks were found relatively quickly. Introduced in 1992, and by 1996 cryptographers were already recommending that people switch to a replacement such as SHA-1 or RIPEMD-160.
SHA256 meanwhile was introduced in 2001, and since then no significant attacks have been found. So not only has it withstood attack for much longer, cryptography has advanced greatly compared to what we knew in 1992.
That still isn't a guarantee of future success. But look at it this way: I don't think you could have introduced Bitcoin in 1998. Hash functions were just too new to be trusted to the extent that Bitcoin requires.
Cryptography as a field advances and the next generations are better than the previous. But even if md5 was pretty poor compared to modern hash functions, AFAIK there is still no working preimage on md5 (correct me if I'm wrong, maybe there's been recent development I'm not aware of), which means bitcoin would still be fine if it was launched in 1995 with md5 as its hash function! (assuming it had transitioned to a better scheme later to avoid collisions attacks).
In fact bitcoin is a pretty good counter-example to your point. It was launched too early, with a poor hash function[1], and yet is still a success.
[1] because bitcoin didn't used a brute-force resistant hash function, Satoshi's dream of “everyone is a miner” quickly disappeared a was replaced by a monopolistic cartel of professional miners.
> assuming it had transitioned to a better scheme later to avoid collisions attacks
Exactly. Collision attacks are fatal to Bitcoin, because they can make it impossible to achieve consensus over what is the valid version of the blockchain data. If you get advanced warning, transition is possible with some caveats. But hoping for advanced warning is risky when money is on the line (collision attacks can even be used to steal money in certain scenarios, eg with certain ways of doing multisig).
> because bitcoin didn't used a brute-force resistant hash function
That's really a topic in of itself. There is no such thing as a non-"brute-force-resistant" PoW function.
Collisions only affect new transactions, they aren't able to tamper with the existing blocks (you need preimage attack for that), and for the record the first collision on md5 only came in 2004 and 2017 for sha1, way after the theoretical vulnerability was proven. There's plenty of time to move from one hashing scheme to another.
> There is no such thing as a non-"brute-force-resistant" PoW function.
Well, maybe on the semantic debate, but there's a big difference between fast hash functions (sha-2 and the likes) and slow-by-design ones: ASIC.
Perhaps. I’ve seen the chain-of-hashed-commits in version control software being described as an antecedent of the bitcoin style of blockchain, though I don’t know enough about the inner workings of any version control system well enough to compare, let alone the ones in use 20 years ago.
Edit: did I misread the title the first time, or has it changed from “the last 20 years” to “the last 35”?
The distributed version control systems you're talking about (Bazaar, Mercurial, and Git) all come out within a few weeks of each other in 2005. The chaining hash system for VCSes is either new or obscure before these systems adopt them: the major prior systems like RCS, CVS, and SVN instead rely on a central database with more-or-less sequential revision numbers.
BDDs / ZDDs are really cool, but this isn't a good link for Hacker News IMO. And the title is clickbait: its not the famous Knuth quote (and the famous Knuth quote isn't even in the blogpost).
Maybe the Wikipedia page is a better start. Or maybe a blogpost out there is a better description of BDDs.
-------
Okay, so what is a BDD? Lets start with what problem we're trying to solve.
"Decision Tables are useful". Lets start with that. They're useful in a variety of algorithms and situations. The above blogpost is your "ELI5" introduction to this subject.
Now lets start talking HARD problems, I'm talking NP-hard, like traveling salesman. We can use "decision tables" to decide if "CityA + CityB" should be in a certain order in the path, or if it should be "CityB -> CityA", and the like. Ultimately, its all a table of decisions, but this table starts getting big. Very, very, very big.
Exponentially big even. Every "column" you add doubles the size of the table. We can't fundamentally get around this, but we can offer a kind of "compression". Lets start with a 3-bit table and think about things.
Now instead of taking up 8-rows, the table only takes up 4-rows. That's the general gist of the problem: these "tables" clearly have compression available.
Now Binary Decision Trees are a compression methodology. Instead of storing a table, you store a graph. One such graph is...
Its the same information as the table, but now in graph form. It achieves the "compression" thing we're looking for.
Ultimately: that's the goal. To "compress" these tables so that they take up less RAM. But we still want to perform operations on them (such as AND/OR/NOT, but also cross-joins and a bunch of relational-algebra). The overall discovery was that the graph-form, the Binary Decision Tree, is actually pretty efficient with a large number of operations.
----
EDIT: Ah right. And the "key feature" of BDDs is the ability to share "subtables" between different tables. Notice that B=0 has two links, so there is substantial "column-savings" compared to the original table.
The "compressed table" had to store 000 and 001 in two different rows. But the A=0 -> B=0 link is "redundant information" in that situation, and itself can be compressed.
The graph form compresses that information, while the "compressed table" doesn't. These small savings don't matter on 3-bit examples. But on a 16-bit or 32-bit or larger graph, those sorts of things really add up to huge amounts of compression.
And once you start sharing subtables among "unrelated" tables (ex: lets say you have 100-such tables. The graph form provides an obvious "common subtable" that can be shared between say 20+ tables at a time. The "compressed table" cannot share such subtables in any obvious way).
You don't want to go too crazy: the optimal sub-table compression is itself an NP complete problem. But don't worry about that: this is quite common on NP-hard situations. You need to solve NP-hard subproblems to solve the greater NP-hard problem efficiently...
Instead, find a greedy, "decent" solution to compression. Simple heuristics (column ordering heuristics, variable-ordering heuristics, etc. etc.) and the like are common here. As long as it works kinda-sorta okay, you're probably fine.
This is a fantastic comment, much more valuable than the linked article, and more clear and the concise than the Wikipedia article. Maybe the better blogpost out there is the one you write based on this comment? You're most of the way there ...
The secret is to use little inaccuracies, and then not sweat the details, lol.
Ehh, I've got it close enough at this point. Its no where near a rigorous description of BDDs, but... sometimes an inaccurate but simple explanation is more useful than a fully accurate description.
In his video lecture Fun With Binary Decision Diagrams (BDDs),[8] Donald Knuth calls BDDs "one of the only really fundamental data structures that came out in the last twenty-five years" and mentions that Bryant's 1986 paper was for some time one of the most-cited papers in computer science.
List all 5-letter words that remain words after replacing a b with o. How can we solve these efficiently?
Put them in a set(), then iterate over its members and report any that contain b and are still in the set after the string replacement. O(n), which can't be beaten.
Edit: If you're downvoting, could you post a comment saying why?
I don't understand how this is O(n). You have to go through the set once to select each word and replace a b with o, then you have to go through the set again to search for the new word resulting from the replacement.
That is, if Ws is the set of 5-letter words we want the set Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ws}. You can see that that's an O(n²) operation (each ∈ is an iteration over Ws).
jayd16 proposed omitting every word that has a b in it from the "search space". I take this to mean, in practice, that we start by initialising a set Ss = {w: w ∈ Ws, b ∉ w}. Then Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ss} and the time complexity is O(|Ws||Ss|) which is again O(n²) in the worst case (where Ws = Ss). Note also that some words in Ws may have more than one b and since we are only replacing "a b" (i.e. one b) we may remove valid words this way.
In any case, I don't see an obvious way to do this in O(n). Maybe I'm not thinking straight though, it's way past bed time.
Two algorithms that are both O(n) can be wildly different in execution times.
More, an O(n) algorithm can be more "efficient" than an O(lg(n)) one, for some values of n. (Or just in another facet. Maybe you actually do care about space.)
The claim wasn't how to do it fast, per se. It was how to do it efficiently. And comparing two algorithms of the same order can have a wide difference in the answer.
I guess you're assuming a hash set and ignoring collisions?
So you fill the set with in O(1*N), again loop through the (original?) list assuming its O(N) to do so searching the set for replacements?
So at least a few passes through every element.
You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts.
>> You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts.
I'm not sure that works. Suppose "abab" and "abao" are words. Note the problem spec says "after replacing a b with an o", i.e. after replacing _one_ b in a word with an o. If you exclude all words with a "b" and replace one b with an o in "abab" you will get "abao" which you have excluded, so you will think it's not a word. I think at best you can ignore only words with a single b.
No collisions in the input does not mean no collisions in the hash algorithm. In reality there's book keeping overhead in a hash data structure that might be significant.
Quantum computers can see information about more than one word with just a single “look.”
You’re right to think this is impossible though. Grover’s algorithm was one of the first examples of something that clearly could not ever exist classically.
Set insertion is O(n) in this case. An O(1) set insertion refers to constant time regardless of the size of the inserted element, but if you add one element to a set, then add a billion elements to the set, the latter will take about a billion times longer.
Since (B|Z)DDs are basically just fancy DAGs, I wonder what the relationship between them and other automata is like? Like can some of these techniques be applied with regexps to make something truly monstrous?
Generalize BDDs to multiway decision diagrams: instead of binary trees on 0 and 1, make n-ary trees on a bigger alphabet. (You probably want to represent the nodes sparsely, not |alphabet| pointers in every node.)
This can directly represent a regex with | operators but not Kleene star. The DD canonicalization automatically makes this structure share suffixes, but not prefixes.
Reduced Ordered BDDs coincide with the minimal DFAs that accept the language of bit vectors encoding the boolean assignments that satisfy the modeled predicate. That is, this holds if the BDD has not had the "skip test if both outcomes less to the same sub-bdd" optimization applied, which anyway only reduces its size by a constant factor.
> Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
So these “BDDs” allow for “efficient” solutions to the traveling salesman problem? Call me a skeptic, but I’m skeptical...
As with any typical problem (NP-hard or otherwise), very large instances are infeasible to solve, and very small instances can be quickly solved. What's interesting is the in-between region: instances that can be solved within a human lifetime, but where efficient algorithms and data structures can often make the difference between getting the answer in days (or months) versus seconds.
For example, the first computation of the exact number of closed knight tours on an 8x8 chessboard was done in 1996 using BDDs. (Their program actually had a bug which they corrected later and in the meantime another method gave the correct answer, but the method itself was sound.)
It's indeed true that the travelling salesman problem (TSP) is a “hard problem” in the sense of being NP-complete. But this implies only that no algorithm is known whose running time grows polynomially as a function of the input size (as the size goes to infinity). The Concorde TSP Solver for instance has solved instances with as large as 85,900 vertices, and instances with about 50 vertices can be solved quickly even with simple branch-and-bound heuristics.
In this case (all the numbers in this paragraph are from Knuth's treatment in Volume 4A of TAOCP), the graph of the contiguous US states has 48 vertices and (it turns out each state has on average only a little over 4 neighbours) 105 edges. A Hamiltonian path is some subset of these edges that covers each vertex exactly once. What BDDs/ZDDs enable is to succinctly encode which of these 2^105 subsets are Hamiltonian paths—turns out it can be done with a data structure having 28808 nodes. Once you have constructed this data structure (ZDD), you can now answer many questions about this entire set of Hamiltonian paths (more quickly than you could by backtracking or similar): how many of them are there? (68,656,026.) How many are there that end in California? (2,707,075.) Which one is shortest (this is the standard TSP problem, for which there are many other methods) (11,698 miles), and which one is longest (18,040 miles)? What is the lexicographically first one (according to some order)? Can you quickly sample a path at random (such that each path is equally likely to be picked)? Etc.
For arbitrary worst-case input (which is what the NP-hardness of TSP is about), the corresponding BDD/ZDD may turn out to be too large, so we cannot do any of this efficiently. The magic is that in many cases of practical interest, we happen to get small BDDs. Knuth's treatment (57 pages of text, 22 of exercises, 58 of solutions) ends with a caveat that among other things points out:
> They apply chiefly to problems that have more solutions than can readily be examined one by one, problems whose solutions have a local structure that allows our algorithms to deal with only relatively few subproblems at a time.
As Knuth mentions, the 1986 paper that (re)introduced BDDs (ordered and reduced, as the term generally means today) was for many years the most-cited paper in computer science according to CiteSeer. It's very readable and mentions the advantages and disadvantages: https://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf
I only (kind of) know BDDs because of their application to symbolic model checking. Moreover, I will be very low on details. So take this reply with a pinch of salt. Short answer: they're different.
BDDs allow for some formula manipulations that make it easy to devise "unbounded" model-checking (UMC) techniques (i.e., they can explore the full state space of a system).
On the other hand, if you are only interested in a bounded exploration of the state space (i.e., check only those states that are at most "k" steps far from the initial state), then you can usually unroll the transition relation, encode it as a CNF formula, and just feed it to a SAT solver. This approach is usually faster than BDDs.
To extend SAT solvers to the UMC case, you have to either devise some tricks to do the aforementioned formula transformations with a SAT solver too, or use the solver to find an inductive argument (if the system is safe up to k steps, it will be safe up to k+1 step, for any k). This is known as k-induction.
Seminal papers in this field include:
J. R. Burch et al., “Symbolic model checking: 10^20 states and beyond,” in LICS 1990. doi: 10.1109/LICS.1990.113767. (BDD-based symbolic model checking)
A. Biere et al., “Symbolic model checking without BDDs,” in TACAS 1999. doi: 10.1007/3-540-49059-0_14. (SAT-based bounded model checking)
K. L. McMillan, “Applying SAT methods in unbounded symbolic model checking,” in CAV 2002. doi: 10.1007/3-540-45657-0_19. (SAT-based unbounded model checking)
M. Sheeran et al., “Checking safety properties using induction and a SAT-Solver,” in FMCAD 2000. doi: 10.1007/3-540-40922-X_8. (k-induction)
That's like asking if using hashmaps are easier than using a database.
You'd probably use BDD in a SAT solver. BDDs grossly cut down on the storage requirements of your variables and their possible "true/false" states... while almost all SAT-based math (union, intersection, etc. etc.) remains efficient.
BDDs aren't the only datastructure (ex: a B-Tree could beat a HashSet in a Database). But BDDs are a very, very good data-structure for SAT.
Uhm, I'm not sure about that. Most state-of-the-art SAT solvers nowadays will rely on CDCL [0], which does not need BDDs. A recent paper [1] is quite clear on that:
> The Conflict-Driven Clause Learning (CDCL) solvers form the core of the algorithms for solving the Boolean satisfiability problem (SAT).
There is a huge slide deck [2] which contains (in the first part) a lot of details about modern SAT solving. Highly recommended reading for those interested.
BDDs are simple and predictable provided you know that the variable ordering that you're using will compactly encode your problem. A SAT solver might not be as predictable (though I don't have the experience to say how big this issue is in practice).
A BDD can also efficiently answer questions like "how many ways can you satisfy this formula?" (subject to the same caveat about problem suitability).
> BDDs are simple and predictable provided you know that the variable ordering that you're using will compactly encode your problem.
Sadly, variable ordering is NP-Hard. This is brutal for static analysis applications where BDDs seem like they are going to save the world but often end up crushing dreams.
This refers to the submitted title ("BDD, the only fundamentally new data structure developed in the last 35 years") whic we've since reverted. If you want to add this sort of gloss to a submission, please do it in the comments. That way you're in keeping with the site guidelines (https://news.ycombinator.com/newsguidelines.html), and your addition will be on a level playing field with others'.
On another note: what are some amazing things you can do with it?
I wouldn't do it justice[1], it deserves a blog post or a book [2] but in general solving almost any boolean algebra problem, in hundreds, and hundreds of thousands variables, very efficiently and in very compact representation (via ordered sparse bit vectors[3]).
While with Karnaugh maps you can simplify a boolean function with a few variables, BDDs can solve for thousands, fast.
And no need to explain applications of high-dimensional boolean algebra on HN, with boolean algebra you can solve any logic problem expressed as boolean function, any combinatorial problem (except for those with nasty functions), classic graph theory problems.
Surprisingly it allows to solve optimization problems[4], like boolean programming, SAT solver, max independent set or max cut in graphs, very efficiently, it can be used in something like belief propagation or lattice induction for inference, but if that's not enough you can use it for random number generation, lossless compression, perfect hashing, etc, etc.
I haven't seen such a versatile data structure elsewhere, most of the other things developed in the last 35 years, like the ones in the comment below are solving special cases, BDD is truly one of the most fundamental and severely underrated "swiss army knives" (that is in CS, EE people know it very well in logic synthesis and verification, BDD's first "killer app").
It's probably easier to list what you can't do with BDD, kind of like what you can't do with (high-dimensional) boolean logic.
I think it skipped the radar of CompSci community at large because it was too quickly siloed into "that circuit analysis/verification tool used by electrical engineers".
Yes, it's "just" a DAG but with very particular (and very simple) constraints which allow it to solve infinite variety of problems in a very elegant and surprising way [5].
Just watching through the Knuth lecture now. 40 minutes in (~54m mark) and I learned something new (to me) and useful and cool (randomly picking maximal independent sets of graphs). And I'm only half way in. Very nice; thanks for the recommendation :)
For perspective, here are some examples of other data structures in the past 35 years that are fundamentally new. (I am only including data structures that differ significantly from their predecessors)
B-epsilon trees: These allow asymptotic speedups for insert/update/delete operations on search trees in external memory (Introduced in 2002 by the paper, Lower Bounds for External Memory Dictionaries)
Cache-Oblivious B-Trees: This is an external-memory search tree that exhibits optimal behavior on a cache with any (possibly unknown) cache-size and cache-line size parameters. (Introduced in 2000 by the paper Cache-Oblivious B trees)
Fusion trees: This allows for search operations in a small binary tree (i.e., a tree whose size is polynomial in the machine word size) to be performed in constant time, rather than logarithmic time. (Introduced in 1990 by the paper Blasting through the Information Theoretic Barrier with Fusion Trees.)
Cuckoo hashing: This is a hash table design introduced in 2001. In 2009, the paper De-amortized Cuckoo Hashing showed how to make all operations in Cuckoo hashing take truly constant time with high probability. This remains (as far as I know) the only known technique for guaranteeing constant-time operation for a hash table without the use of bit manipulation tricks or the method of four Russians.
These are just examples off the top of my head. I'm sure there are many more.
I agree. Related to this, sketches (i.e., small data structures that can be used to recover information about large data sets) are also fundamentally new (and most of the techniques are from the 21-st century).
Confluent/persistent data structures, which I believe was novel research by Chris Okasaki in the late 90s (at least that’s when I first heard of it -- I was in CS academia at the time).
Edit to add: I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis. But maybe I’m wrong! Would love to hear about another other takes on this or links to other research strands I’m not aware of.
The term 'persistent data structure' goes back to papers by Tarjan, et al in the 80s but the path copying technique is much older. My favorite technique from one of those papers, the in-place v2 trick, is an alternative to path copying that achieves amortized O(1) space per update as opposed to O(depth) space per update for path copying; this only gives you partial persistence (linear history like an MVCC database system, not branching history like a purely functional data structure or Git) but often that's all you need. (There's also an extension of the trick to full persistence but it's not very practical.)
> I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis.
I believe the direct inspiration for Clojure's persistent vectors and maps are Bagwell's papers on HAMTs, which weren't so much a new data structure as an example of data structure engineering. Okasaki's thesis has several contributions but its main theme is how you can apply amortization in the purely functional setting if you have laziness or memoization, which is in a very different direction.
Thank you! So I was looking at it from a purely functional point of view, without accounting for the earlier non-pure work in the literature. That makes sense; I was deep in the early Haskell world at the time.
Suffix Arrays: with their meanwhile linear time construction they allow for very efficient pattern matching, indexing and more efficient compression algorithms. (introduced around 1990 https://en.wikipedia.org/wiki/Suffix_array)
It's an important theoretical result, but the optimized library almost everyone uses (libdivsufsort) is based on an O(n log n) time algorithm; I haven't seen any competitive implementations of the linear-time algorithms.
Another example is locality sensitive hashing (introduced in late 1990s), which can be used as a data structure to efficiently solve the nearest-neighbor problem.
No, cache-oblivious B-trees are not a variant of B-trees (although I can see why you might think the name suggests that). I classify them as fundamentally new because they technique they introduce was fundamentally different than past data structures. (Their fractal-like layout allows for them to achieve optimal behavior on an arbitrarily parameterized cache.)
I mean, are there like 2 or 3 pages missing?