16 ms·
Binary Decision Diagrams (2010)
- bra-ket 6y agonot my words but Don Knuth's from his lecture "Fun With Binary Decision Diagrams" at Stanford in 2008: https://news.ycombinator.com/item?id=25342643 https://news.ycombinator.com/item?id=25342643 it's really amazing what you can do with it.
- williamkuszmaul 6y agoFor 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.
- js8 6y agoAlso, I would say the whole concept of https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure is fundamentally new. (And looking at citations, they are not yet 35 years old.)
- williamkuszmaul 6y agoI 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).
- iainmerrick 6y agoConfluent/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.
- psykotic 6y agoThe 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.
- iainmerrick 6y agoThank 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.
- dmoldavanov 6y agoCache-Oblivious B-Tree is a variant of B-Tree The title says "fundamentally new"
- williamkuszmaul 6y agoNo, 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.)
- williamkuszmaul 6y agoAnother example is locality sensitive hashing (introduced in late 1990s), which can be used as a data structure to efficiently solve the nearest-neighbor problem.
- ajfjrbfbf 6y agoThere's Judy arrays too, I'm not sure if it's already included in one of those data structures.
- root_axis 6y agoYou remember the dates of when these data structures were first published off the top of your head? Are you a computer science professor?
- froh 6y agoSuffix 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 https://en.wikipedia.org/wiki/Suffix_array)
- psykotic 6y agoIt'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.
- dang 6y agoThis 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 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?
- bra-ket 6y agoI 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]. [1] it's really worth watching the lecture on BDDs by Don Knuth , starting around 13:32, his enthusiasm is contagious: https://www.youtube.com/watch?v=SQE21efsf7Y&t=13m32s https://www.youtube.com/watch?v=SQE21efsf7Y&t=13m32s Part 2 on ZDD: https://www.youtube.com/watch?v=-HzQYeqS9Wc https://www.youtube.com/watch?v=-HzQYeqS9Wc [2] TAOCP, volume 4A, Combinatorial Algorithms, p.202 - 280: https://www.amazon.com/Art-Computer-Programming-Combinatorial-Algorithms/dp/0201038048 https://www.amazon.com/Art-Computer-Programming-Combinatoria... There is a free preprint here https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz [3] https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr... [4] Bergman, David, et al. "Discrete optimization with decision diagrams." INFORMS Journal on Computing 28.1 (2016): 47-66. [5] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691. I hope that answers your question, dang, and sorry for title mishap.
- Pfhreak 6y agoWhat's with the title?
- raldi 6y agoList 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?
- voldacar 6y agoa quantum computer could do it in O(n^.5) with grover's algorithm
- raldi 6y agoHow would it beat O(1)? Even a quantum computer can't read in the wordlist without looking at every word.
- jordan_curve 6y agoQuantum 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.
- brians 6y agoHow do you put them into the set in O(n), exactly?
- raldi 6y agoSet insertion is O(1): https://stackoverflow.com/a/44080017 https://stackoverflow.com/a/44080017
- margalabargala 6y agoSet 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.
- vojta_letal 6y ago> Let U (the universe) be the set of all mainland USA states. I hope that it's an intentional joke.
- Jtsummers 6y agohttps://en.wikipedia.org/wiki/Universe_(mathematics) https://en.wikipedia.org/wiki/Universe_(mathematics) The set of all elements under consideration. It's a common term in math.
- andi999 6y agoWhat 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. I mean, are there like 2 or 3 pages missing?
- linux2647 6y agoThere are more links to other pages at the bottom, though the first one seems to take you to the original page
- dan-robertson 6y agoThere is also a next link at the top and a table of contents
- andi999 6y agoTrue. 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)
- tasty_freeze 6y agoIf 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.
- m12k 6y ago> 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.
- DSingularity 6y agoIs it easier to use BDD instead of SAT solvers?
- lou1306 6y agoI 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)
- dragontamer 6y agoThat'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.
- 6y ago
- CodexArcanum 6y agoSince (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?
- abecedarius 6y agoGeneralize 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.
- ulrikrasmussen 6y agoReduced 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.
- ComputerGuru 6y agoWhere'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.
- m4lvin 6y agoThis is a quote from Don Knuth, see the comment at https://news.ycombinator.com/item?id=25342972 https://news.ycombinator.com/item?id=25342972
- mellosouls 6y agoThe title is misleading then. There's no discussion of data structure history or originality of this one in the article.
- lacker 6y agoAnother 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.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- ben_w 6y agoPerhaps. 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”?
- jcranmer 6y agoThe 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.
- dreamcompiler 6y agoBlockchains 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. https://en.wikipedia.org/wiki/Blockchain#History https://en.wikipedia.org/wiki/Blockchain#History
- 6y ago
- m4lvin 6y agoWhen 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 https://doi.org/10.1109/TC.1986.1676819 And some shameless promotion, I maintain Haskell bindings for a BDD library: https://github.com/m4lvin/HasCacBDD https://github.com/m4lvin/HasCacBDD
- criddell 6y agoI clicked through and found the 35 year old paper is behind a paywall. That doesn't seem reasonable.
- deleted 6y ago[deleted]
- UncleOxidant 6y agohttps://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf https://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf
- deleted 6y ago[deleted]
- dragontamer 6y agoBDDs / 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. https://www.hillelwayne.com/post/decision-table-patterns/ https://www.hillelwayne.com/post/decision-table-patterns/ "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. ABC | True / False bit ----+----------- 000 | 1 001 | 0 010 | 0 011 | 0 100 | 1 101 | 1 110 | 1 111 | 1 Okay, simple enough. But what if... we "collapsed" the table to compress the values? ABC | True / False bit ----+----------- 000 | 1 001 | 0 01* | 0 1** | 1 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... A=1 -> 1 A=0 -> B=1 -> 0 A=0 -> B=0 -> C=0 -> 1 B=0 -> C=1 -> 0 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.
- raymond_goo 6y agoWould it be possible to test a tic-tac-toe field on winners with BDD or ZDD, removing the current need for doing it with "brute force"? See also: https://stackoverflow.com/questions/33510897/is-it-possible-to-check-for-the-winning-condition-of-a-game-of-tictactoe-using-j https://stackoverflow.com/questions/33510897/is-it-possible-...
- abecedarius 6y agoThat was an example in https://codewords.recurse.com/issues/four/the-language-of-choice https://codewords.recurse.com/issues/four/the-language-of-ch... (with BDD code in Python). Search for "tic-tac-toe".
- not2b 6y agoFrom https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram : 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.
- dang 6y agoIf curious see also 2011 https://news.ycombinator.com/item?id=2477011 https://news.ycombinator.com/item?id=2477011 (a bit) 2010 https://news.ycombinator.com/item?id=1335740 https://news.ycombinator.com/item?id=1335740 (even less, but good)
- adas0693 6y agoBinary 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/ http://www.cs.utsa.edu/~wagner/knuth/ .
- leetrout 6y agoDecision 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]. [0] https://news.ycombinator.com/item?id=25361372 https://news.ycombinator.com/item?id=25361372 [1] https://cloud.nextmv.io https://cloud.nextmv.io [2] https://nextmv.io/blog/how-hop-hops/ https://nextmv.io/blog/how-hop-hops/
- bjornsing 6y ago> 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...
- svat 6y agoAs 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 https://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf