Tuesday, June 22, 2004

A man, a plan, a pointless (?) program

As the Google engineering department's director of search quality, I (along with my team) am responsible for maintaining the ranking technology that decides what order your results show up in when you do a Google search. It's an important job and an exciting one. I can't tell you all the secrets of what my group does, but I can tell you a non-Google story that will give you a taste of what it's like to work with large amounts of text data and computing resources.



On the last palindromic date, 20:02 02/20 2002, I was, like any good computer geek, reminded of the palindrome that appears on page 170 of the computer manual Common Lisp, the Language (2nd ed):

A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal -- Panama!

A quick search reminded me that the record for such a palindrome, established in 1984 by Dan Hoey, was only 543 words. I immediately thought I could (and therefore should) write a program to beat that. I wrote an algorithm that searches a dictionary and figured out how to put the words together in a sentence that starts with "A man, a plan" and ends with "a canal, Panama." It took me until 1:00 a.m. that night of 02/20 (and some minor bug-bashing the next day) to produce this result -- to my knowledge, still the longest palindromic sentence ever created.

So what, you may ask? Good question. I readily admit that my accomplishment has no practical social purpose or business application. But as a story that spans 18 years from Hoey's palindrome to mine, it has a moral about how it is becoming easier to do big things. Hoey is an excellent computer scientist, but he said he spent days writing a disk-based B-tree package for his program. I was saved all this, because a dictionary now fits in main memory and I could use straightforward binary search. Thank you, Moore's Law.

Also, I was saved from having to fiddle with the dictionary because of the public domain Moby Dictionary. Thank you, Internet (and Grady Ward). The advances over the years let me combine a 100,000-word dictionary and a year-old laptop to break an 18-year old record. If you're a programmer, you could do it too: beat my record, or invent something new -- for example, can you invent a double-entendre law firm that is longer than Dewey, Cheatham, and Howe? With the resources available to you, you can accomplish a lot. Let me know what you come up with.

Now if you'll excuse me, I have to get back to work -- I have some ideas that can only be tackled with a few terabytes of text and a few thousand computers.

-- Peter Norvig
director of search quality

Friday, June 18, 2004

Cycling for life

It was hot. It was hilly. It was seven days long. But our two-person Team Google prevailed last week, cycling over 600 miles of hills and coastline to raise money for AIDS research and services. John Barabino and I joined more than 1,200 other cyclists for the grueling-but-exhilarating trip down the California coast - from San Francisco to Los Angeles - for AIDS LifeCycle 3. We were thrilled to be part of the effort to raise $5+ million dollars for the San Francisco AIDS Foundation and the Los Angeles Gay and Lesbian Center, both of which provide extensive services to people with AIDS.

We couldn't ride 600 miles as Team Google without a bit of corporate pride, and our Google cycling jerseys became such hot commodities that we wound up giving them out to other riders.

The event was so satisfying that I've decided to do it again next year. With luck, more Googlers will join Team Google. But even better would be not having to ride for this epidemic, because we will have eliminated it.

Daniel Lemin
Corporate Communications

Friday, June 11, 2004

Yoshka's weekend amble

When I first started at Google, my main job was to lie in the courtyard and wait for the UPS man. My dad and I were pretty much the only ones who showed up before 11AM, so we became the de facto receptionists for a while. I'm always very nice to visitors.

When we moved to Mountain View in the summer of 1999, I switched to full-time. I interviewed a lot of people, but no dogs. Fewer of them were online back then, though of course it's hard to tell sometimes. Eventually, I returned to part-time consulting and spent a lot of time watching ducks in a pond near our office. Fascinating, but ultimately unfulfilling.

Now my office is on the third floor. I take the elevator these days, since I injured my right leg last year. There are more dogs at Google now, but many of them are very small, like King Charles Spaniels. And Yorkies. When dad parks me outside the Google cafe, I love getting attention from all the passers-by. They even know my name! And there's barbecue on the patio every day during the summer. Life is good.

Yoshka, Google's Top Dog

Tuesday, June 08, 2004

Oodles of doodles

One of the things I like best about Google is that we're the kind of company that, when a user writes in to suggest that we honor the once-every-122-years Transit of Venus on our home page, we actually do it!



My name is Dennis, and I'm the guy who draws the Google doodles. But the doodle tradition started here before I did. The first doodle was produced by (who else?) Larry and Sergey, who, when they attended the Burning Man festival in summer 1998, put a little stick figure on the home page logo in case the site crashed and someone wanted to know why nobody was answering the phone. By the time I began an internship here in the summer of 2000, the company was producing doodles on a regular basis. At the time I was a Stanford undergrad majoring in art and computer science, and, although I hadn't been hired to do anything remotely related to logo design, I eventually stumbled into my first doodle gig (Bastille Day, July 2000, for which I did a fairly boring flag motif).

And I've done all the doodles ever since; I've produced almost 150 by now. The doodles are only a small part of my actual job (as Google's international webmaster, I'm responsible for managing all our international site content, which keeps me plenty busy), but it's definitely my favorite. Holding up my mockups and then holding my breath while Larry and Sergey do their "thumbs-up, thumbs-down" emperor thing is never boring, and I love the fact that my little niche within this company turned out to be something so cool and creative and, well, Google-y.

What doodles will I be doing next? Well, telling you in advance would spoil the fun of it, and I have no idea anyway. If you've got any ideas of your own, feel free post them in the Web Search Help Forum. Who knows; you may just make a little Google history yourself.

-- Dennis Hwang

Update August 2009: Contact information updated; date and link corrected for first doodle.

Monday, June 07, 2004

It's not rocket science (or maybe it is)

"Though women represent nearly half the U.S labor force and more then half of all undergraduates, just 18% of scientists and engineers employed in industry are women and only about 20% of students graduating with majors in engineering, physics, computer science, and similar fields are women." This may not be surprising news, and that's a problem. But the Anita Borg Institute for Women and Technology is working on a host of programs that can change these numbers.

Google participates with the Institute to recognize outstanding women students in computer science and technology through the Google Anita Borg Memorial Scholarships. The Institute has just announced the 2004 winners: eight women who have each won $10,000 scholarships, and 11 more honorees who receive $1,000 scholarships.

We salute the winners. May all their successes inspire lots of other women and girls to pursue their (technical) dreams.

Breda Murphy