You Infinite Snake

Like a spider's web

2011-12-06T16:39:00.001-08:00

“It is anticipated that the whole of the populous parts of the United States will, within two or three years, be covered with net-work like a spider's web.”

— Illustration and quote from The London Anecdotes, 1848
Quoted in The Victorian Internet

Google+ vs. Facebook engagement

2011-12-04T22:22:00.000-08:00

Here's a little statistically-insignificant self-experimentation, based on 51 near-simultaneous posts to both Google+ and Facebook, from the beginning of September 2011 to the present.

"Engagement" is the number of unique people (excluding me) who responded, either by commenting, liking or +1'ing the post, or liking or +1'ing a comment on the post. (The scatterplot points are perturbed slightly from their true integral values so they don't completely overlap.) What's remarkable here is how coincidentally similar the engagement is on the two networks — the difference is under 2 percent (!) despite the fact that my social network on Facebook is currently 2.25 times as large as on Google+.

Google+ has very slightly higher engagement on STEM-related posts (science, technology, engineering, and mathematics), while Facebook is slightly higher for other posts, but the differences are well within 95% confidence intervals.

It's possible my social network has somewhat shifted to Google+. Here is the post set split into five chronological partitions with 10 or 11 posts in each.

Engagement as defined above excludes re-sharing posts, because I wasn't confident the two social networks are reporting these in the same way (e.g., do they both report recursive shares?). But there is some interestingly significant difference in sharing behavior on Google+ with STEM posts seeing nearly seven times as much sharing as non-STEM posts in this very small data set, an effect which didn't appear on Facebook.

Of course, all of this is specific to my social network, and really, the sample size is too small to draw any conclusions at all. Now, if someone were to compare posts for a large number of people that cross-post publicly to Facebook and Google+, that could start to get interesting...

Matrix multiplication algorithms over time

2011-12-02T15:37:00.001-08:00

The asymptotically fastest algorithm for matrix multiplication takes time O(n^ω) for some value of ω. Here are the best known upper bounds on ω over time.

The latest improvements, the first in over 20 years, are due to Andrew Stothers and Virginia Vassilevska Williams. The latter gave an O(n^2.3727)-time algorithm for multiplying matrices.

When will the sometimes-conjectured ω = 2 be reached? Certainly nothing wrong with taking a linear fit of this data, right?

So that would be around the year 2043. Unfortunately, the pessimist's exponential fit asymptotes to ω = 2.30041...

Live-Blogging HotNets 2011 (Day Two)

2011-11-16T00:21:00.001-08:00

(OK, not quite live...)

Day One was over here.

Session 5

Christopher Riederer spoke about auctioning your personal information. Unfortunately I missed the talk, but it must have been a good one since there was quite a bit of discussion.

Next up was Vincent Liu speaking about Tor Instead of IP — which is just what it sounds like, Tor as an Internet architecture. Of course you can't just use Tor and they have proposals for controlling incoming traffic, DoS, and getting better efficiency (lower stretch) with enough diversity of jurisdiction and plausible routing-policy-compliance. Similar to what Telex does with network-layer steganography, the general approach here is to make Internet connectivity an all or nothing proposition: If you can get anywhere outside a censored region, you can get everywhere so all the censor can do is block the entire Internet.

Last was Gurney et al's Having your Cake and Eating it too: Routing Security with Privacy Protections. The notion of security here is that the neighbors of an AS can verify that the AS in question selected and advertised routes according to its agreed-upon policy. The privacy is that they can verify this without revealing any more information than the verification itself. The paper presents protocols to verify several particular policies (e.g., if the AS was offered some route, then it advertised one). Could be useful for debugging interdomain connectivity issues.

Session 6

Steven Hong presented Picasso which provides a nice abstraction, hiding the complexity of full duplex signal shaping to utilize discontiguous spectrum fragments.

Mohammad Khojastepour spoke about using antenna cancellation to improve full duplex wireless.

Souvik Sen asked, Can physical layer frequency response information improve WiFi localization? Yes. And it involves driving Roombas around cafeterias.

Session 7

Poor old TCP felt snubbed at this workshop until Keith Winstein started roasting it. TCP is designed to work well in steady-state with very particular assumptions. It fails under messy real world conditions — hugely varying RTTs, stochastic rather than congestion-induced loss, very dynamic environments, and so on. Keith's goal is to make transmission control more robust and efficient by modeling network uncertainty. So the end-host has a model of the network (potentially including topology, senders, queues, etc.) but any of these elements can have unknown parameters describing their behavior. Then it maintains a probability distribution over possible parameter values and updates its beliefs as evidence comes in from the network (e.g., ACKs). At any given time, it takes whatever action maximizes expected utility (= some throughput / fairness / latency metric) given the current distribution of possible situations. The action is a delay until sending next packet. It's a beautifully intuitive idea, or as a certain reviewer put it,

"This is the craziest idea I've heard in a very long time."

Keith showed a simulation in one small example where this approach decides to use a slow start behavior — without that being hard-coded in — but then after getting a little info, immediately sends at the "right" rate. But there are big challenges. Some discussion touched on state explosion in the model, the danger of overfitting with an overly-complicated model, and how much the sender needs to know about the network.

Q: What would be the first variable you'd add to the network model beyond what TCP captures? A: Stochastic loss.

Q (Barath): Should we add a control plane to disseminate information about the network to assist the model? A: anything that gets more info is good.

Q (Ion): When won't this work? A: Model mismatch — if the truth is something the model didn't consider.

Q: Do the smart senders coexist? If you have 2 versions of the algorithm, do they coexist? A: Good question.

Next, a movie. The BitMate paper — "Bittorrent for the Less Priviliged" — by Umair Waheed and Umar Saif was one of the few entirely-non-US papers. Unfortunately visa issues prevented their attendance but Umar presented via a movie. The problem is that high bandwidth BitTorrent nodes for mutually helpful clusters but no one wants to upload to low bandwidth nodes. The solution included several interesting mechanisms but Umar said the one that got 80% of the benefit was something they call "Realistic Optimistic Unchoke" which improved unchoking of low-bandwidth peers. BitMate gets dramatic improvements in efficiency and fairness.

Umar took questions via Skype. It was so 21st century.

BitMate was written up in the NYTimes.

Q: what's your experience with real deployment? A: 40,000 users from 170 countries — a lot from US "for reasons that escape me" (~40% from North America). Many users from Iran, probably to circumvent censorship.

Vyas Sekar told us that a particular real 80,000 user network with tens of sites had 900 routers and 636 middleboxes (Firewalls, NIDS, Media gateways, load balanceers, proxies, VPN gateways, WAN optimizers, Voice gateways). Problem with middleboxes: device sprawl. Another problem: dealing with many vendors (Bruce Davie, Cisco: that problem we can fix!). Result: high CapEx and high OpEx. (Just network security cost $6B in 2010, $10B in 2016.) Also, middleboxes today are inflexible and difficult to extend.

So most net innovation happens via middleboxes, but it doesn't come easily. And middleboxes have been missing from the research community's discussion of innovation in networks. The Vision: Enable innovation in middlebox deployments. Approach: (1) software-centric implementations, (2) consolidated physical platform, (3) logically centralized open management APIs. There are also opportunities for reduced costs (via multiplexing) and improved efficiency (via reuse of functions like session reconstruction of TCP flows).

Session 8

This was the data center session with three more cool papers, but unfortunately I had to leave early.

See the full program.

Overall I was impressed with the ideas and engaging presentations. Thanks to the chairs Aditya and Ion for a very well-run workshop.

Live-blogging HotNets 2011

2011-11-14T13:41:00.000-08:00

Lots of exciting talks and discussion at HotNets. Here are a few highlights.

Session 1

The first session was on Internet architecture. Ali Ghodsi spoke about three unanswered questions for the burgeoning area of {data/information/content}-{centric/oriented} networking. These were privacy, data-plane efficiency, and whether ubiquitous caching (a key feature of nearly all the proposals) actually provides quantitative improvement. For the latter point, the argument is that work on web caching from the late 1990's indicated that if you have caching near the edge (as already exists in present-day web caches), then adding ubiquitous caching to the architecture does not provide much more benefit due to heavy-tailed access distributions. So, does the caching advantage of information-centric networking warrant such a large-scale architectural change?

In later one-on-one discussions, Dan Massey (who later gave an interesting talk on the IPv4 grey market) argued that at least for the NDN project, ubiquitous caching is not the focus. Something more important is being able to do policy-aware multipath load balancing — in a very dynamic way in the network, by shipping content requests optimistically to multiple locations and seeing what ends up working well. A kind of speculative execution for forwarding. This may not be specific to content-awareness, but Dan argued that if you want to make this work, you end up needing something like NDN's Pending Interest Table mechanism. (The discussion was brief, but hopefully I restated the argument accurately.)

Dave Andersen and Scott Shenker argued that the primary goal of a future Internet architecture should be to accommodate evolution within the architecture itself, rather than just adding new functionality. The XIA approach introduces the notion of data-plane fallbacks so the sender can ask for new functionality and if it isn't supported everywhere, things still work. Scott focused on bringing evolvability to the architecture by applying the principles of extensibility and modularity.

There were several questions about what would be the incentives to deploy either approach. Scott responded that while incentives are important, first we need to understand what technical mechanisms we need to make evolvability feasible — which previously we have not understood. Ion Stoica asked, What would be the first thing that would drive deployment of one of the future Internet architectures? Some of the answers included SCADA networks which need extreme security, content caching (despite the first talk!) where content providers have monetary incentives, and (from Hari) the ability to deploy differential pricing by having more information about applications' intent (though users may not like this!).

Another question was whether these architectures would actually have fixed the processes which led to ossification in practice (e.g., via middlebox problems); and whether they'd aid deployment of protocols like secure BGP which have had problems in practice.

Session 2

Haitao Zheng from UCSB spoke about building wireless data centers, where directional wireless interfaces on racks of servers can be dynamically steered to connect pairs of racks that need to communicate. If you want to connect racks of servers with high-bandwidth wireless links, interference is a big problem. Their approach is 3D beamforming: Rather than aiming the radio directly (in the 2D plane at the top of racks), bounce it off a reflective ceiling and put an absorber around the target. This direction of reception reduces interference. In addition to having many pretty pictures of interference patterns, this is part of a line of work (in wireless and optical) that has a very cool approach — we always think of changing the traffic flow to match the topology; now we can change the physical topology to match the traffic.

Abhinav Pathak talked about finding energy bugs in mobile devices — as he said, that hits three hot keywords.

Jonathan Perry spoke about Rateless Spinal Codes. My main question: why do coding schemes get to have such cool names?

Session 3

Mark Reitblatt spoke on "Consistent Updates for Software-Defined Networks: Change You Can Believe In!". Here is the problem they are solving: As you are reconfiguring your network how can you be sure your policy (like availability or security) is preserved even during the transition? Traditionally, this is hard because of the inconsistency of having one set of forwarding rules deployed some places, and another set deployed other places. Actually, it might seem impossible. Even if you magically deploy a change everywhere instantly, you can still get policy violations because packets travel across non-negligible time. Can you solve it? Yes you can!

Junda Liu should get some sort of award for giving the most entertaining talk that also featured a state machine diagram.

Barath Raghavan calculated the energy and emergy of the Internet, which has been getting some press recently and which generated a lot of discussion on the complexities and implications of measuring society's energy use.

Awesome feature of this session: all the talks finished early!

Session 4

Jon Howell spoke on a proposed refactoring (and narrowing) of the API for web applications executing on user machines.

Ethan Katz-Bassett spoke about Machiavellian Routing. The coolness here is a trick by which ISPs can control inbound routing, so if they notice there is a connectivity problem at some AS they can induce other senders to avoid the problem.

Dan Massey noted that a grey market is emerging for IPv4 addresses and argued that we need a way not to prevent the market from existing outside the traditional Internet governance, but instead to verify what transactions happen. This would make the market more honest and efficient. Most interesting point from discussion (I think from Jon Howell): Why do we want to improve the IPv4 market? This will allow more efficient use of available IPv4 addresses ... but if we let the market be as baroque and inconvenient as possible, it will encourage deployment of IPv6 sooner!

Onward to Day Two...

The other Barack

2011-10-20T17:09:00.000-07:00

According to this data, exactly two people named Barack have donated to the Obama campaign. So, who's the other one?

What's wrong with computer science reviewing?

2011-08-03T01:12:00.000-07:00

There is a sense among some researchers in computer science that many peer reviews in our field are bad — in particular, too often unfairly slanted against papers in various ways that do not encourage good science and engineering. Why might this be happening and what can we do about it?

[Aside: you can now follow me on Google+ or via an RSS feed. Short posts there, long posts here.]

The problem

First of all, let me be clear: (1) I think most reviews, regardless of whether they recommend acceptance or rejection, are well done and reflect care and significant time that the reviewers have invested. (2) Exciting, impactful research still manages to get done, so the system does generally work pretty well. Still, that doesn't mean we can't improve it. (3) Despite the fact that I try to take care with each review, statistically speaking I have probably committed each of the problems discussed here.

With the fine print out of the way ... what is this possible problem? The evidence is almost all ancedotal and biased. But since that is all we have, let me supply some anecdotes, first that reviews are often negative:

This July's edition of Computer Communication Review rejected all its peer-reviewed submissions, thus matching (at least for one issue) the Journal of Universal Rejection as the most prestigious journal as judged by acceptance rate.
Jeffrey Naughton critiqued the state of research in the databases community with bad reviewing ("Reviewers hate EVERYTHING!") as a key problem, giving the anecdote that in SIGMOD 2010, out of 350 submissions, only paper 1 had all reviews rate it "accept" or higher; and only 4 had an average rating of "accept" or higher.
Taking a recent major systems-and-networking-related conference as a representative presumably-normal example, papers received generally 4 or 5 reviews and were scored on a scale of 1 to 5. Out of about 177 submissions, only six accepted papers received any 5's. Only one received more than a single 5, which also says something about variance.
"...there is a pervasive sense of unease within these communities about the quality and fairness of the review process and whether our publication processes truly serve the purposes for which they are intended. ... It was clear from the reaction to the panel that concerns with the reviewing process cut across many, if not all, fields of computer science." (Panel summary from a session at the 2008 CRA Conference at Snowbird)

Is it just a reweighting problem? If reviews were just conservative numerically, any problem could be fixed by "curving" the scores up. That would be nice, but ... another anecdote:

A survey asked authors of SIGCOMM 2009 submissions whether they agreed that "The reviews were technically correct". Roughly one-third of respondents disagreed or strongly disagreed, about a third agreed or strongly agreed, and another third had no opinion.

Even taking into account the fact that the survey included authors whose submissions were rejected and might just be grumpy, those numbers seem undesirable. Reviews are sometimes wrong or emphasize unimportant or subjective problems, even when the paper gets accepted. (And that's not necessarily the reviewer's fault.)

But this is true in every field, right? After all, authors have been complaining about criticisms for centuries. Here, by the way, are a couple favorite criticisms:

"Your manuscript is both good and original. But the part that is good is not original, and the part that is original is not good." (unattributed)

"In one place in Deerslayer, and in the restricted space of two-thirds of a page, Cooper has scored 114 offenses against literary art out of a possible 115. It breaks the record." (Mark Twain, How to Tell a Story and Other Essays.)

Getting back to the point, there is plenty of precedent for reviewers not seeing the light. But there is anecdotal evidence that this is a bigger problem in CS than in certain other areas:

A study of NSF panel reviews found that reviewers in computer science give lower scores on average than in other areas. (Note: I read this in CACM or some other magazine but now I can't find it; if you can, please let me know.) Update: Here's the data: CISE proposals average 0.41 points lower than other directorates.
While it appears to be a common (but not universal) belief in CS that reviewers are too-often wrong and frustrating, I'm told by at least one physicist that that is not the general feeling about reviewers in that field. They are "rarely out to actively find problems with your paper", and while they may often misunderstand parts of the paper, the authors can respond and usually the reviewers or the journal editor will accept the response. Publication is still competitive and often annoying for other reasons, but reviewers are generally reasonable.

So what? Does this have any negative impact? As pointed out by others:

Researchers may be discouraged. (I know of at least one top PhD graduate who went to industry citing weariness with "selling" papers as one cause.)
It puts CS at a disadvantage with other fields, if we are generally more negative in grant proposal reviews. As Naughton wrote, "funding agencies believe us when we say we suck".
More speculative or unusual work (with dozens of potential challenges for the approach that a reviewer could cite) is at a disadvantage compared to work with well-known quantitative metrics for evaluation.
Variance in reviews may make papers more likely to return for another round of reviewing at another conference, increasing time to publication and reviewer workload.

Causes of the problem

Naughton suggested that "Reviewers are trained by receiving bad reviews from other reviewers who have received bad reviews in the past". Keshav suggested human failings and increasing reviewer workloads. Without disagreeing with those possibilities, I'm wondering what about CS in particular might exacerbate the problem? Here are two ideas.

No author response to reviewers. As a consequence of CS's focus on conferences, most venues (in my area) have no opportunity for authors to answer reviewer criticism. The communication is author ---> reviewer ---> author, with no feedback to reviewer. It's a little like putting papers on trial without a defense team. As a result:
- Bad reviews are more likely to happen, because the reviewer typically never learns if they have submitted a bad review, and is not really held accountable.
- Once a bad review does happen, there's no chance to fix it.
Focus on bugs. (This is extremely speculative.) As computer scientists, we are really great at spotting bugs, and that's a good thing when you're writing code. Possibly, some of that carries over into reviewing more than it should. Maybe bug-finding is easier than thinking carefully about contributions of the paper — especially if, once you honestly think there's a bug, you don't have to do any more work even if you're wrong. (Just noticed that someone else had the same idea.)

Fixing the problem

I'm suggesting these as possible directions to discuss, not as solutions I think are guaranteed to work.

Allow authors to respond to reviewers. Just as in TCP's three-way handshake, one would hope that both involved parties get feedback. Responses, at least in theory, (1) create incentive for better reviews and feedback to help improve, (2) allow authors to point out simple misunderstandings in reviews. (Note that some venues, like ASPLOS, have rebuttals. And in fact, CCR has reasonably fast turnaround and allows responses to reviewer comments as they arrive. Apparently that didn't help the July issue, though...)

One could argue that reviewers already have an incentive to do well, because they have their reviews looked at (or even voted upon!) by other program committee members. But other reviewers don't know the paper and its area as well as the authors; and reviewers have at least as much incentive to maintain a friendly relationship with other reviewers as they do to argue the case for a specific paper. Arguing a case after one reviewer has taken a negative stand involves extra effort and to a certain extent puts one's reputation on the line. I suspect the most effective response comes from the authors. They have the needed incentive and knowledge.

That seems like the most obvious approach, but it does require organizational change. There are some smaller steps that might be easier on an individual level.

Avoid Naughton's checklist for bad reviewing. Quoting him directly:
- Is it "difficult"?
- Is it "complete"?
- Can I find any flaw?
- Can I kill it quickly?
Focus on what a paper contributes, not on what it doesn't contribute, which is always an infinitely long list. Focusing on the absent results will inevitably lead any paper to the wastebin of rejection and any author to a pit of misery.

In particular, it seems to me that "This paper didn't show X" is, by itself, not a valid criticism. It is an irrelevant factoid unless it negates or diminishes some other contribution in the paper. If it is fair to argue that particular results are absent, then my first beef with every paper is going to be that it fails to resolve whether P ≠ NP.

Of course, a paper should get more "contribution points" for a better and more thorough evaluation, but perhaps it's OK to leave some questions unanswered. Particularly since it's often hard to predict which particular dimension or potential inefficiency the reviewers will be interested in. Leaving certain questions unanswered is entirely compatible with the paper making other useful contributions.
Submit to arXiv, bypassing the reviewing process entirely and letting other researchers judge what they want to read. Subscribe to arXiv RSS feeds so you find out about other people's work more quickly. Of course, arXiv currently has limited value for CS systems and networking researchers, since other such researchers tend not to look for papers there. More on that later.
Adopt policies that tolerate some reviewer pessimism. As an example of what seems to me like a bad idea, a recent workshop had a reviewing policy that allowed a single reviewer to effectively veto a paper if they strongly disliked it.
Implement feedback yourself. If a conference doesn't provide a means for author feedback to reviewers, the reviewer could implement this herself by including in the review a way to provide feedback, e.g., a link to a Google Docs form that could preserve the anonymity of the reviewer and authors. Disadvantage: This only fixes a piece of the problem and might seem strange to PC chairs and authors.

Other past suggestions include reducing PC workloads, making reviews public, maintaining memory across conferences (so resubmissions are associated with old reviews), and much more; see links above and below.

The open question is, which of these will best improve the quality of reviews and, ultimately, CS research? My guess is that any good solution will include some form of author response to reviewers, but there are several ways to do that.

There's voluminous past discussion on this topic. Related links:

Workshop on Organizing Workshops, Conferences, and Symposia for Computer Systems, in particular, see papers/talks in the 11:00 a.m. session. One became an article in CACM.
Open Issues in Organizing Computer Systems Conferences (Jeffrey Mogul and Tom Anderson, CCR July 2008)
Paper and proposal reviews: is the process flawed? (summary of a panel session at the 2008 CRA Conference at Snowbird)
Peer reviews: make them public (Nature correspondence)
Peer reviews: some are already public (Nature correspondence)
How Should Peer Review Evolve? (Ed Chi, blog@cacm)
Conferences vs. Journals in Computing Research (Moshe Vardi, CACM 2009)

Update: SIGCOMM 2012 will have rebuttals. Also, Bertrand Meyer has something to say about CS reviewing.

Vote Tuesday!

2011-04-13T19:59:00.000-07:00

6-year-old Tuesday Muse raised money for Japan with her artwork, and now she's totally excited to be in the Name of the Year competition. But she's in a tough match against Joe Shortsleeve. Why not help her out? Vote Tuesday Muse for Name of the Year!

NOTY has a strong ballot of 64 names this year — including Yolanda Supersad, Dr. Loveday Conquest, Courvoisier Winetavius Richardson, and Mercedes Bunz, who, some readers of this blog may be interested to note, has penned a history of the Internet.

As long as I'm linking...

Donate to Japan disaster relief
	MathJax: Beautiful math in all browsers
A visualization of the speed of light
	Post-it note monsters
Our CS building at Illinois
	Scott Aaronson's ad for theoretical computer science
How real people react to that Stringy Haired Ghost Girl from The Ring or maybe The Grudge (via Philip Levis)
	"It is immediate from the definition that a given classical watch may have several extensions into a mustard watch, whereas given a mustard watch W' there is only one underlying classical watch W from which W' is derived." (via Jeff Erickson)

Attractive scientific plots with gnuplot

2011-02-12T23:52:00.000-08:00

I use gnuplot for nearly all my graph-drawing for academic publications. On the whole, it's clean and relatively flexible, and that combined with inertia has been enough to keep me from trying interesting alternatives like matplotlib, Plot, ploticus, and R. However, gnuplot's default output is not especially pretty. I often see graphs in papers that look like this...

...or worse, if it's been bitmapped rather than using EPS or PDF. With some tweaking, however, one can produce much more attractive output. I would much rather look at plots like this:

In fact it looks better. Blogger doesn't seem to support any vector image format, but here are the pdf version and the svg version. To produce the PDF version, you need gnuplot 4.4's pdfcairo terminal. Below, you can see the gnuplot files for the above two plots.

set terminal postscript eps color

set output "boring_default.eps"
set xlabel "x axis label"
set ylabel "y axis label"

set key bottom right

set xrange [0:1]
set yrange [0:1]

plot "template.dat" \
   index 0 title "Example line" w lp, \
"" index 1 title "Another example" w lp

# Note you need gnuplot 4.4 for the pdfcairo terminal.

set terminal pdfcairo font "Gill Sans,9" linewidth 4 rounded

# Line style for axes
set style line 80 lt rgb "#808080"

# Line style for grid
set style line 81 lt 0  # dashed
set style line 81 lt rgb "#808080"  # grey

set grid back linestyle 81
set border 3 back linestyle 80 # Remove border on top and right.  These
             # borders are useless and make it harder
             # to see plotted lines near the border.
    # Also, put it in grey; no need for so much emphasis on a border.
set xtics nomirror
set ytics nomirror

#set log x
#set mxtics 10    # Makes logscale look good.

# Line styles: try to pick pleasing colors, rather
# than strictly primary colors or hard-to-see colors
# like gnuplot's default yellow.  Make the lines thick
# so they're easy to see in small plots in papers.
set style line 1 lt rgb "#A00000" lw 2 pt 1
set style line 2 lt rgb "#00A000" lw 2 pt 6
set style line 3 lt rgb "#5060D0" lw 2 pt 2
set style line 4 lt rgb "#F25900" lw 2 pt 9

set output "template.pdf"
set xlabel "x axis label"
set ylabel "y axis label"

set key bottom right

set xrange [0:1]
set yrange [0:1]

plot "template.dat" \
   index 0 title "Example line" w lp ls 1, \
"" index 1 title "Another example" w lp ls 2

set terminal svg size 320,240 fname "Gill Sans" fsize 9 rounded dashed

# Line style for axes
set style line 80 lt 0
set style line 80 lt rgb "#808080"

# Line style for grid
set style line 81 lt 3  # dashed
set style line 81 lt rgb "#808080" lw 0.5  # grey

set grid back linestyle 81
set border 3 back linestyle 80 # Remove border on top and right.  These
             # borders are useless and make it harder
             # to see plotted lines near the border.
    # Also, put it in grey; no need for so much emphasis on a border.
set xtics nomirror
set ytics nomirror

#set log x
#set mxtics 10    # Makes logscale look good.

# Line styles: try to pick pleasing colors, rather
# than strictly primary colors or hard-to-see colors
# like gnuplot's default yellow.  Make the lines thick
# so they're easy to see in small plots in papers.
set style line 1 lt 1
set style line 2 lt 1
set style line 3 lt 1
set style line 4 lt 1
set style line 1 lt rgb "#A00000" lw 2 pt 7
set style line 2 lt rgb "#00A000" lw 2 pt 9
set style line 3 lt rgb "#5060D0" lw 2 pt 5
set style line 4 lt rgb "#F25900" lw 2 pt 13

set output "template.svg"
set xlabel "x axis label"
set ylabel "y axis label"

set key bottom right

set xrange [0:1]
set yrange [0:1]

plot "template.dat" \
   index 0 title "Example line" w lp ls 1, \
"" index 1 title "Another example" w lp ls 2

Now here's something for which I would pay (some) real money: a gnuplot terminal which outputs directly to Keynote. Then, for example, during a presentation, one could have lines in the plot appear one at a time, explaining each without the distraction of showing irrelevant objects. This should actually be quite doable since Keynote's format is just a zipped XML.

Update 2011.04.09: Mac users of macports may note that the default install of gnuplot for some reason excludes pdfcairo. Abhinav Bhatele writes with instructions for enabling pdfcairo in macports:

$ sudo port edit gnuplot

Add these lines somewhere in the file (I added them before the lua variant):

variant pangocairo description "Enable pdfcairo" {
     depends_lib-append      port:pango
     configure.args-delete   --without-cairo
     configure.args-append   --with-cairo
}

$ sudo port info gnuplot

Just to check that pangocairo variant exists. And then:

$ sudo port uninstall gnuplot
$ sudo port install gnuplot +pangocairo

You'll need to keep in mind that if you do port selfupdate,
the edited version of the portfile might get overwritten.

Update to the update 2011.12.04: Looks like macports now includes the pangocairo variant, but still does not install it by default; so it should work if you run just the last two lines.

Update 2011.04.09: Added SVG version and made it slightly more beautiful.

A peer-reviewing horror story

2010-12-28T13:19:00.000-08:00

A peer-reviewing horror story. Don't let this happen to you.

Also available in various ebook formats.

Google Frequency Plotter

2010-10-23T22:05:00.000-07:00

Here's an app version of this xkcd comic that lets you plot the frequency of phrases according to Google searches.

Plot
for _ in	0-30 Enter a range like 1-10 or a list like monday,tuesday,wednesday

Permalink to this chart

Some examples below the fold.

Sanity checks

How convenient.

Politics

[Thanks: Bryan]

Most frequent birth year: 1982

What you've got

Mind your phone

Procreation

Post permalinks to your favorites in the comments below.

Disclaimers: The number of search results reported by Google's search API is known to be occasionally bogus and is not a reliable indicator of anything in particular. Also, there's some bug here if you do a range query with only a single value. Finally, an exclamation point in the status message indicates an error in one query or the lack of any results.

Ig Nobel candidate

2010-10-19T18:11:00.000-07:00

"University of Ljubljana researcher Borut Povse is conducting experiments in which a robot limb repeatedly hits human volunteers on the arm to evaluate human-robot pain thresholds in order to facilitate adherence to Isaac Asimov's first law of robotics, which prohibits robots from injuring people." [ACM TechNews]

Public reviewing

2010-10-02T23:27:00.000-07:00

The New York Times has a piece on public review, even to the point of crowdsourcing, as a partial alternative to peer review for scholarly publications. The interesting bit is that at least one journal, Shakespeare Quarterly, has tested this open review process. You can view the submitted papers and discussion (including a paper providing an information-theoretic analysis of Shakespeare). The interface seems well designed and allows commenting on individual paragraphs.

There are doubtless situations where this opens the reviewing process to trolls, flamewars, or inerudite remarks. On the other hand, assuming the comments are used to help inform a final judgement by experts, there could be advantages. Reviewing a paper is sometimes like an NP search problem, to find the contributions and weaknesses. Public review could be seen as using crowdsourcing to tackle the search problem. Certain comments would be easily verifiable by an expert, even without relying on the trustworthiness of the anonymous commenter, yet would not necessarily have been noticed by any particular expert. (The same easy-verification property is one reason Wikipedia is useful even when you're looking for a reliable answer to a question.)

In computer networking research, the closest we come to a collaborative, real-time form of reviewing is Computer Communication Review which has just recently started returning reviews to authors as they are submitted, and allowing authors to comment on the reviews.

Unrelated fun ... here's Seaquence, a clever visualization of musical composition.

Programming Language Wars: The Movie

2010-09-14T21:56:00.000-07:00

In computer science and hacker circles, the programming language wars have, it seems, been raging since the beginning of time. A little electronic archaeology reveals some amusing exchanges:

"By all means create your own dialect of FORTH. While your at it, you can add the best features of PL-I, F77 and CORAL66. Then, look me up when you get out of college and we'll show you how it's done when you have to make a living" [1985 thread]
"This debate ... is very much like two engineers engaged in building a three-mile bridge arguing over the brand of blue-print paper they use." [1987 thread]

Passionate arguments can often be improved by actual measurements. How fast, expressive, and efficient is a particular language? That's what The Computer Language Benchmarks Game set out to provide, measuring time, source code length, and memory use of several dozen languages across a set of benchmarks.

If you have measurements, why not improve them with a visualization? And so I present to you an interactive, multi-dimensional, dynamic, whizbang-o-matic rendering of the Programming Language Wars.

Each circle is a language. Its horizontal position represents the gzipped source code size used to implement the benchmarks, which is intended to measure the language's "expressiveness". Its vertical position represents the real time used to execute the benchmarks, and its size (and color) indicate how much memory was used.

The cluster of languages in the top left are slow but expressive scripting languages. At the bottom right you will find C and C++, the fastest languages, but which take quite a bit more coding to get the job done. In between there is a tradeoff between speed and expressiveness, where lie languages like OCaml (which I happen to use whenever possible).

Actually, each point is only a summary of the language's performance: Consider some metric, like real time, and some particular language L. The Benchmarks Game folks ran implementations of a set of about 12 benchmarks (FASTA, Mandelbrot, ...) in L. L's time for each benchmark is divided by the best time across all languages for that benchmark. This gives us a normalized score for each benchmark; we take the median of these to produce a summary real time score for L. Then we do the same for the other metrics: CPU time, source code length, and memory.

The plot shows data for a single-core x86 box (assuming you haven't yet messed around with the controls). If you press the movie button in the bottom left, it will transition to results on a quad-core box. (Still normalized by the best single-core score. The labels say 1901 and 1904 since Google's API wants dates.) TIP: When you play the animation, select a few languages you're interested in and check the Trails checkbox, so the movement stands out.

To better visualize which languages' implementations took advantage of parallelism, and then click Play. The languages that move downward have improved their real time. Some stay in the same spot, probably indicating that the Computer Language Benchmarks Game doesn't have the best implementations.

Fine. Just tell me which language is best.

These benchmarks are almost certainly not representative of what you want to do. There are various flaws in this approach — how we choose to summarize (the median here) will affect the ordering of languages; the implementations are not perfect; some languages are missing implementations for some benchmarks; even for one language there are many possible implementations with different tradeoffs and only the fastest was tested; and so on. Perhaps most significantly, we're completely lacking important metrics like programmer time, maintainability, and bugginess.

Thus, just as someone out there thinks Circus Peanut Gelatin pie is a good idea, so most of these languages are the right tool for some job. We can't use these benchmarks to brand a language as useless. What I think the benchmarks and visualization can do is introduce you to general-purpose languages that may be a better solution for many tasks.

In particular, you might want to take a gander at the Pareto-optimal languages: those which, for every other language L, are better than L in at least one metric under consideration. If we consider source code length and real time as the two metrics, then the Pareto-optimal languages are:

1 core

4 cores

More expressive
Ruby 1.9
Ruby JRuby
Javascript TraceMonkey
Python PyPy
JavaScript V8
Lua LuaJIT
Haskell GHC
Java 6 SteadyState
C GNU gcc
Faster

More expressive
Ruby JRuby
Python CPython
Erlang HiPE
OCaml
Haskell GHC
F# Mono
Scala
Java 6 Steady State
C GNU gcc
C++ GNU c++
Faster

From top to bottom, these languages trace the best points in the tradeoff between expressiveness (at top) and speed (at bottom). Perhaps what this does best is to illustrate why it is hard to pick a "best" language. For the single-core case, 27% of the languages are on the list above; for quad-core, 48% made the cut. Even with just two simple metrics, many languages might be considered "optimal"!

Coming soon: a visualization of the 3D tradeoff space.

Notes

Last year, Guillaume Marceau produced informative plots based on the The Computer Language Benchmarks Game, similarly showing the tradeoffs between metrics. The CLBG has now included similar plots on their site. [Updated: the CLBG didn't use Marceau's plots directly.] The visualization here summarizes more (which can be good and bad), includes the memory metric and the quad-core data, and lets you interactively play with the data thanks to Google Motion Charts. A chat with Rodrigo Fonseca several years ago got me interested in plotting these tradeoffs. Finally, my apologies to those without Flash for the chart.

What happened to the Internet on Friday

2010-08-30T04:54:00.000-07:00

Note to readers: Judging from the past, this blog will have posts related to both computer science and politics. If you like, you can view just CS or just politics posts, or subscribe to feeds for just CS or just politics.

On Friday, a large disruption of Internet traffic made the news as an experiment gone awry. What actually happened? It's a good lesson in how fragile and insecure the Internet's routing protocol can actually be.

There was indeed a major event on Friday. A plot by Earl Zmijewski of Renesys shows that at the moment the experiment started — 8:41 GMT — about 3,000 IP prefixes became unstable. That is, the routes to these prefixes were quickly changing or being advertised and withdrawn. (An IP prefix is a chunk of destination IP addresses, the basic unit on which Internet routing operates.) Since there are roughly 300,000 prefixes announced globally, this is about 1% of the prefixes on the entire Internet.

We can also observe the effects by looking at the total amount of "chatter" in the Internet's global routing protocol, BGP. I created the following graphs based on raw data from the Route Views project.

This plot shows the rate of BGP messages received by one particular router, located at the London Internet Exchange. Routers are continually exchanging messages about new, changing, or unavailable routes to destinations all around the world. However, as you can see, the event in question vastly increased the rate of routing updates, exceeding the "background radiation" of messages by about a factor of 6.

The event was visible globally. Here is the same plot, for a router at Equinix in Ashburn, VA.

How can a disruption of this magnitude happen? Based on a note from RIPE, it went something like this:

Researchers at RIPE and Duke create a BGP announcement message, which advertises the availability of an IP prefix under their control. The message uses an unusual format, but one which complies with the BGP protocol format.
The message begins to propagate from router to router on the Internet, as normal, until...
...it reaches some router running the Cisco IOS XR software. These routers have (or had) buggy software which, upon receipt of the unusual message, corrupted the message before propagating it to other neighboring routers.
A neighboring router (call it N) has now received a malformed message from the Cisco router (call it C). N then follows the BGP protocol specifications which require that N terminates its BGP connection to C. This disrupts traffic to any destination which N reached via C (and vice versa) — not just traffic to the prefix originally announced by RIPE!
It is likely (depending on router configuration, so I'm not sure how common this is) that either C or N then attempts to re-establish the BGP connection. In this case, C re-advertises every route it knows about to N &mdash perhaps all 300,000 of them. And one of these would presumably be the corrupted message, causing the connection to again be terminated, and the process to repeat indefinitely.

It's always a good idea to isolate security problems to contain damage. And many BGP problems can be isolated close to the origin of the bad announcement. This event, on the other hand, apparently caused (brief) widespread damage for two reasons.

It spread geographically because the original announcement message was entirely valid, and was handled correctly by many routers. Thus, the message could reach buggy routers anywhere on the planet.
It spread to many IP prefixes beyond the original announced prefix, because the BGP protocol spec asserts that if a router sends a bad message for one prefix, it's unsafe to communicate with that router for destinations in any prefix.

Similar events have occurred in the past.

Despite the headlines ("Research experiment disrupts Internet") on Slashdot and Network World and the Renesys post's point of view, I find it hard to place much of the blame on the researchers. I assume it was not their intent to stress-test the live Internet. Clearly, one problem was the software bug which Cisco quickly acknowledged and fixed.

But we can also think about the protocol design. One way to better isolate the damage might have been for the router N to discard only the single malformed message from C, logging an error message but not terminating the entire BGP session between N and C. The counter-argument is that receipt of one malformed announcement raises the probability that other announcements are malformed, too. Indeed, in this bug, C apparently declared an incorrect header length; something similar to this could plausibly confuse N's parsing of all subsequent messages from C.

Looking into the much more distant future, a very different approach would be to base routing decisions on end-to-end observable behavior (do my packets actually get through to the destination along this path, or not?) rather than on relatively uninformative and attack-prone control plane announcements. This robustness is one potential benefit of designs like our pathlet routing and Xiaowei Yang's NIRA.

Political divisiveness at an all-time high, quantitatively speaking

2010-07-27T02:11:00.001-07:00

There's a lot of talk about politics becoming more divisive across parties, with less and less common ground, and Republicans being called and embracing the "party of no" label. But is it true? No need to speculate; we can find out with the help of the raw data in the form of Senate roll call votes (the last ~21.5 years of which are conveniently available), plus some perl scripts.

Number of votes over time

Let's start with something simple. Here's the number of yea/nay votes over time in the Senate. (By yea/nay votes, I mean I'm excluding some exceptional votes such as when the vote is Guilty/Not Guilty.) As the plot below shows, the number of votes has remained fairly steady across time, except that odd-numbered years get more votes and there was an unprecedented spike in 1995. And of course, 2010 is at a disadvantage for obvious reasons.

The Party of No

Does one party vote "no" more often? Below is the fraction of Yea votes cast by each party across time. There is some signal in this data, such as the Republican takeover in the mid-90s. And 2010 is so far at very low fraction of Yea votes by Republicans (49%), beat only by 1993 (43%). But this data clearly requires some more interpretation as to what a Yea or Nay vote actually means. One has to question, for example, why Republicans voted Yea more often in 2009 than Democrats.

The naysayingest senator

Moving to individual member stats, aggregated over the 21.5 years of the data, most members vote no about 30-40% of the time, but there are outliers who are quite agreeable and quite disagreeable:

Here are the top 20 outliers on either end. Current sitting senators, none of whom are in the Yeasayingest column, are linked to their Wikipedia pages.

Yeasayingest		Naysayingest
Member	% Nay	Member	% Nay
Barkley (I-MN)*	14.3	Wallop (R-WY)	49.9
Carnahan (D-MO)	21.5	DeMint (R-SC)	47.9
Burdick (D-ND)	23.7	Coburn (R-OK)	47.8
Matsunaga (D-HI)	24.0	LeMieux (R-FL)	45.5
Krueger (D-TX)	24.3	Goodwin (D-WV)*	45.5
Burdick, Quentin S (D-ND)	24.8	Symms (R-ID)	45.1
Mathews (D-TN)	25.6	Armstrong (R-CO)	45.0
Riegle (D-MI)	26.1	Humphrey (R-NH)	44.9
Bentsen (D-TX)	26.2	Vitter (R-LA)	43.5
Sanford (D-NC)	26.8	Barrasso (R-WY)	43.4

Jim DeMint takes the prize as the naysayingest sitting senator, but he's Walloped by the naysayingest of all time who voted no on almost half his votes. Malcolm Wallop very nearly maximized the entropy of his votes. Again, this data should be taken with a grain of salt, since how often one votes Nay depends on who currently controls congress.

*Barkley and Goodwin don't really count; Barkley was briefly appointed to replace Paul Wellstone and only cast 14 votes, 12 of them Yea. Goodwin was appointed less than two weeks ago to replace Robert Byrd and has only cast 11 votes, 6 of them Yea.

General disagreement

Yea or Nay votes could mean almost anything, depending what question is being voted upon. Here's a more robust metric: the agreement of a vote is 1 if everyone voted the same way, 0 if the vote was split 50/50, and linearly interpolated in between. We're currently at an all-time low of 34.4% (where "all-time" = the last 21.5 years), as you can see below.

But this doesn't expose the divisiveness between parties.

Political divisiveness

Here's what we really want to see: the average distance between Republicans and Democrats. On some particular vote, we can represent the average Democrat position as the fraction of Dems voting Yea; same for Republicans. Divisiveness is the distance between these two average positions. For example, if 50% of Dems and 50% of Reps vote yes, then divisiveness is 0. If 10% of Dems and 90% of Reps vote yes (or vice versa), then divisiveness is 0.8.

The data shows a striking difference. Politics were more centrist in the late 80s. Divisiveness didn't move much for about 18 years, but then divisiveness dramatically spiked since the beginning of the Obama administration, setting a record in 2009 and another record so far in 2010. The difference here is really quite dramatic: 29% divisiveness in 1989, vs. 70% today.

Party unity

Party unity is closely related to divisiveness. I'm defining unity as the fraction of members who take the majority position in their party, so 0.5 is the minimum score and 1 is the maximum. Party unity appears to have increased over time, though with some wild shifts particularly on the Republican side. Interestingly, Democrats seem to be just as unified as Republicans on the mean vote.

Anyone know where to get data going back earlier than 1989?

Update (July 29, 2010):

A few important points to emphasize:

One shouldn't read too much into this data. Divisiveness, as defined above, has increased---but this says nothing about why it has increased. As commenter GoldenBoy pointed out at politicalwire.com, we should naturally expect divisiveness to increase when one party has control of congress and the White House, since they have less need to work with the other party in order to pass legislation. The analysis here really says nothing about to what extent this or other factors caused the increased divisiveness.
Political scientists have performed much more extensive analysis than the simple graphs I've plotted in this post. Brendan Nyhan pointed me to Voteview.com which has great plots of polarization, party unity, and more back to 1879. As a commenter below noted, they also have complete historical roll call data back to the first Congress.
It's important to put the recent increase in divisiveness in the context of a longer-term trend of increasing polarization. There does seem to be a divisiveness spike in the last couple years, but in general an increase is not surprising.

Please exercise your civil responsibilities

2010-06-07T15:15:00.000-07:00

by voting for the best-named towns. (Note: having trouble viewing this in your RSS reader? Try this.)

Click Here for Poll Online Survey
Enterprise Feedback Management
| Polls
| Email Marketing

| Crowdsourcing Software
View MicroPoll

Yes, these are all real places. See also Name of the Year.

Eyjafjallajökull

2010-05-02T12:57:00.000-07:00

Incredible photos of lightning storms over Eyjafjallajökull Volcano in Iceland.

An optimization problem

2010-03-02T22:46:00.001-08:00

You are interviewed for an arbitrary job, which happens to do a background check. What criminal record maximizes your chance of being hired?

"None" is a valid criminal record, but is unlikely to be the optimal answer.

Inspired by a true story.

SIGCOMM 2009

2009-06-13T14:13:00.000-07:00

For readers interested in networking, I note that the SIGCOMM 2009 program is now available.

Also available is Pathlet Routing, our paper with Igor Ganichev, Scott Shenker, and Ion Stoica. Pathlet routing is a new Internet routing architecture which can improve scalability by enabling very small forwarding tables, and can allow senders to choose between multiple paths for improved reliability and path quality. The idea is basically to do source routing over a virtual topology whose nodes are arbitrary virtual nodes (vnodes) and whose links are sequences of vnodes (pathlets). Intuitively, this architecture is highly flexible because vnodes can represent arbitrary granularities, and because pathlets can represent policy constraints on routing while simultaneously enabling a large number of path choices. This is because sources can stitch together pathlets to form an end-to-end route in potentially exponentially many ways.

An interesting property of the design is that it doesn't impose a global requirement on what "style" of routing policy is used, but rather allows multiple styles to coexist. One router could choose to have routes like in today's Internet, with a giant forwarding table specifying only a single allowed route to each destination. And the next router could have a tiny forwarding table that still gives the network owner some control, but provides a high degree of path choice for the senders. I think of this as being very much in the spirit of the principle of designing for variation in outcome advocated by Clark et al. in their Tussle in Cyberspace paper.

Progress

2008-11-01T22:32:00.000-07:00

Gallup has asked, "If your party nominated a generally well-qualified person for president who happened to be X, would you vote for that person?" for X = {Catholic, black, Jewish, female, hispanic, Mormon, homosexual, atheist}. Below I have plotted their results over time.

Update August 6, 2010: The link to the raw data above no longer has it. But you may be able to get it through some combination of here and here (on the latter link, click through to the second page).

Angel Island fire

2008-10-12T23:03:00.000-07:00

Happening right now, a large fire on Angel Island visible around the San Francisco Bay. For size comparison, the island peaks at 788 feet; in the third picture is what I think is a three-story ferry. See also SFGate photos.

How Berkeley Can You Be?

2008-10-04T02:36:00.000-07:00

A few photos from the Thirteenth Annual "How Berkeley Can You Be!?" Parade, Sunday, September 28, 2008.

An arbitrage opportunity

2008-09-25T18:20:00.000-07:00

Nate Silver noted a discrepancy between the market prices for bets on who will win the presidential election at Intrade vs. other markets like the Iowa Electronic Market, with strange bidding patterns at Intrade. More discussion over at Computational Complexity. To help visualize it, here is a graph of the closing prices of PRESIDENT.DEM2008 at Intrade and PRES08_WTA at IEM. Update: CQpolitics: Trader Drove Up Price of McCain ‘Stock’ in Online Market It certainly looks as though there's been an unusually large difference in prices lately.

Recent results in nonlinear peer-to-peer reviewing algorithms

2008-09-11T00:23:00.000-07:00

On Monday I received spam, as many periodically do, from the World Multi-Conference on Systemics, Cybernetics and Informatics, WMSCI '09. Their peer review process having been previously demonstrated by Stribling et al. to be susceptible to random paper generation, they have a new strategy:

Submitted papers or extended abstracts will have three kinds of reviews: double-blind (by at least three reviewers), non-blind, and participative peer-to-peer reviews.

(Emphasis mine.) The conference web site further describes the peer-to-peer review process as

Informal, nonlinear, systemically interactive methods, for the achievement of what is called bottom-up quality[.]

This is great news; as a sometime peer-to-peer researcher myself, I'm eager to see nonlinear peer-to-peer reviewing technology adopted.

I understand that as future work WMSCI is developing an oblivious algorithm for ad-hoc low-power reviewing.

Computer Science Research Trends

2008-08-22T02:23:00.000-07:00

Computer science is a fast-changing field of research. Can we track some of its changes in the past? To answer this or any other question, experimental computer science researchers have essentially three options:

Write a program.
Search the Internet.
Write a program that searches the Internet.

We'll take the last approach in this post. We can pick a term and look at term frequency, that is the fraction of abstracts containing the term, as a function of time. Conveniently the ACM Digital Library and Guide have an advanced search that we can exploit to analyze term frequency across decades of abstracts. We'll start with a generic term, performance:

Let me say now, in case it becomes unclear later, that all the data presented here is actually derived from the ACM's database; it is not made up. (As for the interpretation of the data, well, ...) Moving on, we can plot a couple other terms, which and that:

The naive reader will conclude that conjunctions went out of fashion in the mid 80's, and came back after the dot com crash. However, the inappropriately perspicacious reader realizes that this conclusion is subtly flawed, because the word "that" might be a pronoun, adjective, or adverb: not just a conjunction. Fortunately the astute reader realizes we can look at relative instead of absolute frequencies to help clean up the data set.

The next group of figures are normalized by the term performance. For example, the blue line in the first plot below shows freq(mobile) / freq(performance).

Click on the image below for a larger version.

Now some "matchups", where x v. y = freq(x) / freq(y). Click on an image to enlarge.

distributed v. centralized
flat v. hierarchical
Berkeley v. Stanford
Us v. Them

They're winning, but we're gaining on Them.

Now our final, and perhaps most important, plot.

Good
v.
Evil

While computer science is solidly on the side of good, several abstracts in this search were disturbingly megalomaniacal, such as J. R. Landry's "Can computing professionals be the unintentional architects of evil information systems?", in ACM SIGMIS-CPR, 2008. The author "discusses how the technical rational paradigm supports the creation of systems that embody administrative evil" and aims to "determine if information systems can harm or be evil, the frequency of harm, and response to harm by designers and users."

We can be thankful that according to its abstract, the paper is only "a research-in-progress".

This post was originally an Outrageous Opinion at SIGCOMM'08. Here's a PDF of the original presentation.

Judicial Linguistics

2008-08-15T15:24:00.000-07:00

There is nothing inherently argumentative or prejudicial about transitive verbs [.]
— Sacramento County Superior Court Judge Timothy M. Frawley

Turns out it's not his first foray into judicial linguistics.

During a recent trial, both attorneys handling a case before Judge Timothy M. Frawley misused the word "acclimated" while questioning a witness. Frawley ... waited for a break in the proceedings and, outside the presence of the jury and witness, alerted the attorneys to the correct use of the word.

Graphing English

2008-08-06T02:31:00.000-07:00

Given two words, can we connect them by a chain of synonyms? For example: minuscule — little — short — poor — wretched — ugly — frightful — tremendous — enormous. Try some:

[Note, the tool's offline right now due to a system reinstallation ... should come back shortly ... -- Dec 6, 2011]

Connect two words with a chain of synonyms:

In the graphs above, each node is a word and an edge connects each pair of displayed words that can be synonymous. The raw data on semantic relationships is from Princeton's WordNet project.

Many word pairs are not linked. How large is the largest connected component—that is, the largest set of words such that any pair in the set can be connected by a chain of synonyms? An interesting graph theoretic question.

The answer is that the largest component has 25,105 words, or 17% of all words in the database. Meanwhile, the second largest component is over six hundred times smaller, with only 38 words (show it above).

Is this structure bizarre? Actually it's roughly what one would expect knowing random graph theory, which I'll now attempt to explain in one paragraph. A classic (Erdős–Rényi) random graph consists of n nodes, connected by a bunch of edges chosen uniform-randomly. Suppose the number of edges is such that on average, each node has d neighbors (for us, d synonyms). Imagine exploring a connected component by starting at one node and expanding outward: first looking at the nodes that are one step away from the starting point, then two steps away, and so on. What happens to the size of this frontier? If d < 1 then the frontier tends to shrink by a certain percentage in each step, so with high probability it dies out before the component gets very large. On the other hand, if d > 1, then the frontier tends to expand by a certain percentage in each step. Chances are pretty good that the frontier just gets bigger and bigger until the component includes a good fraction of all n nodes in the graph. That's the giant component. The second largest component must be very small, specifically O(log n) nodes, since otherwise it's likely to intersect with, and thus be absorbed by, the giant component.

Our graph of English has d = 2.92 synonyms per word. But of course English is not a random graph—which, with the same d, would have a largest component of 93% of its nodes and a second largest of about 5 nodes. Considering that we get within an order of magnitude without modeling any of the structure of the language except the number d, this is not so bad. And WordNet doubtless does not perfectly represent English: for example, it's plausible that common words are better annotated with synonymy relations than, say, abulia or vituperation.

I was led to think of this topic during conversation with some folks from UCL and CMU. But others have built a graph out of WordNet too (after all, it is called WordNet). A paper by Kamps, Marx, Mokken, and de Rijke, Using WordNet to Measure Semantic Orientations of Adjectives, scores words based on their relative distance to "good" vs. "bad".