Visualizing Algorithms

http://bost.ocks.org/mike/algorithms/

by callum85 • 12 years ago

1557 87 12 years ago

bost.ocks.org

mbostock11• 12 years ago

Author here, ask me anything. And don’t miss the related work section at the end — there’s a ton of links there to inspiring work.

viggity• 12 years ago

this is only slightly tongue in cheek, but do you ever get tired of being so awesome? Seriously. this shit is amazing.

thanks for all the time/effort you've put into d3. my side project (machete.io) certainly wouldn't be possible without it.

mbostock11• 12 years ago

Ha, thank you. The trick to appearing awesome is to surround yourself with people doing awesome things, and then figure out how to synthesize their ideas into something new and (hopefully) transformative. Most of the ideas & forms in my article aren’t new, but I tried to weave them into a broader look and derive some interesting variations.

webXL• 12 years ago

Awesome side project. See you're using Crossfilter. Sports data seems like natural fit. As a huge football (American) fan, and former player in college, I know how valuable down/formation data can be when trying to come up with a game plan. It would be interesting to see who's signing up for your beta ;)

austinhyde3• 12 years ago

Oh man, that's awesome! I see I'm not the only one with an addiction to d3 and knockout. I've actually just recently gotten around to playing with the two of them at once: http://jsbijn.com/gitufejo/3/edit?html,js,output

jpeterson• 12 years ago

First of all, amazing article!

However, I believe that the bit about light being a "continuous" signal in the first paragraph invites conflicting thoughts of wave / particle duality, which distracts from and is not at all relevant to your point.

The eye samples light because it connects to a machine with a fixed number of inputs. This setup would also require sampling if the signal were not continuous at all, but instead consisted of a much larger number of discrete parts than the "sensing" equipment could handle.

mbostock11• 12 years ago

Yes, you can consider light a discrete signal, too. I glossed over this because resampling a discrete signal is harder to explain than sampling a continuous signal; I think about it as first reconstructing a continuous signal (typically by convolution) and then sampling it, as described here: http://graphics.stanford.edu/courses/cs248-05/samp/samp1.htm...

subbu• 12 years ago

Most d3 books out there are entry level. They don't cover advanced concepts which are needed to build serious visualizations. The only way to learn advanced stuff is to go through your bl.ocks, which could be daunting sometimes without comments. It'd be awesome if you can think of writing an advanced book. I know its too much to ask for, especially considering your active contribution on Google Groups and StackOverflow.

mbostock11• 12 years ago

I’ve made a couple starts on books but so far haven’t been able to stick with it long enough to finish; it becomes too tempting to release content as examples or smaller articles. And while those are useful, too, piecemeal content lacks the cohesiveness / comprehensiveness / depth of a book… so I’ll keep trying and hopefully find a way to make a book in the future.

(And by “book”, I’m including online publications like Mark Pilgrim’s excellent /Dive into HTML5/. I’d almost certainly publish online given the interactive nature of the subject.)

pgbovine• 12 years ago

How many hours did it take for you to make this page? (even after you created your initial talk.)

I love these sorts of interactive, visual essays and would love to find ways to lower creation times.

mbostock11• 12 years ago

Writing always takes longer than I expect. The issue wasn’t technical (it wasn’t too hard to take my examples from bl.ocks.org and embed them on a page). It just required more thought to take my speaker notes and translate them into prose. You can get away with more hand-waving in speech than in writing.

Also, there were a few things in my talk that I wanted to fix, like replacing the rainbow color scale with something more effective.

The examples themselves I worked on intermittently, typically for an hour or two in the evenings. I got interested in mazes as an analogy for design process when I gave a talk at OpenVis earlier in the year.

cs702• 12 years ago

Have you ever considered visualizing artificial neural networks in training or in operation?

Speaking purely from a selfish standpoint, it would be awesome to SEE what back-propagation "looks like" with different neuronal activation functions, or what feature learning by restricted Boltzmann machines "looks like," or how dropout causes networks to generalize better -- to name just a few possibilities.

If anyone can visualize neural network algorithms in a way that is intuitive and beautiful, it's you!

Osmium• 12 years ago

