Filling out your bracket

If you're a gear head like me, March Madness is statistics nirvana. When it comes to filling out your bracket, you have so many choices!

• You can get all scientific at places like Bracketscience.com, or plug in numbers from a well-known ranking like Jeff Sagarin's ratings at USA Today, or the Rating Percentage Index ratings.


• Or you can try to harvest the wisdom of crowds, and use the law of big numbers at a site like ESPN's National Bracket. Wow! The country thinks Cal is just going to get stuffed! If you do this, note these good bits of advice about how you might get a good result, just not good enough.


• Or you can try to work your way through the bracket carefully, using lots of heuristics like who's the better coach, or who has a better back court, or who excels at the 3-point game


• And, of course, you can take the President's bracket; he knows a lot more about basketball than me!

Or you can take Raymond Chen's approach, which is, if nothing else, always both amusing and educational.

Arrival of the Waesche

It appears that the USCSC Waesche has now arrived in Alameda. The Waesche is a National Security Cutter, the second one of a planned eight. It is "the flagship of the U.S. Coast Guard’s fleet"!

As described by the Coast Guard:

The National Security Cutter, for example, will enable the Coast Guard to screen and target vessels faster, more safely and reliably before they arrive in U.S. waters – to include conducting onboard verification through boardings and, if necessary, taking enforcement-control actions.

In addition to its well-known search-and-rescue and anti-terrorist missions, the Coast Guard is involved in issues of customs, immigration, and drug enforcement, and the new cutters will be part of all these efforts.

Here are a few web pages specifically devoted to the Waesche:

• http://www.uscgcwaesche.com/


• http://www.uscg.mil/pacarea/CGCWaesche/


• http://en.wikipedia.org/wiki/USCGC Waesche (WMSL-751)

Keep an eye out for the Waesche if you are anywhere around San Francisco Bay!

P.S. Anybody know how to pronounce Waesche? Would it be something like Way-Ski?

Updated: Gregor Rothfuss points me to this German-English dictionary entry, with audio. It sounds like the correct pronunciation is more like "Vay-Shuh" -- thanks Gregor!

The Data Deluge

The February 27th, 2010 issue of the Economist has an interesting special section:

Data, data everywhere: A special report on managing information

The special section contains about ten articles, looking at the subject from various angles. From the first article:

The world contains an unimaginably vast amount of digital information which is getting ever vaster ever more rapidly. This makes it possible to do many things that previously could not be done: spot business trends, prevent diseases, combat crime and so on. Managed well, the data can be used to unlock new sources of economic value, provide fresh insights into science and hold governments to account.

But they are also creating a host of new problems.

The companies and organizations which are working with this "big data" are the obvious ones: Google, IBM, Microsoft, Oracle, etc. Here's an example:

Wal-Mart's inventory-management system, called RetailLink, enables suppliers to see the exact number of their products on ever shelf of every store at that precise moment. The system shows the rate of sales by the hour, by the day, over the past year, and more. Begun in the 1990's, RetailLink gives suppliers a complete overview of when and how their products are selling, and with what other products in the shopping cart. This lets suppliers manage their stocks better.

The article gives a clever use of such data mining:

In 2004 Wal-Mart peered into its mammoth databases and noticed that before a hurricane struck, there was a run on flashlights and batteries, as might be expected; but also on Pop-Tarts, a sugary American breakfast snack. On reflection it is clear that the snack would be a handy thing to eat in a black-out, but the retailer would not have thought to stock up on it before a storm.

The articles touch on many of the problems in dealing with big data:

• Size/cost/time to process such enormous amounts of data


• False conclusions, confusing interpretation issues


• Security and privacy concerns


• Ownership issues


• Fair access to data


• Environmental issues

You might be surprised to see "Environmental issues" in the list.

Another concern is energy consumption. Processing huge amounts of data takes a lot of power. "In two to three years we will saturate the electric cables running into the building," says Alex Szalay at Johns Hopkins University. "The next challenge is how to do the same things as today, but with ten to 100 times less power."

Both Google and Microsoft have had to put some of their huge data centers next to hydroelectric plants to ensure access to enough energy at a reasonable price.

The articles also talk about many of the fascinating areas of technology being driven/created by these new big-data efforst:

• Cloud computing


• Query processing


• Statistical algorithms, such as
  
  
  
  • collaborative filtering
  
  
  • statistical spelling correction
  
  
  • statistical translation
  
  
  • Bayesian spam filtering
  
  
  • Predictive analytics
  
  


• Storage and networking advancements


• Data visualization


• Flash trading

It's a long list, and a lot of exciting areas.

As is often true with Economist special reports, the writing is fairly dry, and the presentation tends to provide a fairly high-level overview of a lot of related areas, without providing much in the way of resources for digging into those areas more deeply.

But overall it was intriguing and quite worth reading.

From cradle to cloud

In cloud computing, one of the big issues is how to transfer your data to the cloud. Various techniques are used, but here's, apparently, the current state of the art:

• Get a SATA drive


• Fill it with your fine data


• Put it in a mailing envelope and mail it to Amazon


• They'll load the data into your cloud for you!
  

