New Work on Equitability and MIC

A few years ago, working with a diverse group of scientists, I was looking at a problem related to big data analysis.  The setting was data exploration, where you are working with a high-dimensional dataset, and you are seeking pairs of dimensions that are related in interesting but a priori unknown ways;  that is, maybe there's a linear relationship, but maybe there's a more complicated relationship (sinusoidal, parabolic, etc.), and you don't know what you're looking for in advance.

One statistical approach is to throw a so-called measure of dependence at the problem, which will tell you whether variables are related or unrelated.  But in big data sets, you may expect to have lots of dependent pairs;  what you really want is not just a "dependent-independent" test, but a scoring mechanism that ranks the extent of dependence appropriately over a wide range of possible relationships.  This methodology seemed underserved by the literature.  We dubbed what we were aiming for "equitability", and designed a statistic we dubbed MIC (maximal information coefficient), a "bucketed" version of mutual information, that seemed to be a good ranking mechanism for equitability.  The work appeared in Science some years back (the link here will allow you to access it). 

The work has, I think, been quite successful -- a number of people have used MIC in their research to analyze data sets, and the idea of equitability seems to be catching on.  But after it came out, there were some questions and issues raised primarily by statisticians.  We had always planned to go back and revisit some of these issues, and, after various delays caused by life, a group of us started back on it again.  The project seemed to balloon, and we've been working on and off on it for at least a year now.  (Some earlier, initial drafts pointing to where we were going are on the arxiv.)   Finally, we've reached a stopping point, and we've just put up 3 papers on the arxiv, all of which are now being submitted to various journals.  In this post, I'll outline what the papers cover, after the links.

1. Equitability, interval estimation, and statistical power. arXiv
   
   
2. Measuring dependence powerfully and equitably. arXiv
   
   
3. An Empirical Study of Leading Measures of Dependence. arXiv 

Really, there seemed to be 3 issues that people wanted to hear more about after the initial work, and each topic ended up being "large" enough that it merited its own paper.

First, people wanted further theoretical foundations for equitability.  Our Science paper, being for a general audience, provided an intuitive definition, but we didn't define it as one would in a mathematics paper.  (That was, I should be clear, intentional.)  We thought our definition was pretty clear in plain English, but for some it was not sufficient;  one group, in particular, seemed to ignore our explanations when in their own work they added restrictions to "equitability" and incorrectly ascribed them to us. 

So the first paper formalizes this notion of equitability.  As is usually the case, formalizing it turns out to be helpful.  In particular, it shows that there are (at least) two natural ways of thinking about equitability.  One way formalizes our original conception that an equitable statistic is a statistic that gives similar scores to relationships with the same amount of noise, even if the relationships are of different types.  But a different way of viewing the formalization shows that equitability can naturally be seen as an extension of statistical power against a null hypothesis of independence (i.e., relationship strength = 0), to power against null hypotheses representing all levels of dependence (i.e. relationship strength <=x for any x).  This view clarifies the relationship between equitability and power against independence, showing the former generalizes the latter.  In our new papers we have some really nice "heat-map" style visualizations for viewing equitability performance results based on this view that I think are really useful in thinking about and understanding equitability in the paper.  

Second, people wanted faster, better versions of our proposed scoring function, MIC.  We ended up going back to the theory of MIC, examining further its relation to mutual information, and, perhaps unsurprisingly, doing so allowed us to make tangible practical advances.  We ended up with algorithms for computing MIC that are both faster and more accurate.  (Our original algorithm in the Science paper used a heuristic approach based on dynamic programming to approximate the MIC score from the data;  our new approaches have both improved speed and accuracy.)  We're hopeful that people using MIC will be able to switch over time to these improved algorithms.  Connecting to the first paper, in re-examining MIC we also developed a variation of MIC (called TIC, for total information coefficient) that is better designed for achieving power against independence as opposed to equitability.  We are hopeful that TIC may prove useful to people on its own, as well as in conjunction with MIC. 

Third, people just wanted to see more comparisons.  Well, really, here I think everyone just has their own favorite measure of dependence, and before they go switching to this new-fangled thing that appeared in Science of all places, they want to see more.  Specifically, subsequent to that initial paper, there were people concerned about the power against independence of our methods -- although, again, to be clear, equitability is a larger notion that power against independence, so one might expect a method designed for equitability would not have as high power against independence as methods designed specifically for that purpose.  Also, there were some people who claimed, based on very limited experiments, that mutual information estimation would be more equitable than MIC.

So the third paper is a large-scale empirical study.  In terms of equitability, we find that MIC still seems to be the current best measure.  (Mutual information sometimes does well -- in some very particular circumstances, it can do better than MIC, which is not especially surprising since MIC is a "scaled" version of mutual information -- but MIC still performs much better overall.)  In terms of power against independence, we find that MICs power was underrated in previous studies.  The discrepancy seemed to be that previous studies used MICs default parameter settings, which were designed for equitability performance, not power against independence;  using different default parameters yields substantially better power against independence.  (The new algorithms in the second paper that yield more accurate calculations improve the power further.)  Finally, the TIC measure described in the second paper does even better, is easily computed when computing MIC scores (and so has negligible overhead if computing MIC scores), and appears to be comparable to other state-of-the-art measures in terms of power against independence.  We also find that the new ways of computing MIC are indeed faster and more accurate than previous methods. 

We're hoping these works, collectively, move the ball forward on this topic.  We like seeing MIC being used, and hope people will start using it more when analyzing their large dimensional data sets.  To be clear, perhaps tomorrow we will find that there are better scoring mechanisms than MIC for equitability;  perhaps even better mutual information estimators will suffice.  That would be great!  (I think of it like clustering algorithms;  there are lots of good clustering algorithms, different ones may be better suited to different situations.  The more the merrier.)  We also think equitability continues to be a useful framework, and that there's more to be done with equitability.  Though for now our group may again take a breather on this topic, and see what arises from our current work. 

Girls Who Code (Newton) Visit to Harvard

My friend David Miller is looking for instructors to help out with the Newton Girls who Code club.  Here's an announcement, please connect with him if you're interested. 

They visited Harvard last week -- David gave me permission to post his description of the visit.  It seemed like a well-organized event -- thanks to the Harvard Women in Computer Science group for putting it together.

----

Last Friday, the Newton Girls Who Code club was welcomed by the Harvard Women in Computer Science at Harvard's Maxwell-Dworkin Laboratory. The students learned about the joint Harvard-MIT Robot Soccer team from the mechanics tech lead, Harvard junior Kate Donahue. She showed us last years fleet of robots (named after Greek and Roman gods), and described their work on preparing this years fleet (to be named after Harry Potter characters). Kate emphasized the interplay between computer vision, artificial intelligence, mechanical engineering, and distributed systems. Many of the robot parts are 3D printed -- a technology that the Newton GWC students will become more familiar with this fall as we integrate the Newton Library's 3D printer into the GWC activities.
 
After the robots demonstration, the students took part in a Q+A discussion with Harvard WiCS undergrads Hana Kim, Ann Hwang, and Adesola Sanusi. Our students asked great questions about our hosts' motivation and history with coding, the mechanics of being a college CS major, the role of gender in the CS community, the connections between computer science and other fields, and our hosts' vision for the future of computing. The WiCS undergrads are excellent role models and were enormously encouraging. They pronounced our students more than ready to take Harvard's most popular course, Introduction to Computer Science, and recommended they try out the free, online, EdX version today. It was an exhilarating afternoon!

My (Positive) Apple Retail Repair Experience

I switched to Apple machines several years ago, and have been very happy with them generally.