Seconded. I was recently trying to find a good resource to simply and concisely explain (or at least give a 'feel' for) artificial neural networks to someone and came up blank. Everything I found was either assumed too much domain-specific knowledge or was too long.

mbostock11• 12 years ago

I haven’t done much with neural networks, but Christopher Olah wrote a fantastic post on visualizing low-dimensional ones:

http://colah.github.io/posts/2014-03-NN-Manifolds-Topology/

pospeselr• 12 years ago

If you're interested in visualizing RBMs or AutoEncoders in real time, you should check out my project VisualRBM:

https://code.google.com/p/visual-rbm/wiki/Screenshots

It basically lets you do exactly what you're looking for. I'm going to eventually add support for visualizing each layer of a DNN during back-propagation training, but that's several releases away.

strebler• 12 years ago

I have found this useful for helping visualize what's happening inside a neural net: http://cs.stanford.edu/people/karpathy/convnetjs/

pokpokpok• 12 years ago

thanks for producing such beautiful work! I've used these visualizations to explain what a programming thought process is like.

infogulch3• 12 years ago

Beautiful! These would be very useful to someone learning these algorithms, but also to someone interested in creating their own visualizations. I like how you highlight the drawbacks of different types of visualizations and demonstrate that different visualizations can have different goals, and offer creative solutions for both.

One nitpick with the maze visualizations though. I found that the maze color flood animations have the same issue that you mentioned sorting has: animations are frustrating to watch because you have to wait and then rely on memory to recognize patterns. Specifically, I found the color scale rotation was much too fast to see large patterns, and even small patterns were too dense to be able to trace backwards after the maze had been fully colored.

I have an idea for an alternate visualization: Only show the fully colored maze (no intermediates), but vary the color rotation length over time from frame to frame. You'd be able to see color rippling through the maze and be able to follow the ripples over both large scale and small scale features.

mbostock11• 12 years ago

Thanks for the feedback. There’s a similar idea I also want to try, which is to use color cycling for the mazes. Like this:

http://www.effectgames.com/demos/canvascycle/

Varying the rotation length sounds interesting and, like you suggested, could be great for seeing both micro and macro features. There was a bug previously where the Prim’s visualization rotated twice as fast, and it looked quite different!

mtdewcmu2• 12 years ago

Sorting-algorithm animations have a long history, and, when I was younger, I thought these animations were fun to watch, but I never learned anything from them. At this point in my knowledge, I wouldn't expect to learn anything from a visualization unless I had already studied the algorithm quite closely and I had a specific question I wanted to answer. Even then, it's a shot in the dark; most algorithms don't lend themselves to being visualized. The animations are very pretty, though -- who knows, maybe they will help someone.

polskibus2• 12 years ago

Fantastic article! I am a big fan of your work. Some questions:

- any plans on trying to make a canvas based d3 adapter/library? Also thinking about webgl here, although I believe x3dom works well enough

- have you played with other programming languages to evaluate their support for data vis expressiveness? If so, what would you recommend to try out?

mbostock11• 12 years ago

Re. Canvas, yes and no. On the one hand, D3 (data-driven documents) is intrinsically tied to the DOM and I don’t want to compete with standard representations like HTML, SVG and CSS. On the other hand, D3 supports Canvas for geographic projections and we could expand that to include other geometries like d3.svg.{line,area,symbol} and d3.geom.voronoi. But it’s only worth dropping into Canvas if there’s a significant performance bottleneck, and often there isn’t. Jason and I are working on the geometry pipeline so we’ll see. X3DOM also fits well with D3, though I tend to focus on 2D visualization.

tubelite• 12 years ago

Slight tangent: in those cases where canvas is desired only for the ability to convert a visualization into a PNG (rather than performance), it is possible to serialize a D3-created SVG into an XML string and render it to an image/canvas. The process is straightforward for Chrome and Firefox, but needs the canvg library for Safari.

phloxicon2• 12 years ago

Beautiful article. Is there a repository with the source code available? You mention viewing the source in the article but my mobile browser can't do that.

phloxicon2• 12 years ago

Found them: http://bl.ocks.org/mbostock

julie1• 12 years ago