The more things change, the more they stay the same.
As Andrew Tanenbaum wrote in his textbook on networking:

Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.

(Though I remember the quote more vividly from Jim Gray's work on data transfer for astronomers):

I’ve been working with a bunch of astronomers lately and we need to send around huge databases. I started writing my databases to disk and mailing the disks. At first, I was extremely cautious because everybody said I couldn’t do that—that the disks are too fragile. I started out by putting the disks in foam. After mailing about 20 of them, I tried just putting them in bubble wrap in a FedEx envelope. Well, so far so good.

SEDA

The last time I looked into web server architecture was six or seven years ago, when someone pointed me at Dan Kegel's C10K paper. I'm pleased to see that he tried for a while to keep that paper up to date, although it looks like it's been a few years since it was updated.

Recently, I followed some links and ended up at Matt Welsh's SEDA work. Welsh appears to have moved on to other projects, but the SEDA work remains live at SourceForge.

I read through the SOSP 2001 paper and enjoyed it; it's quite readable and well-written, and explains the basic principles clearly.

The primary focus of SEDA is on helping software developers build what Welsh calls "well-conditioned services":

The key property of a well-conditioned service is graceful degradation: as offered load exceeds capacity, the service maintains high throughput with a linear response-time penaly that impacts all clients equally, or at least predictably according to some service-specific policy. Note that this is not the typical Web experience; rather, as load increases, throughput decreases and response time increases dramatically, creating the impression that the service has crashed.

Modern network servers tend to use one of two basic programming techniques: thread-based concurrency, or event-driven programming. Welsh compares and contrasts the two models:

The most commonly used design for server applications is the thread-per-request model. ... In this model, each accepted request consumes a thread to process it, with synchronization operations protecting shared resources. The operaitng system overlaps computation and I/O by transparently switching among threads. ...
When each request is handled by a single thread, it is difficult to identify internal performance bottlenecks in order to perform tuning and load conditioning.

...

The scalability limits of threads have led many developers to eschew them almost entirely and employ an event-driven approach to managing concurrency. In this approach, a server consists of a small number of threads (typically one per CPU) that loop continuously, processing events of different types from a queue. ... Event-driven systems tend to be robust to load, with little degradation in throughput as offered load increases beyond saturation. ... The choice of an event scheduling algorithm is often tailored to the specific application, and introduction of new functionality may require the algorithm to be redesigned. Also, modularity is difficult to achieve, as the code implementing each state must be trusted not to block or consume a large number of resources that can stall the event-handling thread.

To overcome the problems of the two basic approaches, the SEDA work proposes a synthesis and unification:

The staged event-driven architecture (SEDA) ... decomposes an application into a network of stages separated by event queues and introduces the notion of dynamic resource controllers to allow applications to adjust dynamically to changing load.

...

A stage is a self-contained application component consisting of an event handler, an incoming event queue, and a thread pool. ... Each stage is managed by a controller that affects scheduling and thread allocation. ... Stage threads operate by pulling a batch of events off of the incoming event queue and invoking the application-supplied event handler. The event handler processes each batch of events, and dispatches zero or more events by enqueuing them on the event queues of other stages.

The paper goes on to work through many of the details, and to demonstrate a variety of different resource controller implementations, showing how the alternate controllers can provide elegant implementations of adaptive load shedding without forcing complexity into the system developer's core logic.

It's quite a nice presentation, and I liked the way it was all pulled together. I was intimately familiar with the basic techniques and approaches, but it was very helpful to see them pulled together and structured in this fashion.

If you're at all interested in how to build scalable and robust network services that perform reliably under extreme conditions, it's worth spending some time with this work.

Allocation

A good friend of mine is embarking on a new career at Google. Bravo! I think this will be a really exciting move for him; he's a special individual and I think he will do quite well. He's spent too much time working in organizations that wasted his talents, and it's past time for him to have an opportunity like this.

We happened to be talking the other night, and he was describing the process known as Allocation. As I understand it, it goes something like this:

• You interview at Google. You do well, you like Google, they like you, you have the right stuff, and they make you an offer.


• You accept.


• This process is being repeated, simultaneously, with dozens of other individuals (Google are now quite a large organization). So you become part of a pool of talent who are all entering Google at the same time.


• Every so often (monthly? bi-weekly?), Google convene the Allocation Review Board, comprised of some set of HR personnel, together with the hiring managers of various projects who have budget ("open reqs").


• The Allocation Review Board sit and study the available talent in this pool. Each project has a certain amount of "points" to spend; they discuss things somewhat, then they each "bid" on the incoming fresh meat.


• This information is then entered into a computer, possibly along with the results of a questionnaire you've completed about yourself. An algorithm then crunches the data, and performs the allocations.


• Your precise position, including your title, job description, chosen team/manager, and initial project(s), are now known, and you are informed.


• You show up for your new job!

When my friend described this process to me, I was aghast, horrified. It sounded paternalistic and demeaning; I am not a number! Is it just my age? Do all companies do this nowadays? Am I misunderstanding the process?

Has anyone been through this, and willing to share their experience? I'd love to learn more...

Data Compression

Here's an amazing web page which contains an entire book on the theory and practice of Data Compression. Very impressive!