One convenience is there is an Apple store in the mall about 10 minutes from my home, so when things go wrong, I know where to go.  Thursday night a screen-related hardware glitch developed (which, to be clear, in this case was not what I would call a product defect;  let's say it was a me defect).  I ran over and they said it would probably need to be taken in for a repair.

Not being ready to hand over machine just yet, I went home to pull off some data, and then booked an appointment.  The downside to the Apple store is you really need to book an appointment online, even for (or especially for) things involving repair.  My walk-in Thursday I didn't even get up to the Genius Bar; one of the people up front just suggested what they thought was going on.  And my Apple store, at least, is painfully busy, all the time.  I got an appointment for Saturday afternoon, nothing available Friday.  I went in Friday morning before heading to work on the off chance I could get it in then;  they said the walk-in waiting time was 90 minutes to 2 hours.  I should have expected;  the walk-in waiting time always seems to be measured in hours.

That's the downside.  The positive is, when you have an appointment, they are great.  I had no wait when I went in Saturday, and in the past, if they're running behind, they've let me know if I have to wait for my appointment and estimated for how long.  They are courteous and professional.  They will let you know what they are doing as they test your machine, what needs to be done, and provide estimates for how long it will take.  Their setup really engenders trust.  I also have found their repair times reasonable and understandable.  My machine is back to me and all is well Monday afternoon.  (Thank you, Apple Store.) 

I haven't had to deal with them often over the last decade -- I'd say a reasonable number of times considering the number of Apple machines I've had and in family use.  Overall this experience is typical.  There's anxiety in going in for any sort of repair process, but they did an excellent job.

Finally, I imagine this is not useful advice to people reading this blog, but do back up your data regularly and/or automatically.  One of the first questions they always ask is whether you have a backup, and it's always a good feeling to know that if worst comes to worst you just put your state on a new machine.  Someone else at the Genius Bar while I was there had their computer put back in working order but their data was lost;  they weren't the sort of user that it was a real problem, but the occasional reminder that backups are important is always helpful.

  

Women in Math (and Computer Science)

Wednesday afternoon I went to a panel organized by the Harvard Undergraduate Mathematics Association for a "Gender Gap on Math Discussion".  I went both to hear what was going on (as there's still that gender gap in CS, and we're always eager to hear ways that we might do things better that might reduce that), and for moral support for some people I know who were involved.  The panel was co-organized by Meena Boppana, an undergraduate who did research with me the summer before last and is currently a star in my graduate class, and one of the panelists was Hilary Finucane, a graduate student who I advised on her senior thesis and collaborated with on multiple papers with when she was an undergraduate at Harvard.  I should note that Meena and several others had done a survey of Harvard math undergraduates which had highlighted some issues that would be a starting point for discussion.   

I could only stay for the first half or so, but it seemed very positive.  A number of faculty showed up, which was promising.  My take on the panel's take was was that they were interested in how to make improvements in the culture, and the goal was to try to start figuring out how that could happen, in part by sharing their experiences.  The discussion was both balanced and thoughtful, presented positives with negatives, but focused on how to improve things.  There's a writeup in the Crimson with more details.  The main point that came out in the first half was something I've seen and heard before:  the importance of having a community, including (but not necessarily limited to) a community of women that can offer support, guidance, and mentorship, but also just so you don't continually feel like the only woman in the room. 

And as long as we're on the subject, there's been a number of recent stories (or older stories where I've recently seen the links) on women in math and computer science.  Focusing on Harvard to start, there's a nice writeup about Harvard's Women in Computer Science group, which has helped provide that community that encourages women to take classes in and concentrate in computer science.  An article from last year discusses progress at Harvard in closing the gender gap in computer science.  There was even an article in the Harvard Political Review covering gender gap issues at Harvard.

Outside of Harvard, from sources on Google+ I've seen a blog post with an interesting slide deck from one Katie Cunningham that provides a great starting point of discussion about the culture and women in computer science.  And, finally, a link to something simultaneously sad and funny (things-male-tech-colleagues-have-actually-said-annotated) that reminds us why we have to keep trying to improve the culture. 

On the Shannon Centennial

I found in my snail mail mailbox my paper copy of the IEEE Information Theory Society Newsletter.  First, I was delighted by the news that Michelle Effros (of Cal Tech) is the new President of the IEEE Information Theory Society.   Michelle has a long history of service (as well as, it goes without saying, outstanding research) in the information theory community, and is a great selection for the job.

In her opening column, Michelle discusses the importance of letting people outside of their community know what the information theory research community is doing, especially with the Shannon Centennial (April 30, 2016 will be the 100th anniversary of his birth) coming up.  The IT Society will be spearheading outreach efforts as part of the Centennial.  As Michelle says,

Every school child learns the name of Albert Einstein;  his most famous equation has somehow entered the realm of popular culture.  Why is it that so few people know the name or have heard about the contributions of Claude Elwood Shannon?

In Computer Science, Turing is our "guiding light", and we had a very successful centenary celebration -- as well as a recent popular movie The Imitation Game -- to make Turing's life and work as well as the importance of computer science as a scientific discipline more well known and understood to the rest of the world.  But Shannon, too, is one of the guiding lights of computer science;  it is hard to imagine large parts of computer science theory and networking, for example, without the foundations laid out by Shannon in developing the theory of communications.

I have always thought that the Information Theory community and the computer science community -- particularly on the theory side -- should interact and communicate more, as there are huge overlaps in the problems being studied and still significant differences in techniques used (although there's more and more crossover in this regard).  Perhaps the Shannon Centennial will provide some grand opportunities for the two communities to come together, to promote the Shannon legacy, and as a side benefit to learn more from and about each other.

Links: HBR article on Women in STEM and AAUW Report

A latest article on bias issues for women in STEM by Harvard Business Review. 

A slide presentation by AAUW related to their report: Solving the Equation: The Variables for Women’s Success in Engineering and Computing.  The full report can be downloaded for free here.  

Double Hashing (Lueker and Molodowitch)

A subject I've grown interested in, related to multiple-choice hashing schemes, is when (and why) double hashing can be used in place of "random hashing" with an asymptotically negligible difference in performance.

One early, useful work on this subject is by Lueker and Molodowitch.  They provide a very nice coupling argument between double hashing and random hashing in the setting of open address hashing in their paper More Analysis of Double Hashing.  (The original paper appeared in STOC 1988.)  In this post I'll summarize their argument.  I apologize that both the text and my exposition might be a little rough. 

They work in the open address hashing setting;  each key runs through a permutation of the table locations when it is being placed, and it placed in the first empty location, with each location holding a single key.  When searching for a key, we run sequentially through its permutation;  we either eventually find the element or we find an empty slot, in which case we know the key was not in the table, and the search was unsuccessful.  We measure the expected time for an unsuccessful search when a table with m slots is loaded with pm keys for a constant fraction p.  For convenience we will have m be prime, as this will simplify matters when we consider double hashing.  If each key's permutation is completely uniform over all permutations, we call this random hashing, and the expected time to search for key not in the table is 1/(1-p) + o(1);  with some work you can get that it is 1/(1-p)+O(1/m), but we will not concern ourselves so much with the low order terms here.

With double hashing, for a key x, the permutation is given by h_1(x)+ j h_2(x) mod m for hash functions h_1 and h_2, where h_1(x) is uniform over the range [0,m-1], h_2(x) is uniform over the range [1,m-1], and the permutation takes the values in the order j=0,1,2,...  This gives a permutation (because m is prime), and with double hashing, you just need two random hash values, which from a theoretical standpoint is "much less randomness" than a fully random permutation, and from a practical standpoint is easier to implement. 

What Lueker and Molodowitch show is that for any (constant) load factor p, with double hashing, the expected time for an unsuccessful search remains 1/(1-p) + o(1).  They show this through a coupling, which shows that double hashing and random hashing can be coupled so the "the same thing happens" -- that is, the key goes into the same slot -- under both double hashing and random hashing most of the time.  Unfortunately, it doesn't happen all the time;  the coupling is not strong enough to say that all the keys are placed the same with high probability.  But they show that they can arrange the coupling so that thing work out nicely just the same.

To start, let us start with a setting where we have loaded our tables with n keys using random hashing, and now take two copies of our state, and consider a single step of random hashing in one copy and double hashing in the other copy, side by side.  Clearly, for random hashing, the probability that a key is placed in any empty slot is 1/(m-n) for each slot.  In expectation (over the random past), by symmetry, for double hashing the expected probability that a key is placed in any empty is 1/(m-n), but the actual probability for each slot will depend on the configuration.  But what they show, using Chernoff bounds, is the the actual probability the key is placed in each slot is at most q/(m-n) for some q that is (1+o(1)), with high probability over the past random placements of the n keys.

Now for the coupling.  Starting from empty, at each step we use double hashing in both of our copies with probability 1/q = 1- o(1).  Note that this ensures that the probability a key is placed in the "random hashing" copy of the process is at most 1/(m-n), so far.  So with probability 1/q, we have placed the key in the same slot in both tables, and so it is as though we've done random hashing for this step.

But what about what happens with probability 1-1/q?  Maybe we could ignore it, if 1/q was 1-o(1/n) for example, as a low probability event;  unfortunately, that's not the case.  In particular, we actually expect that the coupling will fail for some smallish (polylogarithmic) number of steps.

Instead, with probability 1-1/q we place the key so that the step follows random hashing in total.  I'm not saying with probability 1-1/q we place the key at random;  I'm saying we place the key so that, in total (including the 1-1/q probability first step where they key was placed by double hashing) we place the key so that, overall, the probability any empty slot obtains the key is 1/(m-n).  Another way of thinking about this is in the other direction;  my coupling always placed the key according the random hashing, and with probability 1/q (which again is very close to 1) that matches what would be done with double hashing.

So in our random hashing copy of the table, we just placed a key according to random hashing.  How should we think of what is happening over in the double hashing copy?  For that table, with probability 1/q all went fine -- a key was placed by double hashing -- and with probability 1-1/q some key just dropped into the table that wasn't placed by double hashing.  It's like an extra present from above.  But it's not a key placed by double hashing.

The next part of the argument is to recognize that that's OK, in the following sense.  If you simply add a key anywhere is an open addressed hash table, you just make things worse, in a very specific way.  Any slot in the table that would have been filled if you hadn't put in that key will still be filled at the end of the process even when you add that key.   That is, if S is the set of slots that would contain a key if no extra keys get placed, and S' is the set of slots that contain a key if you, at various points in the process, just add some extra keys anywhere at any point, then a simple induction gives S is a subset S'.

So now let's consider multiple steps of this coupling.  At each step, the ball is actually placed according to random hashing, so at every point in the process, the "state" is that of a random hashing process.  On the double hashing side of the coupling, with probability 1/q a ball was placed by double hashing, and with probability 1-1/q an extra ball was just placed.  So if we count the number of balls placed by double hashing, when we reach the time when n keys have been placed by double hashing in this process, on average n/(1-1/q) = n(1+o(1)) keys (in expectation -- by Chernoff bounds one can get a high probability result) have been placed overall.

The result:  placing n keys by double hashing is stochastically dominated (in terms of the keys that have been placed) by placing n(1+o(1)) keys by random hashing.  In particular, after we place n=pm keys using double hashing, the expected time for an unsuccessful search is bounded above the expected time for unsuccessful search after putting in pm+o(pm) keys using random hashing, which is 1/(1-p) + o(1).  You can do a similar sort of coupling to show that double hashing stochastically dominates placing n(1-o(1)) keys by random hashing.  As a result, asymptotically, there's only an o(1) difference in terms of the expected time for unsuccessful search, a result which explains the negligible difference in performance one sees in implementation.





  

Power of Randomness at Georgia Tech

I'm spending (part of) the week at "The Power of Randomness in Computation Workshop", an IMA (Institute for Mathematics and its Applications) and ARC (Georgia Tech Algorithm and Randomness Center) co-sponsored workshop at Georgia Tech.  Here's the schedule.  I'm told slides will eventually be put up somewhere on the IMA website for such things.  Great organization at Georgia Tech -- a big crowd in a very nice room, lots of food and coffee, all very well organized.  They even had Ben Affleck waiting in front of the building for us this morning.  He seemed to be a little busy shooting a movie to greet us properly, but maybe he'll have a bit more time to chat tomorrow.  

Besides Ben, a few other highlights:

Leslie Goldberg started things of talking about the complexity of approximating complex-valued Ising and Tutte partition functions.  I remember the Ising/Tutte models (mostly from graduate school and shortly after);  now there are connections between various problems in quantum computing and these functions on complex values, which (or course) I had not known.

Nike Sun gave a talk on the exact k-SAT threshold (for large k).  It was very clearly presented and gave the argument at the intuitive level.  I gained some insight into why the "locally random tree" type argument I've enjoyed in coding/belief propagation arguments breaks down in certain satisfiability problems, due to clustering of solutions and other challenging correlations, and how those issues can be handled. I started to understand (I think) the point of replica symmetry breaking arguments and how they were used to guide the analysis of the k-SAT problem.

Other talks from the day:  Amin-Coja Oghlan also talked about replica symmetry techniques and their uses for random graph coloring problems, Eli Upfal talked about some new shuffling techniques for oblivious storage dubbed the Melbourne shuffle, Aravind Srinivasan gave a talk on the Lovasz Local Lemma (staring from the Moser-Tardos results and showing how these arguments carry forward and give greater power and insight into the use of the LLL for additional problems), and I talked about invertible Bloom lookup tables and briefly mentioned a few other unrelated things in progress.

  

Hate EasyChair

I just typed in a nice long review on EasyChair.  Yes, I prefer doing this with the online form when I'm just sitting around and have time to do a review. 

Apparently I didn't hit one of the score buttons (although I'm pretty sure I did, let's give EasyChair the benefit of the doubt there) so EasyChair says there's an error and, of course, forgets my nice long typed review when it takes me back to the review page, so I'll get to re-do and re-type it later. 

Sigh.  I guess I'll go back to doing my reviews in a text file and cutting and pasting.  No, this has not happened to me in recent memory in HotCRP.  Put this down as one more reason (but not the only one) why I don't like EasyChair and would prefer a better designed system (like HotCRP...).

New Heapable Subsequence Paper

In the "only a dozen people could care about this category"...

About 4 1/2 years ago, I posted about a paper we had put up on the arxiv about Heapable Sequences and Subsequences.  The basic combinatorial structure we were looking at is a seemingly natural generalization of the idea of Longest Increasing Subsequences.  Say that a sequence is heapable if you can sequentially place the items into a (binary, increasing) heap, so each new item is the child of some item already in the heap.  So, for example, 1 4 2 3 5 is heapable, but 1 5 3 4 2 is not.  Once you have this idea, you can ask about things like the Longest Heapable Subsequence of a sequence (algorithms for it, expected length with a random permutation, etc.).  Our paper had some results and lots of open questions.

I admit, when we did this paper I was hoping that some combinatorialist(s) would find the notion compelling, take up the questions, and find some cool connections.  Longest Increasing Subsequences are somehow related to Young tableaux, interacting particle systems, and all sorts of other cool things.  So what about Longest Heapable Subsequences?

I had to wait a few years, but Gabriel Istrate and Cosmin Bonchis recently put a paper up on the arxiv that makes these connections.  Here's the abstract:

We investigate partitioning of integer sequences into heapable subsequences (previously defined and established by Mitzenmacher et al). We show that an extension of patience sorting computes the decomposition into a minimal number of heapable subsequences (MHS). We connect this parameter to an interactive particle system, a multiset extension of Hammersley's process, and investigate its expected value on a random permutation. In contrast with the (well studied) case of the longest increasing subsequence, we bring experimental evidence that the correct asymptotic scaling is 1+5√2⋅ln(n). Finally we give a heap-based extension of Young tableaux, prove a hook inequality and an extension of the Robinson-Schensted correspondence.

(Note, that should really be "Byers et al...")  

I love the new conjecture that the expected minimal number of heapable subsequences a random sequence decomposes into is ((1+sqrt{5})/2) ln n.  (It's clearly at least ln n, the expected number of minima in the sequence.) 

There are still all sort of open questions, that seem surprisingly difficult;  and I certainly can't claim I know of any important practical applications.  But Longest Heapable Subsequences just appeal to me as a simple, straightforward mathematical object that I wish I understood more.

For simple-sounding but apparently difficult open questions,  as far as I know, the answer to even the basic question of "What is the formula for how many sequences of length n are heapable?" is still not known.  Similarly, I think the question of finding an efficient algorithm for determining the Longest Heapable Subsequence (or showing it is hard for some class) is open as well.  

Stress: Competition and Ranking

One issue I keep seeing in comments here and elsewhere on this issue is that academia is very competitive, with everyone worried about their rank.  In my last post, I admitted that it would be hard to completely deny that there is competition, particularly when people are younger, which tends to come out when jobs are at stake.  But, for the most part, I think the role of competition is completely exaggerated, strangely so.  Academia -- at least, certainly, my branch of it -- thrives on collaboration, and I believe people who go into it thinking that it is a big competition are going to lose out, both professionally and in their enjoyment of the profession.  (Indeed, one of the reasons I write these posts is because I don't want undergraduate and graduate students getting what I think is a one-sided, incorrect view of how academics work.)

First, I would again like to compare academics with other professions.  I've seen comments (including on this blog) that other professions are less competitive than academia, and people are less worried about rank.  I think people who are making that suggestion need to check in with people working in those professions, because I think they're ridiculously wrong.  Lawyers coming out of school to get jobs, doctors trying to get fellowships or residencies, consultants at consulting firms -- all very competitive.  As you move up, this continues.  For lawyers, there's who can bill the most hours, and the challenge to make partner;  for doctors, who can get the best positions at hospitals;  and for businesspeople, every promotion is a step up.  Even for software engineering types, there's competition.  When I was a graduate student, I recall visiting friends who had gone to a large well-known company, and for a large part of the evening all they talked about was what "level" they and others were in the company and the annual reviews and who was doing what project that might get them ahead.  So let's not be delusional and start by acknowledging that there's competition everywhere, and that's unsurprising when jobs and money are at stake.  While I'm not suggesting I have deep knowledge of all of these careers, I think academics have much less competition than most.  

If academics appear like they're concerned about ranking, perhaps it's because they appear to be easy to rank.  First, as I pointed out last post, there's not that many of us.  Second, there are obvious metrics everyone can understand:  number of papers published, number of papers appearing in "top" conferences, and h-index stand out.  I'm not suggesting these are good metrics -- but they're easy and to a first order give (potentially) some useful information.  They're a quick way of bucketing or sorting people, particularly those without an established track record and are therefore not necessarily widely known or visible in the field, and therefore have more of an impression and an impact on younger academics.

But very quickly after your PhD, this sort of ranking loses its importance, and the very idea of ranking starts to lose its value -- as many have noted in a variety of venues.  In academia, there's lots of ways to be successful, many points on the Pareto frontier.  There are many great results waiting to be found and many different subfields to work in.  At the end of the day, a history of good work and specific achievements is what people look for;  there's not really a finite pool of such things for which to compete.  Indeed, I'm not sure how I would go about competing with the top people in the field, except to try to do interesting work, which is what I'm trying to do anyway.  (A secondary way to compete is just to make sure people know about your work.  But giving talks is less important to being successful than doing the work that goes into the talks in the first place;  again, it can have a bigger impact for people in the early stages of their career.) 

Against this idea of competition, just look at how people in academia work together.  In computer science theory, in particular, most papers have several authors working together.  In a number of cases these are students with their advisors, but a closer look reveals that in many cases, they are not.  Credit can be shared easily in academia, and collaborations can lead to results that individuals could not get alone.  Working in groups is a way for people to get more done.  Instead of competition, collaboration often yields the path to having a greater impact on the field.  Rather than being a "competitive game", research is more a "cooperative game".  (As an aside, this is why theory's approach of alphabetical order for authors rather than some sort of implicit "credit scheme" based on author order makes such great sense.)  In most areas of computer science that I've participated in, a similar spirit prevails.

I encourage graduate students to team up pick out projects to work on together (and have seen this at other places, also -- one of my best experiences as a graduate student was such a project).  It gives them something to do and a sense of ownership outside of working with their advisor.  And, importantly, in reinforces that these other students are their colleagues, and that working together is a great idea that can gain for everyone.  Hopefully, they also learn that working together is more fun and generally more productive than working alone.  When it comes to hiring time, it's nice to see students who have worked on such team projects, because I typically prefer colleagues with a track record of working well with others.     

Sometimes small competitions break out, sure -- multiple groups are working on the same or similar problems.  Often, though, this is a very healthy competition, pushing progress forward in an area over a series of papers.  I remember in the past an argument with another group when we were working on similar problems and an issue of "credit" in the writeup of the various papers came up.  A week later, we were starting collaborations together on new ideas.  That's not exactly the sign of a super-competitive landscape. 

It could be that I've just got a mistaken impression of the field.  Harvard is a wonderfully collaborative place, and personally I've found overall I like working with others more than on my own.  But when I think of cutthroat competition, I don't think of the job I'm in.

To conclude the post, I think what may be going on is people confuse "competition" with "drive".  Most academics are smart, successful people, who are internally driven by a desire to do great work.  To many, that must appear like "competition", but if so, it's internal competition -- you're not out to beat others, but to be our best.  And I think it's very possible academia does have more "Type A" personalities that have this internal drive that is, surely, not always healthy.  It's not clear to me that this academia's fault -- such people would be similarly driven in any career -- but, if it is true, then it suggests we might consider if this is best for our field, and how we might open up the field to a wider set of personalities or how we might make work in this field healthier for this type of personality.  

Stress, Continued: Jobs

Continuing from last post, I aim to focus on some of the issues related to stress in academia.  Today's post will be related to stress and the nature of academic employment.

The most stressful issues I can think of in academia relate to finding or keeping your job.  Graduating and finding the first job, especially when the job market is tight, cannot help but lead to stress for most people.  (Indeed, these days, the process seems to be getting worse -- as postdocs become normalized in Computer Science, many people have to find the their "first job" two or more times.)  Similarly, when you come up for tenure, it's obviously very stressful.  Even if you think you deserve tenure, there is uncertainty because the process it outside your control, and the 1-bit decision can have a tremendous impact.  While changing jobs later can also be stressful, and I'll discuss that, these two times seem to be the worst.

As a starting point, however, compared to other professions, the issues related to getting a first job and tenure are not especially unique to academia.  Doctors have residency and specialization after medical school, lawyers wait years to become partner.  Business people have it different, perhaps;  tech startups notwithstanding, there are people who still climb up the corporate ladder.  The tenure situation is, arguably, a more severe end goal than in other professions, but with what seems to be a commensurate reward;  you don't really have to worry about a job after, if you are willing to stay at your institution.  The framework and corresponding stress seem comparable to many other career paths, although there are career paths that avoid such poignant milestones.  In particular, in computer science, many students from top institutions can quickly and readily find work at major companies or startups, and their stress seems to come from having a wealth rather than dearth of choices.

Would there be changes to the system that would help?  I don't think so, and this requires some explanation.  The issue of job stress, to me, seems fundamentally an issue of supply and demand.  In the top 20 computer science departments there are approximately 1000 professor jobs.  Heck, maybe I'm off by a factor of 2, depending on how you count (tenured vs all, maybe top 30 instead of 20).  Positions turn over very slowly.  In short, academia is a niche market, with a small supply of jobs and, generally, heavy demand for them.  This creates a lot of friction in the system.

In years past, we've seen a slowdown in the CS academic job market.  Even small slowdowns create tough situations with the small job supply.  The solution was to introduce more postdocs.  It was a working solution for the time, but with risks and downsides -- a de facto postdoc requirement added into the employment picture? -- that leaves us with as many questions as answers.

Similarly, tenure seems like such a huge deal in large because one cannot readily move to another position easily.  Yes, there is the issue of being rejected, and the corresponding loss of prestige that goes with it, but even ignoring that, the challenge of where to go (in academia) if tenure is not granted looms large.  The problem extends past tenure.  Even very good people can find it hard to move, as the small number of jobs available make for an inflexible, challenging job market.  If I was at Google and wanted to work at Facebook or some other company, such a move should not, generally, be difficult;  people make such switches pretty regularly.  If I walked over to MIT and told them I would like to move there, there are huge barriers, perhaps the most obvious of which is MIT has a wealthy choice of wonderful people it could choose to hire instead, and is careful in choosing who it hires to one of those limited slots.  Indeed, at most other schools, the obvious issue is whether there would even be a senior position available, but MIT computer science always seems to have a position if it wants one.*  The upshot is if later in life a professor wants to switch jobs for any number of personal reasons (dissatisfaction with the current location, divorce or family issues, etc.), it's not always easy or possible to do and stay in academia.   The problem is again related to scarcity in jobs, and solving that problem seems out of reach, involving changes to institutional or societal structures.  (That is, we have to convince our universities we need to hire more CS faculty, and/or we need to convince society to spend more on research/professors/education.)

The job stress issue is the most prominent stress issue I see in academia, and I think it underlies a lot of other stresses.  When people say academics are over-concerned with and spend too much time jockeying for being ranked highly -- a point I have issues with and I'll return to in a later post -- to the extent that's true, I think some of it is inescapable in such a job market.  When you graduate, you'll be compared to other graduates and that will have an effect on what jobs you can get.  When you are up for tenure, you'll be compared to peers, implicitly or explicitly.  If you want to switch jobs post-tenure, how you compare to people at the institution you wish to move to and to others in your field is important.  All of these comparison points become more important in a tight, friction-filled job market.  As much as I'd like that not to be the case or deny it, I think it's better to face the reality of it.

What possibility is there for a solution?  The easiest I can think of is to expand the job market, which I think comes from industry jobs.  As part of this, we have to help make sure industry sees the value and importance of research, and of having its own researchers.  Some people have said that academics look down on "non-academic" employment for students and especially PhDs.  I don't think that's generally true in CS, but to the extent it is, that's setting unrealistic expectations for outcomes for many -- or most -- of our students.  The virtues of jobs in industry are well documented, as are the virtues of academic jobs;  maintaining a culture where both are seen as positive outcomes seems healthiest for stress levels of individuals and for the health of the CS academic community generally.  

Other solutions welcome and more to come.

* Just kidding around with you, MIT.  But seriously, is there any upper bound on you all?

 
    

Stress

I've seen lots of news and posts recently on the general theme of stress in academia. Daniel Lemire blogs about Stefan Grimm, a professor who recently committed suicide, and talks about academia as an anxiety machine.  More close to home, we recall that Seth Teller committed suicide earlier this year.  Previous Harvard faculty member and loud blogger Matt Welsh frequently portrays academia as a stressful place (most recently discussing the Fame Trap), and recently Harvard's Radhika Nagpal offered her advice about the scary myths of academic life and how to find happiness.

So here is my question, and I don't think it's a simple one:  is the academic world a stressful place?  The above are an interesting set of anecdotes, but there are certainly contradictory anecdotes. 

For example, as a starting point we might look to the CareerCast list of least stressful jobs, where university professor was judged the least stressful job in 2013 (and nearly the least in 2014), and the reaction to it.  (A nice Forbes article here, and last year's related article here with hundreds of comments.  Inside Higher Ed articles here (2014) and here (2013).)  The big quote this year from Inside Higher Ed:  

Tony Lee, publisher, CareerCast, added via email: "We received a lot of feedback about our ranking of university professor as a low-stress job. But we found that while adjunct and part-time teachers are right that their jobs can be stressful, the stress levels for tenured university professors – which is what we rank – are lower than the majority of other jobs we measure in our report."

My own take on this amusement (before we get to the serious) is that they probably underestimate the stress levels of professors -- even tenured, university profs.  On the other hand, since CareerCast's "most stressful" jobs include military, police, firefighters, and event coordinators, I'm not going to argue against the point that university professors may have it comparatively easy.

Now, more seriously, is life working in academia stressful?  I think it's an important question;  to the extent that academia is more stressful than it should be, it may be damaging both to individuals, and to the overall success of scientific productivity on a larger scale.  On the other hand, perhaps the level of stress in academia is natural for various reasons, including the type of work involved, or the type of people involved, and is not really so bad either in relative or absolute terms.   

I don't know the answer to this question.  I could speak for myself (this is my blog, after all), but that's just more anecdote.  I poked around a little bit but didn't see anything especially informative in the research literature I saw;  I'd be happy to have pointers suggested.  Also, it's a problematic question, for several reasons, as there are all sorts of underlying questions to answer first.

1)  Stressful compared to what?  What are the right comparisons?  I tend to think the comparisons should be with other professional jobs (doctor, lawyer, businessperson -- and, for CS, I guess the appropriate "software engineer" type title), which seem to me to pretty stressful employment options in their own right. 

2)  Stressful at what time in one's career?  I think there are different stressors, and different amounts of stress, at different career points.  Grad student stress is not the same as assistant faculty stress is not the same as tenured faculty stress.

3)  How would one measure "stress", anyway?  CareerCast gives some information on its criteria which leads to university professor being (one of) the least stressful jobs.  Daniel Lemire offers the week-end-freedom test for how free you are (which may be one way of checking stress), but I don't agree with his assumptions. 

4)  And how might one account for various selection effects?  Maybe academics are more generally "Type A personalities".  Perhaps the right questions are not why academics are stressed, but why does academia attract so many Type A personalities, and/or does academia reward Type A personality-types in ways that are detrimental.

5)  Are Computer Science/Engineering in academia different in terms of stress than other academic fields, since these are the areas I care most about?  (Ostensibly, for instance, we get paid higher salaries, and have ample opportunities for outside-university work.  Both of these could affect stress levels.)

I'm sure you can come up with more issues that complicate the basic question.

I may do some more posts on this basic theme;  I do think the topic is important, but there's little hard information.  Seeing as how there's lots of psychologists hanging around universities, I'm surprised that I didn't quickly find one or more recent comparative studies on stress levels, personality types, etc. for academics, but perhaps I just need to look harder.  (If only I had the time!) 

To be clear, my bias is that when I read blog posts from my respected colleagues that portray academic life as some sort of competitive pressure-cooker where everyone is out to increase their ranking and are working 80+ hour weeks without any sort of social life, that's just not the reality I am aware of.  (Including, I think, for the people who actually write these posts, who generally seem to be talking about "other people".) 

To cut off some potential responses, I'm not blind, nor stupid;  there are plenty of stresses in academia, in particular having to do with the employment situation, where the number of jobs is not sufficient for the number of potential job-seekers generated.  And I would be interested in finding useful ways to understanding stress in the field and how to reduce it productively, especially for graduate students.  But to do this, we would need to move beyond individual anecdotes, gain some more data-driven understanding of what's going on, and start determining best practices.  The mythologies about academic life and stress do not seem helpful in understanding where there are problems and how to address them.  

CS 50 Fair (Live)

The madness that is the CS50 Fair at Harvard is going on now.  Hundreds of students demo-ing their final projects.  If you can't be there, you can watch the live stream.  I did a brief stop-by this morning and saw some fun and useful stuff -- one student showed me a simple setup for students to ask questions online in class and have other students up-vote them so the prof can see popular questions.  (There are tools that do this, sure, but it would be nice to have a simple one-off easy-to-use code setup to do this on the fly.  Hey -- student -- if you're reading this, come see me, I want your code. )  Another had a nice interface that gathered information on all the various Harvard events from different websites and pulled them together with some basic search functionality.  I'll have to talk with David Malan about how we're doing transitioning some of these useful prototypes into tools for us or around campus.  Still amazing what energetic CS students can do after an introductory class.  And hopefully I'll go back and see another shift of projects later this afternoon.

Yet More Good News, Harry Lewis Edition

As mentioned previously, our current Dean for the School of Engineering and Applied Sciences, Cherry Murray, will be stepping down at the end of the year.

The good news out today is that Professor Harry Lewis will be stepping up to serve as the Interim Dean.  To those in the outside world, you may know Harry for his blog, his books (CS books like Elements of the Theory of Computation (2nd Edition) and Data Structures and Their Algorithms, or more popular books like Excellence Without a Soul: Does Liberal Education Have a Future?, Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion, and Baseball As A Second Language), or his time as the Dean of Harvard College. 

For those of us who have been students (or professors, or both) at Harvard, we know Harry as a mentor, a guide, a wise man to come to for advice, and an inspiration.  (Both Salil and I frequently mention Harry Lewis and CS 121 at Harvard as reasons why we ended up as computer scientists.)

We are very fortunate that Harry stepped up to take on this important role, and his work will let SEAS -- and CS at Harvard -- continue to flourish.  As Harry says in the Crimson article above, "“The future of engineering at Harvard has never looked brighter than it does today."  And as FAS Dean Michael Smith says, “He brings to the deanship a thorough understanding of SEAS culture and academic life, exceptional insight into the undergraduate experience as a former dean of Harvard College, and the intellectual and administrative agility needed to effectively guide SEAS during this interim period.”

More Good News, Eddie Kohler Edition

Continuing the good news at Harvard, word has been given that Eddie Kohler has officially been offered tenure.  So we hope/expect/are excited about keeping Eddie here for decades to come.  

Eddie's contributions to computer science are well known -- he recently won the SIGOPS Mark Weiser award --  but perhaps less well known and appreciated are his contributions here at Harvard.  I can't imagine how we were surviving before he got here; he enriches the place constantly through teaching, tools, insights, questions, and countless other ways.  It's great news for us here at Harvard. 

Congratulations to Eddie. 

The News Is Out

Harvard Computer Science was given a sizable gift from Steve Ballmer;  we're excited at the opportunity to grow this gift will provide us over the next several years.  For more news, see the Crimson article, the Boston Globe article, the New York Times blog writeup, etc. 

Veterans Day

Veterans Day is a federal holiday, but, at Harvard classes go on.  This year, the holiday is observed for staff, but we'll be teaching.

I can't easily find out when the practice of having classes on Veterans Day became standard.  I found this Crimson article from 2004, but it makes it sound like holding classes (it seems to just mention sections, not actual lectures) was not official policy.  I also am not sure when this dichotomy of the day being a staff holiday, but classes are held, started.  I'm a bit embarrassed to say I haven't noticed this scheduling issue until this year, so perhaps the changes are new.

I understand that, from a teaching and scheduling standpoint, it's a bit annoying with the holidays messing up the teaching schedule.  It's also annoying when your children are out of school for the day for a federal holiday while you have to teach.  Also, it seems a bit odd, if not somewhat unpatriotic, "cancelling" Veterans Day for the students (and faculty), although I know that most people generally do not engage in veteran-specific activities for the holiday.  (That's true of our family, and my wife is a veteran.)    

I suppose I might not really have thought too much about it, except that somehow I noticed that Columbus Day is a university holiday at Harvard, and, because I'm sure most readers do not get enough John Oliver in their diet, here what his show has to say about that.  

Happy Veterans Day.

Weekend Links (November 1 Edition)

A variety of links on related news.

Ebola #1 (local):  The HackEbola with Data website gives detail for the upcoming Harvard Hacking event in conjunction with Statistics without Borders.  If doing some data mining for a cause is your thing, please check it out.  (No, you don't have to be associated with Harvard to participate...)

Ebola #2:  New Yorker magazine has an article out on "The Ebola Wars" that among other things, describes the work done by Harvard colleague Pardis Sabeti and her lab. 

Ranking again (no, not again!):  This one is tells the story of King Abdulaziz University and the US News and World Report Rankings.  (I note, as follow up from a few years ago, that I remain disturbed that nobody is offering to pay me large sums just to have me affiliated with them for the purposes of raising their citation count.)

Crimson #1:  If you're into this sort of thing, the umpteenth "Stanford vs. Harvard" article.  (Yawn.)

Crimson #2:  Anyone know of a good Dean who might be available?  

Yale:  My take on how you grow a department:  keep telling people you are going to/need to grow the department, and why.  Lather, rinse, repeat.  I hope this article is just the start. 

Rankings Everywhere

Like many (theoretical) computer scientists, I spent far, far too much time this weekend thinking about rankings.  Well, really, it was more that I was being far, far too amused by the various posts and comments on the novel ranking site "Ranking of CS Departments based on the Number of Papers in Theoretical Computer Science",  which led to posts at the Computational Complexity blog and in theory, the first of which shut down the comments rather quickly, and the second of which is at this time nearing the amazing 100 comment line.  (Luca's post deserves it -- it was the funniest thing I've seen all week.  Kudos.) 

Now, to fan these flames to further untold heights, I was informed that new US News and World Report Computer Science Rankings are out.  Needless to say, I disagree with them.  How exactly can Harvard be second to MIT?  Ridiculous.

(For those who are concerned about such things, the methodology is also given, though I haven't checked to see what parts of it are reproducible.  And what is that "Web Of Science" thing?  Is it as good as the citation tools in Google Scholar?)

For the ultimate in ranking tongue-in-cheek-iness, and for those who haven't seen it, I also recommend the NRC Deranker, which will (eventually) provide you the ranking you personally agree most with. 

Welcome, Attorneys!

You might wonder why I am welcoming attorneys to the blog.  Well, I happen to know that some attorneys read my blog.  I know this because recently, as an expert witness, while I was testifying in court, the attorney on the other side during my cross-examination specifically asked me about my blog.  Based on their questions, I am reasonably sure they had downloaded all the posts.  I imagine some poor associate attorney low on the totem pole had to read through it all to see if they could find anything embarrassing they could use in the context of the case. 

I don't think it was successful.  But who knows.  At one point, the attorney cross-examining me asked if one of the reasons I liked to do consulting work was because it pays well.  I answered, "I would say that's one of the reasons."  That wasn't a hard answer to give;  it's an honest answer.  But afterward I recalled that, years ago, I had talked about consulting on my blog.  I looked it up, and sure enough, here is what I wrote years ago:

I enjoy consulting, for several reasons:

1. It fulfills a need to be more directly relevant to the real world.
2. It gives me a chance to work with different sets of people.
3. It allows me to learn new things and exercise skills that I don't necessarily use as a professor.
4. It pays well.

Based on my experience as a witness, I am of very high certainty that the attorney had this post in front of him when he asked the question.  Of course, when he asked the question, he failed to note the other reasons I had given for consulting, or provide me the blog post for context.  But my assumption is that they were simply looking for a "gotcha" moment.  Perhaps the question and my response made me look bad to the jury.  (After subsequent clarifying questions on the issue from the client's attorney, I would like to believe it had no effect.)  I imagine that they were hoping that I would say that the pay wasn't important, in which case I am sure they would have readily put up the post from my blog to show the jury to try to discredit me.   

I talk very little about my legal consulting on the blog or publicly.  The main reason, obviously, is out of respect for and professional obligation to my clients.  But I find I don't blog about it even in very general terms, where confidentiality or other similar issues would not come into play.  And one good reason not to is that an attorney could use anything I write on the subject to try to impeach my credibility as a witness, even if it is out of context. 

Of course, as this example shows, anything I post online can potentially later be used against me in a case or in court.  Or in other situations.  These issues regarding our permanent digital identity, and how modern technology allows our past to easily be brought up and used against us, are not new;  I'm not suggesting I'm offering novel insight here.  Really, I'm just relaying an instance where the issue of my digital identity, in the context of this blog, hit me head on.  Certainly when I wrote that post years ago about consulting I did not think it would come up later in this way.  Mostly it makes me wonder how my children, who are busy exploring their own identities (digital and otherwise), will manage in a world where most of their history will be available online, for people to use or misuse in ways that I could not imagine.     

Harvard Junior Faculty Job Search

Harvard Computer Science is doing a junior faculty search this year.  We pretty much have been doing one every year, but it's nice to be able to make an announcement and point people to the ad.

So here is the ad, telling you what you need so send in if you're applying. 

Also as usual, we're looking in all areas, because we're always interested in great people.  However, in the interest of full disclosure, the focus this year is described as

This is a broad faculty search and we welcome outstanding applicants in all areas of computer science, including applicants whose research and interests connect to such areas as engineering, health and medicine, or the social sciences. Of particular interest are candidates with a focus on systems and data science, including operating systems, networking, software engineering, data storage and management, and computational science.

We'll look forward to your application.

Cuckoo Filters

An upcoming paper appearing at CoNext will be of interest to any Bloom Filter user or aficionado:

Cuckoo Filter:  Practically Better than Bloom
(Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher)

Let me describe a cuckoo filter and some of what's in the paper for you.  If you want to avoid a technical discussion, all you need to know is that for reasonably large sized sets, for the same false positive rate as a corresponding Bloom filter, cuckoo filters use less space than Bloom filters, are faster on lookups (but slower on insertions/to construct), and amazingly also allow deletions of keys (which Bloom filters cannot do).  If you want to look at code, there's even a github repository for you with code for cuckoo filters. 

Note:  I'll assume you probably know what a Bloom filter is in the discussion that follows.  As a reminder, it's a hash-based data structure for set membership that can give false positives;  by allowing false positives, you can save space in your representation of the set.  I'll assume you probably know what cuckoo hashing is.  As a reminder, in cuckoo hashing, you have buckets that can contain a fixed number of keys, and each key gets some number d of buckets (obtained by getting d values from hashing the key) where it can be placed.  When you insert a new key, if all of its buckets are full, you can move keys out of that bucket to one of its other buckets to make room.  Since apparently there are drinking games that exist based on taking a drink whenever I use the word "Bloom filter" or "cuckoo hashing" in a talk, I imagine most readers of the blog know about these things.  (Or, always, Wikipedia.)

The framework used in the paper comes from the following idea.  One way of implementing Bloom filter functionality when given a static set of items is to use a perfect hash function;  that is, as hash function that maps the n elements of your set into an array of size n in a 1-1 fashion.  Then, you use another hash function to store a fingerprint of the element instead of the element itself in the array location.  To do a set membership test on an element z, you hash z once to find its location in the array, and hash z again to find its fingerprint, and check against the fingerprint in the array location.  For elements not in the set, you get a false positive rate of 2^{# of fingerprint bits}.

The problem is that the perfect hashing framework doesn't allow you to insert new items naturally.  Or do deletions (but standard Bloom filters don't allow deletions also -- you need a counting Bloom filter for that).  So a natural thing to do is to think of using some other sort of hash table, besides a perfect hash table, and see what happens.  This idea was explored way back in for instance some papers I worked on in 2006 (here and here) using "d-left" hash tables, which are based on a multiple choice hashing scheme.

If you're going to use multiple choice hashing schemes, though, you should think about using cuckoo hashing.  The ability to move keys around means you should get better space utilization;  for example, even with 2 choices, if your buckets can hold 4 items, cuckoo hashing can get you about 95% space utilization.  The problem with cuckoo hashing in this setting is that, for a Bloom filter, you want to just keep fingerprints of keys, not the keys themselves.  So, when you want to move the key, how do you figure out where to move it to -- you no longer have the key to hash?

The approach used in the paper is a trick called partial-key cuckoo hashing.  To get two buckets for our key, we do a hash to get the first bucket (idealized to be uniformly at random), but to get the second bucket, we do not hash the key, but just the fingerprint of the key;  we XOR that value with the value for the first bucket to get the second.  The upside of this approach is given a bucket and a fingerprint in the bucket we can find the other bucket corresponding to the fingerprint.  (XORing the hash of the fingerprint works if the fingerprint is in the first bucket or the second, as is easily checked.)  The downside is if our fingerprint has F bits, that means our second bucket is really only chosen from 2^F possibilities;  it is not uniform conditioned on the first.

Because of this limitation, one interesting aspect of the paper is that we show, in theory, this approach just will not work.  Specifically, there is an Omega(log n) lower bound on the size of the fingerprint that must be stored; this means the cuckoo filter is super-linear in space, unlike standard Bloom filters which are linear in space.  This lower bound is easy to derive.  Suppose that you have buckets that can hold b keys.  If 2b+1 keys have the same pair of buckets, then there is trouble;  you can't fit 2b+1 keys into 2b bucket slots.  So the question is whether there are collections of 2b+1 keys that have the same pair of buckets.  With standard cuckoo hashing, this would be a low probability event.  With partial-key cuckoo hashing, the probability depends on the size of the fingerprint, since this determines how many possible second choices of a bucket there are for each key (given their first random choice of a bucket).  If you have too few choices, you will get too many collisions, or too many keys in a pair of buckets.  Some straightforward calculations yield the Omega(log n) lower bound on the size of the fingerprint.

So now that we've proven theoretically that this won't work, how could it work in practice?  If you go back to those calculations, you find that the lower bound has some nice constant factors.  The bounds you get on the fingerprint size are actually (roughly speaking) log n/(2b).  That constant factor in the denominator, even when b=4, covers a large range of n.  In practice, fingerprints can be quite a reasonable size, and still avoid the potential bottleneck of too large a group of keys all hashing to the same small number of buckets. 

In any case, this may be the first paper I've written that contains a proof that the described data structure fails in theory but works in practice.  (The other way around I generally find much easier.) 

Big open theoretical question:  try to analyze why partial-key cuckoo hashing gets roughly the same load threshold as regular cuckoo hashing.  (Anyone want to work on that?  Let me know...)

This post is long enough;  there's a lot more in the paper, including comparisons with other schemes, bit-saving tricks, and lots of performance results.  Have a look.  

Postscript/Tangent:  In a recent review (for a different paper, with a different theme) one reviewer made the following comment/criticism:  "Despite years of research, no one has found a variant of cuckoo hashing that can outperform simpler methods in realistic situations."  To which I say, hunh?  Yes, I understand linear probing is wonderful in practice due to cache effects and block sizes and in many and perhaps even most situations can yield better performance than cuckoo hash tables.  But certainly not everywhere.  Cuckoo hash tables certainly seem at least potentially better for many hardware settings, and for at least some important applications -- such as this one -- cuckoo hashing seems to be a clear win.  (The issue here is the number of fingerprints you have to deal with on a lookup affects the false positive probability -- so even if linear probing lookups are "faster" due to cache effects and block sizes, if you try to get this sort of space utilization you get larger contiguous blocks which increase your false positives.)

My co-author David Andersen also violently disagrees with this review comment, and points to these recent papers at NSDI and Eurosys.  

Perhaps I'm missing something, but my thought was this was a sign of a bad review (both in content, and in its overall rudeness).  I felt obliged to try to correct the record (and I can only hope the reviewer sees this post).     
 

Andreessen-Horowitz Again

Andreessen Horowitz had a second Academic Roundtable, gathering together academics, VCs, and people in startups to talk for a few days about a variety of topics.  I wasn't sure why I was invited the first time (which I wrote about last year), and am even less clear on why I was invited back, but I again had a very good time. 

Before a few words about the talks, the high order point:  I'm told that most/all of the talks will be put online over the coming weeks.  So if you're interested, you can experience them yourself.  I think it's great that they're doing that this year;  if you like the talks, you should tell them, so they keep doing it.  (If they don't have comments there, you can always comment here.)  Sadly, they don't seem to be up yet, but I'll post the links when they become available. 

Highlights would include a discussion of Bitcoin -- interesting to hear what Ed Felten, well-known Princeton professor and now ex-Chief Technologist of the FTC, thinks about the Bitcoin economy.  Dawn Song of Berkeley gave a general talk on security issues of the present and future, while Dan Boneh of Stanford gave a talk on the power of program obfuscation.  Raj Rajikumar of CMU gave some history and some peeks into the future of driverless cars -- it's not just Google, you know.  Tuomas Sandholm of CMU talked about his take on the starting of startups while still being an academic (based on now-multiple experiences), and Josh Bloom of UC Berkeley (and wise.io) described the differences between writing papers about machine learning and building products using machine learning.

Of course, some heated discussion about the variety of issues that arise between academic work and transfer of technology to startups inevitably ensued.  (Maybe that's why I get invited.)  The key idea repeated by many (on both sides of the fence) in various forms was that businesses (and in particular startups) are very busy going down their road of development and product, and they may see many things out the sides of that road that are very interesting, but don't have time to explore off the road.  Academics are interested in things way off the road, often thinking of issues much further out in time-scale.  And (at least in my opinion) the role academics play is a good thing;  there (obviously) remains a lot of ways the two worlds can interact and cooperate. 

On Academia vs. Industry.... MSR SVC Closing

I'm one of those professor types that ends up defending the joys of life as an academic versus a career in industry -- some of you who read this blog have probably seen me comment at Matt Welsh's blog or Daniel Lemire's blog/Google+ chain.  And to be clear I'm not anti-industry, I just want to make sure there's a fair discussion.

In that vein, I'm sad to hear that Microsoft Research Silicon Valley will be closing, as described in this article.  I know many people at MSRSV, and have visited there often.  It's a loss to the community to have it close.  I have sympathy for those who work there -- this must be stressful -- but this sympathy is happily diminished because I know the people there are so talented, they will quickly move on to other employment.  (When Digital Systems Research Center closed long ago, a number of the people I worked with in the lab just moved on to some small company that seemed to be just starting to really get going, called Google.  I wonder how it worked out for them.) 

After a moment of silence for the lab, I do feel it necessary to point out that this is one of the "issues" in the academia vs industry life choice.  The life cycle for companies moves rapidly.  That's not a bad thing, but it's a thing.  Disruptions like this are a non-trivial risk in industry, much less so in academia.  (Just look at the history of research labs.)  Again, I'm sure it will work out for the people at MSRSV, but any life shift like this -- even if it ends positively -- is stressful.  Without wanting to overstate the consequences, it's worth pointing out.

Simultaneous Enrollment

The Crimson has an op-ed on simultaneous enrollment, that I agree with.

Harvard does not like simultaneous enrollment, which means a student taking two classes that meet at the same time -- any time overlap counts (whether the whole class or half an hour once a week).  If you want to take a class via simultaneous enrollment, you have to petition the Administrative Board, and your professor is supposed to provide direct hour-per-hour instruction for the class you can't intend.  As a previous Crimson article states:

The Faculty Handbook requires that “direct and personal compensatory instruction” for simultaneous enrollment, but only recently has the Ad Board refused to recognize videotaped lectures as a stand-in for class time.

The article references that for the past several years the Ad Board has accepted recorded lectures, under some additional conditions, as a suitable proxy for the direct and personal compensatory instruction.  This apparently represented a change from their past position, and this last year, while I was on sabbatical, some Standing Committee on Education Policy decided to push back and say no more recorded substitutions. 

(An aside:  I don't know why they used the dated term "videotaped".  My lectures have been recorded and made available online;  these days, I'm not sure any "videotape" is actually involved in the process.)  

I believe I had a great deal to do with the Ad Board accepting recorded lectures the last several years.  My undergraduate class, CS 124, was recorded with very high quality production for the Harvard Extension School, and I made this video available to the students.  Some years ago, students starting approaching me wanting to do simultaneous enrollment for CS 124, and I thought it was fine, because of the availability of class lectures.  (That was, for instance, how the Extension students were taking the class.)  In particular, every year some number of students seemed to want to take CS 124 and a conflicting math class that overlapped, which made it very difficult for a small number of students who wanted to pursue both CS theory and mathematics.  (Both classes were "gateways" to more advanced classes;  at least for me, changing my class time would have just introduced other more challenging time conflicts;  neither class appeared poised to change times.)  But other class overlaps came up as well. 

I initially faced some opposition from the Ad Board when I supported the students' petitions for simultaneous enrollment because I suggested the recorded lectures were a suitable proxy.  They objected, and I objected to their objection.  After some back and forth, we found language which we managed to agree met the language of the faculty rules, with the outcome being the students could, in the end, rely on the recordings of class lectures.  I admit, I believe it helped that I had served on the Ad Board, and had a good working relationship with them, so they were willing to work with me to come to a mutually acceptable solution.  The framework we established was later used for CS 50 and other computer science classes, because I passed on my successful approach with the Ad Board to others.  (David Malan asked me for assistance on the issue, for example.)  There was, however, always some tension, with the Ad Board continuously questioning whether using class recordings to justify simultaneous enrollment was suitable.  Meanwhile, the number of such petitions kept growing. 

Apparently, while I was sabbaticalling, various powers that be have acted to tighten the rules for simultaneous enrollment, and disallow my previous framework.  Interestingly, CS 50 -- the class with the most requests for simultaneous enrollment -- seems to have acquired a blanket exception, which I am happy for, but still leaves the rest of us facing unhappy students who often have to deal with ugly situations.

What I find frustrating is that, to my knowledge, this change is not based on any data about student performance, or any understanding of student behavior.  It's based on a presumption that students are supposed to sit in classes to learn.  David Malan has some great data showing this presumption doesn't seem to have a basis in reality.  Students in CS50 taking the class under simultaneous enrollment don't do any worse than other students.  In fact, if I recall the data right, they do better than average;  this would not be surprising, as they are a self-selected group with apparently high interest in the subject.  David also has great data showing how lecture attendance steadily drops over the semester.  If a substantial fraction of the students are missing class and watching the video anyway, what's the point of blocking simultaneous enrollment?  Maybe because of all this data at David's command CS 50 got its exemption, but I'm sure if we go back we'd find similar findings for CS 124 and other classes.   

Professors have always had the right to refuse simultaneous enrollment petitions for their class, so if the professor expects student attendance, there is no problem.  I don't think it's a radical suggestion to say that for recorded classes, professors and students should have the ability to jointly decide if simultaneous enrollment is a suitable solution to the small number of inevitable class scheduling conflicts.  I'm not sure what combination of faculty and administrative busybodies decided they had to fix what I see as a non-problem, but I'm sure their rule-making (or in this case rule-interpreting), while it only affect a small number of students, will be a significant net negative.  Kudos to the Crimson for pointing out that this is a poor decision, and I only wish I was optimistic that it could be quickly reversed.  

Biggering

Preliminary course enrollment numbers are in.  Our new theory course, CS 125 (rapid introduction to theory), has 32 undergrads and 5 others, for an enrollment of 37.  Salil and I had predicted and desired in the 20-40 range for the first year of this course, so we're on target.  We hadn't thought about CS 125 being a class for grad students, but it actually makes sense.  Entering CS grad students who haven't had background in theory, or grad students from other related areas (statistics, mathematics, etc.) who want a fast-paced introduction to the basics of CS theory, would both fit in well for this class.  Maybe next year we'll even advertise it for grad students as well.

Our mainstream required-for-majors theory course, CS 121 (the "here's Turing machines and undecidability and NP-completeness" course), has an enrollment of just over 150, the largest it's ever been.  Given that CS 125 was supposed to draw some students from 121, that's even more amazing.  

And the standard CS introductory course, CS 50, has over 800 undergraduates (and over 850 total) signed up, making it now the largest class at Harvard.  This was so noteworthy that the Crimson had an article this morning about it.  As usual, you can find a great quote from Harry Lewis: 

“Harvard students are smart people,” said Harry R. Lewis ’68, former dean of the College and current director of undergraduate studies for Computer Science. “They have figured out that in pretty much every area of study, computational methods and computational thinking are going to be important to the future.”

So the growth continues, at least for another year.

You Can Rename My Family for.....

An interesting article in today's Crimson about the background to the announcement that Harvard's School of Public Health will be re-named the Harvard T. H. Chan School of Public Health, for a $350 million donation.  Feel free to comment on your feelings regarding the issue.  (The Kennedy School of Government notwithstanding, Harvard schools have not been "named" via donations historically, although certainly buildings and such have.)  I'm not publicly taking sides -- indeed, it seems like a wonderful debate challenge to figure out arguments on both sides of the issue as to whether naming schools in this way is a good or bad idea.  Even if you think it's a good idea, you might wonder about the price tag...

In particular, I can't help but wonder what the naming rights of the School of Engineering and Applied Sciences could go for?  In the course of our capital campaign, will I have the chance to find out?  Maybe we could get a bidding war going?  How much would SEAS have to get for me to feel good about having "Harvard's XXXX School of Engineering and Applied Sciences" on my letterhead for some appropriate name XXXX? 

At a baser level, Mitzenmacher has always been a problematic name.  Too long.  (On so many standardized forms, I end up as Michae Mitzenmache....)  Maybe I should offer myself up for naming rights.  Sadly, I don't think I'd get $350 million.  

Teaching Sorting

For many years now, while teaching the introductory Algorithms and Data Structures, I have told students that we won't be starting with (or really covering) sorting and searching, because it's boring.  While that description is an exaggeration (the students see mergesort [an example of divide and conquer] and heapsort [heaps are important as an implementation of priority queues for Dijkstra's algorithm]), I've never thought that staring this class with a long unit on sorting/searching algorithms, which most textbooks like to start with, is the best use of time.

So it was a bit odd to find myself for our new "honors course", CS 125, spending the first day-and-a-half or so on sorting algorithms.  The key was that there was the right motivation for it.  We'll be tackling both algorithms/data structures and complexity, and the theme of how to model computation will play a big role throughout the course.  When we thought about what was the right way to introduce the class, and in particular this theme, sorting seemed like the right choice.

After very quickly refreshing the students on some basic comparison sorts (bubblesort and mergesort), we present the standard lower bound argument for comparison-based sorts.  But then we show how this lower bound can be broken, by assumptions about the data that allow one to go beyond comparisons to other operations.  Specifically, we raced through counting sort, bucket sort (for random data), and sorting via van Emde Boas trees.    (The students in particular seemed to be talking through the details of van Emde Boas trees at the class break, which I'd like to think because they were new and interesting, but possibly was due to the fact that it was the first time I'd ever presented them, and maybe my delivery for that topic needs some tuning.) 

Lo and behold, I find myself finding sorting interesting!  We didn't even get to more advanced interesting possibilities, like data-oblivious sorting or "bleeding edge" parallel sorting.  I feel I need to apologize to sorting, for mistakenly suggesting that it's a boring topic.  I still wouldn't want to start an algorithms/data structures class with multiple weeks of sorting and searching algorithms, but sorting is a natural way to introduce some key concepts in algorithms, and there's fun to be had in the large variety of approaches to sorting.