you said ask me anything :)

What about vizualizing randomness ?

Like in this article ? http://lcamtuf.coredump.cx/oldtcp/tcpseq/print.html

tezza• 12 years ago

In case you're revisiting this post later ( 17 hours elapsed when I got to your article )

1. Recording the missteps to Perfection

In future could you record the number of edits required to come up with your finished essays ? I've always found that it takes a lot of steps to make something that elegantly looks as though no mis-steps were taken. Some form of screen recording style evolution of the essay over time

I know Paul Graham had a live essay session recording.

2. Archiving live and interactive works.

I guess your piece will archive okay as it is the sum of static files. But I do hope that your essay plays well with archive.org so that future people can enjoy your article.

3. The future of the interactive essay

Relating to 1. I can't imagine that preparing an interactive essay is an easy affair. A lot of effort goes into a static essay. How much work is it to interactivate it? Do you feel it will become more widespread as an essay form or restricted to a select bunch of interactivists ?

E books - smartphones really make interactive essays possible to disseminate.

mbostock11• 12 years ago

1. Ah, but how to define an “edit”? The git repo for the talk had 69 commits, but they varied greatly in size. There’s also the history of the individual examples (which could be crawled from GitHub Gist), the history of the write-up (which I squashed on merge, sorry!), as well as various notes scattered while I was still figuring out the topic.

2. I hope it archives well — there are no dependencies on other sites, though it loads resources via JavaScript. The site is backed by a repo on GitHub. (Though I should point out that I retain copyright on my personal website, despite the source being viewable.)

https://github.com/mbostock/bost.ocks.org/tree/gh-pages/mike...

We have a similar concern with published graphics on The New York Times. It’s funny and sad now how so many animations on University course websites are practically unviewable because of waning support for Java; I expect it will be similarly awkward to run Flash plugins in ten years. On the other hand, content written to web standards seems to have a longer shelf-life, as the standards are widely supported by many organizations, not just one. So my hope is that standards-based graphics will both archive well and continue to run on evolving browsers.

3. Yes, it’s already the case that graphics (and further interactive graphics) are increasingly integrated with prose, rather than being relegated exclusively to standalone content. That’s not to say standalone graphics are bad — there are many viable forms for graphics, and sometimes you want it to be standalone — but that we’re figuring out ways to integrate “multimedia” more elegantly and less gimmick-ly.

I still think the hard part is expressing the ideas & communicating effectively rather than the technology. Designing interaction is hard because there are so many ways to do it, and you don’t always know what will be intuitive to readers.

spenuke• 12 years ago

Can someone clue me in on the usage of bitwise operators when declaring the cardinal direction variables (NSWE)? I can't make sense of it -- those values don't seem to make use of any bitwise operations further down the line, unless I'm missing something, which is very possible.

Is this just a stylistic choice to signal the uses for those variables? (Though I confess I still don't know what that signal would be, anyway.)

Any illumination would be appreciated, but should MBostock still be following this, thanks so much for your work! So inspiring.

mbostock11• 12 years ago

Sure, it’s a bit field, which is an efficient way to store multiple booleans (bits) in a single number.

https://en.wikipedia.org/wiki/Bit_field

The maze is defined as a rectangular grid of cells, where each cell is bit field specifying whether you can navigate from that cell to each of its four neighbors: the cell above (N), the cell below (S), the cell to the right (E), and the cell to the left (W). The bit masks are powers of two (N = 1 << 0 = 1, S = 1 << 1 = 2, W = 1 << 2 = 4, E = 1 << 3 = 8) to uniquely assign each bit to each of the four directions.

For example, say that you have a cell that’s open to the north and the south, as part of a vertical passage. The bit field therefore is 0011. To check whether you can go south from the cell, you use the bitwise AND (&) operator: 0011 & S = 0011 & 0010 = 0010 = truthy. To likewise check whether you can go east from the cell: 0011 & E = 0011 & 1000 = 0000 = falsey.

hexleo• 12 years ago

Thank you for your work. Very impressive work. Examples of these algorithms cat let my students can easily lean.

resu• 12 years ago

Breathtaking work!

Found a ton more interesting examples here: http://bl.ocks.org/mbostock

talles• 12 years ago

This one is so beautiful: http://bl.ocks.org/mbostock/d8e15a0ab7f85818a5bd

parham• 12 years ago

Power of visuals, so pretty.

gadgetdevil• 12 years ago

The web is truly the new <canvas> for the artist.

hamxiaoz• 12 years ago

I'm thinking the same thing.

VMG• 12 years ago

This one is also interesting (requires WebGL) http://ottoallmendinger.github.io/js-quickhull3d/

joaomoreno• 12 years ago

Great job, this both reads and looks great!

prestonbriggs• 12 years ago

Here're are a couple of papers you'll probably enjoy:

Design and implementation of the UW Illustrated compiler by Andrews, Henry, and Yamamoto PLDI '88

and

The University of Washington illustrating compiler by Henry, Whaley, and Forstall PLDI '90

DalekBaldwin• 12 years ago

I can't find any copies of these papers that aren't behind a paywall. Is there any record of what the visualizations looked like?

reader50002• 12 years ago

Really is interesting how proper visualization allows you to see very subtle probabilistic distinctions that probably only a phd in stochastic processes would understand intuitively.

lpwaterhouse• 12 years ago

Hug of death?

jqm• 12 years ago

This was really great.

Especially maze turning into spanning tree. That one was truly mind blowing.

jmt7les• 12 years ago

I could watch that for hours straight.

mu_killnine• 12 years ago

This is incredible. As a non-CS major, it's been truly a fascinating read!

prezjordan• 12 years ago

Off-topic: Why isn't my macbook a jet engine right now? I've read plenty of blogs with nothing but a parallax scroll at the top and my computer fan goes insane.

But, on this blog, TONS of dynamic code running and not a peep.

tsenkov• 12 years ago

Precisely what I was thinking by the end of the post.

_pmf_• 12 years ago

Why isn't my macbook a jet engine right now? I've read plenty of blogs with nothing but a parallax scroll at the top and my computer fan goes insane

Ah, the beauty of Javascript!

zedadex• 12 years ago

Fits right in with my rapid-temperature-rise-based workflow!

domdip• 12 years ago

Funny thing about that random comparator shuffle - Microsoft used it for their browser selection screen (part of the EU antitrust settlement). Oops!

http://www.robweir.com/blog/2010/02/microsoft-random-browser...

Artemis2• 12 years ago

Great piece of work!

I've seen in the piece of code corresponding to the Fisher-Yates algorithm this snippet: "n-- | 0". Has the "| 0" any importance?

abbeyj• 12 years ago

x | 0 will truncate a floating point x to an integer. The multiplication happens first so the overall expression acts like i = (Math.random() * n--) | 0.

TD-Linux• 12 years ago

This is actually the only way to do integer arithmetic in Javascript (without the array types introduced by WebGL). It's how asm.js signals integer math as well: https://en.wikipedia.org/wiki/Asm.js#Examples

appreneur• 12 years ago

Beautiful...just to understand that algorithms also paint beautifully ...visualising algorithms awesome!

idibidiart• 12 years ago

I wonder about visualizing the algorithms that visualize the algorithms. Being serious and curious here.

yazinsai2• 12 years ago

Tread carefully, for you risk breaking the universe.

milroc• 12 years ago

http://bost.ocks.org/mike/join/

mellisarob• 12 years ago

please recommend a good book that would assist me with the basics.

yazinsai2• 12 years ago

+1 if you didn't understand a thing but kept scrolling for the sweet, sweet animations

johnsteve• 12 years ago

well this excites me now. can anyone help me master the basics or suggest any good book?

ilovecookies• 12 years ago

How many times has this been on HN..

https://news.ycombinator.com/item?id=7822983 https://news.ycombinator.com/item?id=7652333

I know it's more times but I haven't found those threads..

sys32768• 12 years ago

How did you people learn these things without visualizations?

goblin89• 12 years ago

Anyone interested will probably also enjoy Mike's talk “Design is a search problem” from Openvis conference: http://www.youtube.com/watch?v=fThhbt23SGM

Visualizing Algorithms

Related Stories