Gregable.

Back from Kilimanjaro

2010-08-31T05:35:00.000-07:00

I'm a little late in writing this post, but better late than never. Two weeks ago, I got back from my trip to Tanzania where me and 3 buddies climbed Mt. Kilimanjaro. It was a great trip - a week on the mountain, 3 days of Safari, and a few rest days scattered between. I posted some photos to Picasa: Kilimanjaro Trip Pictures.

99% of the hikers climbing Kilimanjaro start at midnight from Barafu camp at around 15k ft altitude, hike to the top (19k ft) for sunrise, and then turn around and descend a few minutes later back to 10k ft altitude. Our group instead opted for the little known Crater Camp option. We started our hike from Barafu at 8am, daylight and much warmer. We ascended to Stella's Point on the Crater Rim, 500 ft lower and a 30 minute hike from the actual peak (Uhuru Peak) and then dropped down into the Crater for the night. The plan was to wake up and start hiking at a leisurely hour of 5am in the morning.

The crater was well worth the extra day, most of the hikers never set foot in it, but we had time to explore. I opted to check out the glacier inside the crater, which is shrinking and may soon be gone completely. Many of our porters had never done the Crater Camp option before, so they were just as excited as we were.

Unfortunately, after going to bed, the altitude kicked in for me. We were all already weak, but it really hit me hard. When our guides woke us up in the morning, I decided to descend instead of finishing the last few hundred feet to the top. Acute Mountain Sickness was an interesting experience - it felt like the worst flu you've ever had: headache, nausea, vomiting, and extremely low energy levels. I had to take a break between tying one boot and the other. I was wearing a heart rate monitor for the trip and my resting heart rate was around 120 beats per minute - normally, it's around 70. Fortunately, dropping altitude did the trick. A few hours later at a lower vantage point, I was feeling absolutely fine. The other 3 in our group finished the route to the top and joined me that afternoon.

Not too many meteors, but the stars were better than I've ever seen before. By day 2 we were camping above the clouds, so there was essentially no man-made light pollution except for our own flashlights. The milky way was not only bright and clear, but I swear that I could actually make out hints of different colors in the stars with my unaided eye. I tried but failed to take any photos worthy of sharing.

On the tail end of the trip, we went on a 3 day Safari. I have to admit that I was mostly on the trip for the hike and hadn't really researched the Safari much in advance, but it was also a blast. Nice and relaxing, and crazy amounts of wildlife as you'll see in the photos.

Kilimanjaro: Wish me luck

2010-08-02T17:08:00.000-07:00

Tomorrow morning, I'm off to hike Mt. Kilimanjaro in Tanzania. It is 19,334 ft above sea level at the summit, the tallest peak in Africa.

If we're doing well, we'll even sleep one night inside the Crater, at roughly 18,000 ft. That should be amazing and painful at the same time. We'll be hitting the summit around new moon. Most people go for full moon as you have to do some night hiking, but we'll be hiking during the Perseids meteor shower, so the lack of moonlight, the lack of human-made light, and the high altitude should really make for quite a show.

I was hoping to be able to use MyTracks on the journey and post the route when I return. On some test trips, I tried a few solar chargers to keep my phone going, but none of them were able to collect as many photons as my Nexus One wanted to eat. I'll still be bringing the phone along for identifying stars (see my previous post), but I'll leave it off most of the way. I'll also bring back lots of photos to share on the blog.

If you want to get more involved, Jeremy, one of the other hikers, will be carrying a Spot messaging device that will track our route. You can see the map at http://jeremyshapiro.com/kili/. Another way to participate it to "sponsor" our climb in a sense. Matt Cutts set up a page at charity:water in honor of our trip, and he blogged a little bit about his choice of charities. Lastly, check back in about 2 weeks for a final update.

The 4 Android Apps that all backpackers should carry

2010-07-30T20:01:00.000-07:00

If you go backpacking or even hiking and use an android phone, here is a list of the Android Apps you should be carrying.

My Tracks: Record GPS tracks of where you hiked, view elevation profiles, and upload to Google Maps. Tip: To keep battery low, change the settings for coordinate frequency to "battery miser". This is what I use to generate nifty maps and elevation profiles of my hikes that I post on this blog.
Google Skymap: Augmented reality for showing the stars in the sky. Hold your phone up to the starry sky and see whether that bright thing is a planet or a star, and which one. Works even without data access.
Peak.AR: Augmented reality that will tell you the name of every mountain peak you are looking at.
Rainy Days: Overlays moving weather images over google maps to show you live weather around you. Obviously only works if you have data coverage.

I'm headed to Kilimanjaro on Tuesday, what are some other good backpacking Apps?

Twitter Queries and the Telephone game

2010-04-22T16:57:00.000-07:00

Last week, during the Twitter Chirp conference, Evan Williams apparently (I wasn't there) said that twitter gets about 600 million queries per day. Danny Sullivan claims to have caught Evan after the talk and Evan confirmed that the number was around 19 billion queries per month.

Danny then takes this number and made a blog post about this on Search Engine Land: Twitter Does 19 Billion Searches per month, beating Yahoo and Bing (sort of). In this post, Danny compares the 19 billion number to comscore numbers on google/yahoo/bing worldwide queries. He follows up by pointing out the "(sort of)" part, the caveats as I read them:

The comscore numbers are third-party, twitter is self-reported. Apples and oranges.
The number doesn't count partners like Google and Bing.
The "vast majority" of the searches are API requests, via applications running standing queries.
Many queries are generated by widgets placed on web pages that automatically return search results to display.

Danny even adds that Evan mentioned that twitter search itself only contributed to the overall queries in "the low double-digits". I'm not sure if that means 10s of millions per day or something else

Danny's article seems completely accurate to me, although certainly suggestive of a comparison that isn't entirely accurate. However, few people seem to read closely to the caveats. People have started reporting Danny's numbers verbatim without mentioning any of the caveats. For example:

Twitter Chirp: Twitter Search is Bigger than Yahoo and Bing Combined

Daily searches on Twitter Should Reach One Billion Queries in May

People have started quoting the articles that are quoting Danny, the notion that twitter is a bigger search engine than bing/yahoo seems to be gaining popularity. I believe that I even heard someone at SMX yesterday claim the 600M/19B numbers were search.twitter.com queries, and that the actual API queries far exceeded this.

My theory though is that the 600M/19B numbers refer to a backend query count, not actual user search queries. The comscore numbers are referring to actual queries done by users in a search box. If a running Tweetdeck instance is monitoring a query every 5 seconds or so, that one instance could rack up around 20,000 queries/day for each query it is monitoring. Similarly, widgets placed on web pages will generate at least one query per page view on those web pages. That's similar to saying google has bajillions of queries because analytics is installed on lots of webpages. Its even possible that me looking at my twitter stream or @gregable stream is a counted query. Furthermore, if I conduct a query on search.twitter.com and leave the page up, it refreshes every once in awhile - presumably each time it polls for new data, that's also considered a query - so 1 user query on search.twitter.com could be hundreds of queries the way Evan is counting.

Note, I don't claim Evan lied. I don't even claim he did anything deceptive in the way he counted queries. Danny put the twitter queries in context with comscore numbers, not Evan. And Danny was clear to point out the caveats, no blame there either.

I would take a wild guess that apples to apples, if you looked at actual twitter search "queries" in the sense that a user considers a query, it's "low double-digit" counts - say 20 million/day, and that those are actually roughly 10x smaller due to repeated polling - say 2 million / day. That puts Danny's comparison more like:

Google: 88 billion per month

Yahoo: 9.4 billion per month

Bing: 4.1 billion per month

Twitter: 0.06 billion per month

Still a huge number for twitter, but a bit more accurate of a comparison. Am I right? Evan? Danny?

Update: 06/08/2010: Techcrunch quoted Twitter's COO Dick Costolo as saying that twitter has 190 million visitors per month. This casts additional cold water on the notion that twitter actually gets 19B user queries every month. It would be strange indeed if the average visitor actually made 100 queries/month on twitter.

Training for Kili

2010-06-07T22:03:00.000-07:00

In August, I'll be doing my best to hike to the summit of Mt. Kilimanjaro, Africa's tallest peak. In the meantime, I've been trying to hit the trail whenever I can to make sure I'm in the best shape I can be in. The better shape I'm in, the more fun I'll have.

Pinnacles Day Hike Elevation

Last Monday, May 31, Memorial Day, Cristin and I joined @JeremyShapiro and Emily to hike around Pinnacles National Monument. Our route climbed from the east entrance up the High Peaks Trail, descended from the peaks on Tunnel Trail and Juniper Canyon Trail, and then looped back along the mellow Balconies Trail through Balconies Cave, a Talus Cave formed by rocks falling into a V-shaped valley. The whole trip was supposedly around 9 miles, of course with as much elevation change as we could find in order to prepare for the climbs we expect on Kili. The graph on the right is the elevation profile that MyTracks recorded. The GPS bounces around a bit though so the total distance of 12 miles is an overestimate. We were on the lookout for some California Condors, but failed to find them. The area was starting to get a bit hot for the summer, but still not too bad. Hopping into a dark cool cave in the middle of the afternoon was still an appreciated break from the sun. A few photos that I snapped with my cell phone when I remembered can be found here: Pinnacles Photos.

Ohlone Backpacking Day 1, Elevation

This past weekend, June 5-5, @JeremyShapiro, Ryan Moulton and I loaded up the backpacks and went for a 2-day trip in the Ohlone wilderness, hiking from Del Valle to Stewart Camp. Since it's a training mission, I opted for plenty of comforts and extra water, my pack weighed in at right about 40 pounds. While only 6.5 miles (again MyTracks is incorrect), The route was quite steep and exposed for much of the way as you can see in the elevation profile on the left. We ate lunch in the little dip you see around 1,800 ft, alongside a shady brook in Williams Gulch. Then it was more climbing up to the final ridge.

Nearing the campsite, we saw a small cairn indicating a path the bottom of Murietta Falls. We dropped packs and wandered down to find that the falls was only a trickle at the time. There was a small pool at the bottom with several small snakes in it trying to stay cool. The basalt rocks on top of which it flowed were fairly unusual looking for the area, and since two of us are regular rock climbers, we decided to free climb the falls back to our packs instead of hiking back up the path. The climb had several large ledges so it was fairly safe, but the climbing was sketchy in places, we thought we might need to downclimb a couple times. We eventually made it up the falls with only minor injuries, and startling only a handful of snakes. A little extra adventure for our adventure.

Another half mile of mellow trails and we reached our campsite, only to find someone else already in it. We held the reservation for this site for that night. The other group we found in our campsite had a reservation for the next campsite over - another 4 more miles. After completing the 6 miles of strenuous climbing, they had found themselves unable to continue on, so they squatted in our site instead. Fortunately, we found another spot just a short distance further down the trail that had been used as a campsite before and while it was smaller it turned out to be an even better campsite. A rock outcropping above the site provided some great flat spots to cook food and enjoy a fantastic view of the bay area, overlooking Livermore, Oakland, the SF Bay, San Francisco, and even the Pacific. It was possibly the best view we saw on the trail, and we only found it because someone else had stolen our campsite. We hung out and watched the sun set, the lights of the cities come on, satellites and shooting stars flying by overhead, and airplane traffic starting the descent into SFO. Ryan played the role of cameraman for this venture, you can find more photos over at Ohlone Backpacking Photos.

Using Amazon's Mechanical Turk for Price Comparison Shopping

2010-05-23T23:25:00.000-07:00

I use a ReadyNAS NV attached to my home network. When I bought the device, I initially installed 3x 300GB drives into it and that has served me well providing 600GB of RAID protected storage.

I recently decided to upgrade the drives. Netgear has a ReadyNAS Compatibility Guide which lists specifically tested and recommended drives to use with each of the ReadyNAS products. I knew that I wanted 1TB drives, which seemed from limited research to be a fairly good spot in the market. That left me with 11 drives to choose from, which seemed like alot of work to research and price compare. I researched a few on Amazon and bought my first drive for around $145.

For the other 3, I decided to try a different approach mostly as an experiment. I created an account on Mechanical Turk and asked 3 workers to find me the lowest price they could on any of these drives. I charged the task out at $3/worker and since there was no clear success criteria, I promised in the task description to give a $10 bonus to whichever worker found the cheapest price. I mentioned that coupon codes, discounts, and rebates were all fair game, but not to worry about shipping/taxes to keep it simple. I only cared about price: performance didn't matter much since it was a NAS drive. Total cost = $3 x 3 + 0.30 x 3 (Amazon's fee) + $10 = $19.90.

Here are the results, about an hour later:

Seagate Barracuda LP ST31000520AS at buy.co.uk for £68.02. I didn't specify US, my mistake. Still approved the work.
Seagate Barracuda ST31000528AS at unistorage.com for $68.84. This worker actually listed lowest prices for every one of the drives. The $68.84 one was the cheapest before shipping/taxes. This worker got the bonus by a slim slim margin (see worker 3).
Seagate Barracuda LP ST31000520AS at Newegg for $69.99. This drive ended up cheapest after shipping/taxes.

Ultimately I went with worker #3's suggestion, despite awarding the bonus to worker #2. Either way, I saved about $75 per drive over what I had bought with my own poor research, so this paid off in spades. I might have been able to figure this out myself and save the $20 as well, but this approach was less work and more interesting.

I think if I did it again, I'd be a little bit more specific about what I want (US retailer), maybe add shipping/tax to the mix, possibly ask for the 2-3 cheapest drives they could find so I have some choices. I'd also probably drop the task price to say $0.25 but add that any worker that gets within 10% of the lowest price worker will also earn a $3-5 bonus. I suspect that the ability to earn $3 for a few quick pricegrabber searches might make sticking around and spending more time doing research less enticing. Still the results weren't that bad with my first try, enough to make me wonder what else I could use the turk workers for.

Google Encrypted Search

2010-05-23T20:39:00.000-07:00

It's often fun to read the response that the internet community has to Google's launches, especially ones that I'm somewhat familiar with. There is always a bit of tinfoil hat concerns about Google's intentions.

Late last week we launched to Beta an Encrypted Google Search option. Most discussions focus on the privacy aspect of this launch, but there are a number of discussions noting that this disables referrer (and hence query) passing for many destination websites: take the webmasterworld discussion for one example. The tin foil hat interpretation is that Google hidden agenda is to prevent webmasters from seeing their query data.

Fortunately, it's easy to see what is actually going on. When you surf using the HTTPS protocol, the goal is to encrypt(hide) your surfing traffic from your transmitting network, not from the destination sites. However, if you click from a HTTPS page to an HTTP page, passing the referrer would leak a small amount of data about your encrypted traffic to the network. As a result, all web browsers that I know of send an empty referrer string in this case. Interestingly, if you navigate between HTTPS pages, even on different domains, the referrer is passed. This is consistent with hiding the data from the network but not the destination site.

If a webmaster so desired, they could move their entire site onto HTTPS and then start getting the HTTPS referrers sent to their server again. If Google's intent was to prevent websites from seeing query strings, there are much easier ways to do so, such as using POST.

Gas Station Inefficiency

2010-05-22T21:18:00.000-07:00

Near where I live is a gas station that is almost always packed and overflowing into the road. It's not particularly small, but they have decent prices.

I've wondered why the station always looks so busy. I think I have the answer. In addition to having decent prices on gas, they also have a big sign that reads "9c/gallon off with cash". I've observed that the vast majority of the users wait in line until their car is in front of a pump, then walk into the store to get in another line to prepay in cash for their gas. Once they've prepaid, they return, pump, and sometimes go back in for change. If you add all this up, they spend about 5-10 minutes with their car in front of the pump for every 1 minute or so of actual pumping of gas.Pump utilization is abysmal, leading to low throughput, leading to long queues. Sounds like a dumb algorithm to me.

What I don't know is if this behavior increases their sales or decreases them. I know that Cristin and I sometimes avoid this station because of the congestion meaning lost sales. However, it's possible that the lines of overflowing cars out into the road draws attention and gives a false sense that this must be the cheapest around driving more sales still.

Reservoir Sampling

2007-10-08T22:27:00.000-07:00

If you don't find programming algorithms interesting, stop reading. This post is not for you.

On the other hand, if you do find algorithms interesting, in addition to this post, you might also want to read my other posts with the algorithms tag.

Problem Statement

Reservoir Sampling is an algorithm for sampling elements from a stream of data. Imagine you are given a really large stream of data elements (queries on google searches in May, products bought at Walmart during the Christmas season, names in a phone book, whatever). Your goal is to efficiently return a random sample of 1,000 elements evenly distributed from the original stream. How would you do it?

The right answer is generating random integers between 0 and N-1, then retrieving the elements at those indices and you have your answer. (Update: reader Martin astutely points out that this is sampling with replacement. To make this sampling without replacement, one simply needs to note whether or not your sample already pulled that random number and if so, choose a new random number. This can make the algorithm pretty expensive if the sample size is very close to N though).

So, let me make the problem harder. You don't know N (the size of the stream) in advance and you can't index directly into it. You can count it, but that requires making 2 passes of the data. You can do better. There are some heuristics you might try: for example to guess the length and hope to undershoot. It will either not work in one pass or will not be evenly distributed.

Simple Solution

A relatively easy and correct solution is to assign a random number to every element as you see them in the stream, and then always keep the top 1,000 numbered elements at all times. This is similar to how mysql does "ORDER BY RAND()" calls. This strategy works well, and only requires additionally storing the randomly generated number for each element.

Reservoir Sampling

Another, more complex option is reservoir sampling. First, you want to make a reservoir (array) of 1,000 elements and fill it with the first 1,000 elements in your stream. That way if you have exactly 1,000 elements, the algorithm works. This is the base case.

Next, you want to process the i'th element (starting with i = 1,001) such that at the end of processing that step, the 1,000 elements in your reservoir are randomly sampled amongst the i elements you've seen so far. How can you do this? Start with i = 1,001. With what probability after the 1001'th step should element 1,001 (or any element for that matter) be in the set of 1,000 elements? The answer is easy: 1,000/1,001. So, generate a random number between 0 and 1, and if it is less than 1,000/1,001 you should take element 1,001. In other words, choose to add element 1,001 to your reservoir with probability 1,000/1,001. If you choose to add it (which you likely will), then replace any element in the reservoir chosen randomly. I've shown that this produces a 1,000/1,001 chance of selecting the 1,001'th element, but what about the 2nd element in the list? The 2nd element is definitely in the reservoir at step 1,000 and the probability of it getting removed is the probability of element 1,001 getting selected multiplied by the probability of #2 getting randomly chosen as the replacement candidate. That probability is 1,000/1,001 * 1/1,000 = 1/1,001. So, the probability that #2 survives this round is 1 - that or 1,000/1,001.

This can be extended for the i'th round - keep the i'th element with probability 1,000/i and if you choose to keep it, replace a random element from the reservoir. It is pretty easy to prove that this works for all values of i using induction. It obviously works for the i'th element based on the way the algorithm selects the i'th element with the correct probability outright. The probability any element before this step being in the reservoir is 1,000/(i-1). The probability that they are removed is 1,000/i * 1/1,000 = 1/i. The probability that each element sticks around given that they are already in the reservoir is (i-1)/i and thus the elements' overall probability of being in the reservoir after i rounds is 1,000/(i-1) * (i-1)/i = 1,000/i.

This ends up a little complex, but works just the same way as the random assigned numbers above.

Weighted Reservoir Sampling Variation

Now take the same problem above but add an extra challenge: How would you sample from a weighted distribution where each element has a given weight associated with it in the stream? This is sorta tricky. Pavlos S. Efraimidis figured out the solution in 2005 in a paper titled Weighted Random Sampling with a Reservoir. It works similarly to the assigning a random number solution above.

As you process the stream, assign each item a "key". For each item in the stream i, let be the item's "key", let be the weight of that item and let be a random number between 0 and 1. The "key", , is a random number to the n'th root where n is weight of that item in the stream: . Now, simply keep the top n elements ordered by their keys, where n is the size of your sample. Easy.

To see how this works, lets start with non-weighted elements (ie: weight = 1). is always 1, so the key is simply a random number and this algorithm degrades into the simple algorithm mentioned above.

Now, how does it work with weights? The probability of choosing i over j is the probability that > . can have any value from 0 - 1. However, it's more likely to be closer to 1 the higher w is. We can see what the distribution of this looks like when comparing to a weight 1 element by integrating k over all values of random numbers from 0 - 1. You get something like this:

k =

If w = 1, k = 1 / 2. If w = 9, k = 9 / 10. When replacing against a weight 1 element, an item of weight 5 would have a 50% chance and an element of weight 9 would have a 90% chance. Similar math works for two elements of non-zero weight.

Distributed Reservoir Sampling Variation

This is the problem that got me researching the weighted sample above. In both of the above algorithms, I can process the stream in O(N) time where N is length of the stream, in other words: in a single pass. If I want to break break up the problem on say 10 machines and solve it close to 10 times faster, how can I do that?

The answer is to have each of the 10 machines take roughly 1/10th of the input to process and generate their own reservoir sample from their subset of the data using the weighted variation above. Then, a final process must take the 10 output reservoirs and merge them.

The trick is that the final process must use the original "key" weights computed in the first pass. For example, If one of your 10 machines processed only 10 items in a size-10 sample, and the other 10 machines each processed 1 million items, you would expect that the one machine with 10 items would likely have smaller keys and hence be less likely to be selected in the final output. If you recompute keys in the final process, then all of the input items would be treated equally when they shouldn't.

Birds of a Feather
If you are one of the handful of people interested in Reservoir Sampling and advanced software algorithms like this, you are the type of person I'd like to see working with me at Google. If you send me your resume (ggrothau@gmail.com), I can make sure it gets in front of the right recruiters and watch to make sure that it doesn't get lost in the pile that we get every day.

Google I/O Site Review

2010-05-13T16:09:00.000-07:00

If you are going to be at Google I/O next week, I'll be on stage for the SEO Site Advice from the Experts Session with Matt Cutts and Tiffany Lane. It'll be a fast-paced Site Review, lots of fun. Check us out, Thursday the 20th, 2:15 PM, Room 8. Matt has put out the call for sites to review, ideally get in on the list early.

Henry Coe, Kelly Lake, Backpacking

2010-05-10T12:34:00.000-07:00

This past weekend I went backpacking in Henry Coe with JeremyShapiro, Matt Cutts, and David Signoff.

We hiked in on a perfect day from the Hunting Hollow entrance on a gorgeous day, a grueling climb up Middle Steer Ridge Trail, a short stroll along Steer Ridge Road to lunch at Wilson Peak where we saw a deer also relaxing and having lunch. We backtracked slightly and quickly descended half the elevation we just gained down Serpentine Trail. Back up on Tule Pond Trail, following the ridge on Wasno Road, then Wagon Road, and then a very steep descent down Kelly Lake Trail to Kelly Lake. Total distance: roughly 10 miles

There were 4 parties including ourselves overnighting at Kelly Lake. Beautiful spot, but lacking for ideal campsites and we weren't the first to arrive. I think I still prefer having Redfern pond to myself 2 years ago to sharing Kelly Lake with others. Serenaded by birds and then frogs, our crew played cards and then got a good nights' sleep.

The next morning, rain clouds started appearing so we packed up camp quickly and headed out. Our plan was to stick to trails back to Hunting Hollow, but we hit some moderate rain on the return hike and so took a shortcut. Back up Kelly Lake Trail on the other side, ridge walking on Wasno Road until descending on Dexter Trail which is when the rain hit, and then a moderate descent along Grizzly Gulch Trail until we reached the Coyote Creek park entrance. From there, only a 2 mile flat walk back to Hunting Hollow Entrance where my car was getting a nice shower. Total distance: roughly 7 miles.

I found a similar hike done by another crew, with GPS map and altitude here: Hunting Hollow to Kelly Lake round trip with GPS. That trip was 20 miles with 6800ft of elevation gain/loss.

Domain'ing is Annoying

2010-04-24T16:42:00.000-07:00

The way in which domain names are allocated seems broken to me. Speculators register domain names for a very small amount of money ($6/yr for .com's, sometimes pennies for some ccTLDs) and then refuse to give up the rights for anything less than $10,000. The domains are worth more than the registration cost to someone who would actually use them, but less than the squatter price. As a result, excellent domain names go unused (parked) while good content creators with low budgets end up with stupid domain names that nobody wants but which are affordable.

A strawman proposal for fixing this:
Instead of a flat $/yr charge for domain names, charge based on demand. If a user comes along to the registrar and wants to buy an already used domain name, they can file a bid with the registrar. The registrar records and authorizes the charge for the bid, perhaps even taking the money into escrow. At the same time, the current owner is contacted. The current owner can now choose:

Accept the offer, sell the domain name.
Accept an immediate increase in the annual registration fee for that domain name of 5% of the offer price.

So for example, I might bid $1,000 for greg.com. The owner of greg.com doesn't have to accept my bid, but if they don't, the registration cost rises to $50/yr. This should make them less inclined to squat. More valuable domain names will end up with a higher registration cost and worthless domain names will end up with a potentially lower registration cost.

The 5% is just a random number. Tweaks might include a some cap at $500, or having the percentage decrease as the offer increases so that the registration fee for google.com or whatever isn't astronomical. Perhaps reduce the percentage the longer the current owner has owned the domain as changes in identity are undesirable. It also seems like you might want to have registration fee hike exceptions in some cases, such as trademarks. Lots of options available.

Where should the extra registration money go? The registrars don't deserve most of this. I'd probably put it towards public projects to build better planet-wide network infrastructure (fiber in the ground) or something.

Preloading Hard Drives with Movies - Sneakernet

2010-04-13T17:51:00.000-07:00

The financial times has an article yesterday about Seagate preloading USB hard drives with movies. Apparently the drives will come with around 20 popular movies already present, but reading between the lines they are encrypted. If you want to watch them, you can do so by buying the decryption key online. I'm sure there is more DRM to it so that you can't easily share the movies, but the basic idea is kinda neat. Essentially, you are bypassing the biggest issue of digital delivery of movies (bandwidth and the latency of waiting for the download) by having the access to the movie controlled by a download of only a few kb encryption key.

I think this approach has potential beyond what Seagate is doing. Imagine if your Netflix subscription, instead of shipping you DVDs one at a time, just shipped you a hard drive with your entire movie queue on it in encrypted form. When you are ready to view the next movie in the queue, you just log into your netflix account and download the encryption key in a few seconds. Instead of having X DVD's out at a time, you could have X encryption keys per month or something. The advantage is that there's much less shipping involved and you can rearrange your queue however you want and start watching any of the movies immediately with no wait for the mail or slow internet download. Even a HD movie is probably only around 10GB, so a cheap 500GB hard drive should be able to hold around 50 movies, and moore's law will only improve on this.

Going a step further, using the MPAA's own statistics, there are roughly 600 big movies released to theaters a year, not all that many. At 10GB per movie, that's only 6TB of space required, or 500GB per month. Lets say all of these movies were "finished" at least 1 month before release. You could buy a 500GB drive for way less than the cost of a month of a cable subscription and by sending this back and forth to netflix, you'd have continuous on-demand access to any of the blockbusters the day that they are released and for roughly a month to follow. The producers could simply not sell the decryption keys until the chosen release date.

This is just the latency/bandwidth tradeoff of using the sneakernet.

Rock Climbing at Red Rock

2010-04-08T23:50:00.000-07:00

Cristin and I just returned from an action-packed rock climbing trip/tweetup at Red Rock outside Las Vegas. We spent 2 days climbing rocks, leaving our hotel around 8am and heading back around 5pm each day. The original plan was to climb for 4 days, but after day 2 we were a bit worn out and took a day off, and on day 4, rain clouds rolled in at about the same time we did so we had to bail and take advantage of the local indoor climbing gym instead where we found several other disappointed red rock climbers-to-be.

There were about a dozen total climbers in our crew, I met about half of them for the first time on the trip. Hello to @eleddy, @sudarkoff, @adrienneknits, @rockgrrl, @voden, @katiebeth, @tiffanymroyal, @joshuamontague, @chadcat, @JeremyShapiro, and @pwcarey, who took the above photo of me above on the 2nd day.

The trip was fantastic. I'd driven through red rock once before, but this was a different way to experience the park. There were unmarked trails in guidebooks which once followed led to hidden cracks chock full of other climbers, it felt like "the secret world" of Red Rock. This was only our third trip climbing outside of the gym, so it was even more of an experience for us.

On Day 1, we started out the morning climbing several routes at the Magic Bus area, which is actually one of the less red of the red rocks. A pretty vertical flat face, a great way to warm up. We heard some thunder in the distance, ate some lunch and as the area started to get crowded we headed on to Black Corridor for the afternoon. Black Corridor is a area with two vertical walls facing each other, like if you cut a loaf of bread in half and pulled the halves apart just a little bit. There were a ton of people already here, but there were also a ton of different routes available. It was a perfect afternoon spot as the two walls gave you plenty of shade when you weren't on the rock. I tried a fun route that was giving everyone trouble, a 5.10 (in theory) with a specific move about halfway up that none of us could get past. It required pulling up on a ledge not deep enough to get a whole finger joint onto.

On Day 2, we hit up Panty Wall in the morning whose base was a wide flat ledge above another vertical cliff, so it was a bit nerve wracking for several of us, myself included, when looking down at the drop below. But the view of the canyon was georgeous and the routes on the wall were lots of fun. For the afternoon, the group decided to head over to Calico Basin, on the flip side of Red Rock's best formation, but technically outside the park. We climbed around on Cannibal Crag, a massive boulder with routes on both sides. Jeremy showed me how to do a pitched route (although only 1 pitch) as well as how to lead belay, as we climbed the route "you are what you eat" with the big crack you can see in the picture to the left.

There were a few people with camera's going all the time, namely Cristin and Peter. Lots of photos available for anyone interested. I'm the guy usually in the blue jacket and orange helmet.

After we departed Red Rock, Cristin and I took a side trip to Death Valley for 2 nights. We did a couple fun hikes, including one through a canyon with extremely smooth marbled walls that get cut by waterfalls in the rainy months, making for some fun little rock slides. Another hike took us to the base of a small ice melt waterfall at a higher elevation, something I never expected to find in Death Valley. It was literally a desert oasis. Wherever the water flowed there was tons of life, but only a few feet away it was dry desert terrain. There are more photos of death valley here: http://picasaweb.google.com/jennifer.mccain/DeathValleyApril2010

Bay Area Weekending

2010-03-20T01:07:00.000-07:00

I've recently found myself telling a few people about how I found out about interesting thing X or Y to do in the CA bay area. It occurred to me that this might be a good topic for a blog post. If you always are looking for things to do, perhaps this might give you a few ideas.

Weekend Sherpa: Every thursday, the weekend sherpa publishes a newsletter of recommendations of outdoor trips to do in Northern California. I find the site is amazingly well curated, much more so than even similar magazines I've perused on grocery store shelves. For example, this post "Land of the Giants" recently inspired me to take off to Sequoia for the weekend and try my hand at snowshoeing.

Bay Area Hiker: The best single source of information I've found about great hikes in the bay area, primarily day hikes. There are tons of other great websites to look at too, this one just has alot of hikes in one place. Each hike has detailed description including photos, recommendations for time of year, and directions.

Point Reyes: This is the furthest west chunk of coastline in the area, making it a habitat for a variety of sea wildlife that you don't see as much elsewhere. Sea birds coming in to lay eggs, sea lions, etc. The peak whale watching season is just beginning now and this is the only place I know where you can see them without getting on a boat, useful if you get seasick like I do. It's also just an extremely pretty chunk of land. It's probably the largest park of this sort within driving distance with so many options for things to do. Tip: An excellent place to stop for grub along the drive is the Coast Cafe in Bolinas.

Planet Granite: Not cheap, but if you ever wanted to try rock climbing, this may be one of the best indoor climbing gyms in the country. I've been to about half a dozen different climbing gyms, so I can't personally compare, but I've heard from other folks that the Sunnyvale and SF gyms are really top notch. I wouldn't recommend the Belmont location though. This place rocks. I get a few free guest passes if anyone wants to give it a whirl.

I guess you can tell fairly easily what kinds of things I like to do on weekends. Any other good suggestions I should be trying?

PQ Tree Algorithm and Consecutive Ones Problem

2008-11-14T03:51:00.000-08:00

In grad school I ran across an cool problem and an interesting algorithm to solve it. Your input is a grid of elements, lets say rows 1, 2, 3, 4, 5 and columns A, B, C, D, E. In addition, you are given a set of "rectangles" which each consist of a subset of the grid's rows and a subset of the grid's columns. Is there a way to arrange the grid by permuting it's rows and columns such that all the rectangles are present contiguously?

Imagine a rectangle consisting of rows 2 and 5 and columns A, C, and D. The grid must be arranged such that row (2, 5) are contiguous and columns (A, C, D) are contiguous. One rectangle is trivial, multiple rectangles is a challenge. Take a look at the figure which visualizes one of these grids with embedded rectangles.

I realized the 2D problem decomposes into two separate 1D problems. The rows can be arranged without caring about the columns and vice versa. Once you reduce the problem to 1D, it turns out that it is a problem known as the Consecutive Ones Problem. If all you want to do is find an valid ordering, there is even an algorithm to solve the problem. In my case, there was rarely a perfect ordering, so I had to extend the problem to find the best ordering for some definition of best (see this paper on the subject).

The PQ Tree Algorithm

That would be the end of the boring story, except I mentioned that there was a algorithm that solved the perfect ordering problem and it was well-studied. It turned out that despite it being well studied, it is poorly known and virtually unreferenced on the internet.

The paper that explained it, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, came out in 1976. The paper doesn't exist anywhere on the internet, not even for purchase. No full description or implementation of the algorithm exists on the internet either. None of this has changed in the 5 years since I looked into this algorithm - still barely any references on the web. I intend to change that today.

The algorithm is called the "PQ-Tree Algorithm". I picked up a copy of the paper in book-form from my local library. Surprisingly, the problem can be solved in linear time. It is quite an intricate algorithm. I think I recall spending 2 weeks doing nothing but implementing this algorithm.

Lets make sure that you know what the problem is first. I'll state it simpler than my above 2D problem:

Consecutive Ones Problem

Imagine that you are having a dinner party and are planning the seating arrangement. To simplify the problem, imagine your seating as a one-dimensional ordering of your guests: Sue > Fred > Tom > Rudy > Bob > ... You are trying to choose a seating arrangement that makes the most sense for your guests, and you have a number of constraints that apply to the problem. Each constraint is represented by a subset of your guests which you want to seat together (consecutively). So, if one constraint is that Sue, Fred, and Bob sit together, then there are certain permutations that are invalid and certain permutations that are valid:

Valid: Rudy > Sue > Fred > Bob > Tom
Valid: Tom > Rudy > Bob > Sue > Fred
Invalid: Tom > Bob > Rudy > Fred > Sue

Furthermore, there may be many of these types of constraints, so perhaps you have (Sue, Fred, Bob) as one constraint and another might be (Sue, Bob, Tom). One possible solution would be given as:

Tom > Sue > Bob > Fred > Rudy

This is the crux of consecutive ones problem, although the consecutive ones problem is formulated a little differently: Given a binary matrix containing only ones and zeros, reorder the columns such that the ones in every row are consecutive. The image below illustrates the point:

The matrix (a) can be transformed to the matrix (b) be rearranging only the columns in (a). The matrix (b) has the consecutive ones property (COP) in that the 1 values in each row are consecutive when read in order. The consecutive ones problem is: Given a matrix (a), determine if it can be converted into a matrix (b) by rearranging columns such that (b) has the consecutive ones property, and if so represent all valid orderings of the columns.
To see that this is the same as the guest seating problem, assign each guest to a column in matrix A. Each row represents one of the constraints we want to apply to our seating - the columns in that row containing 1's are the guests that we want to seat together.
Not all matrices can be transformed into a COP matrix. Similarly, some matrices can have many possible orderings.

My Contributions

I implemented this algorithm in grad school. My implementation then was functional but not high quality, and it was embedded in a larger library. I've spent considerable spare time here and there over the last couple months rewriting a large part of that code.

I've created a project up at github which tracks the code: PQ Tree Algorithm Implementation.The code (just a library) should be decent, bug-free, and GPL. The first internet implementation out there.

A full description of the PQ Tree algorithm can be found on knol: PQ Trees and the Consecutive Ones Property. I'd recommend checking out the algorithm knol even if just to get a high-level flavor of this interesting algorithm.

If you stumble across this page while trying desperately to do some research for your graduate program, I hope this is useful to you. I ask one small thing of you though. I spent a good bit of time putting all of this together. Drop me a comment or email letting me know how you are using it. That way I'll know it was worth the effort.

Birds of a Feather

If you are one of the handful of people interested in PQ-Trees and advanced software algorithms like this, you are the type of person I'd like to see working with me at Google. If you send me your resume (ggrothau@gmail.com), I can make sure it gets in front of the right recruiters and watch to make sure that it doesn't get lost in the pile that we get every day.

Feed Reader Recommendations: Boston Big Picture

2008-11-11T09:28:00.000-08:00

I don't normally recommend blogs for people to check out or subscribe to. When scanning my own feed reader, most of the blogs I subscribe to are not really fit for a general audience. That said, there is one blog that I ran across that seems to be a relatively little known gem and probably matches a wide audience of interests. That blog is the Boston Globe's Big Picture Blog. Every few days they post a series of photographs on one particular "story". These are always global public interest stories, not local boston news or anything. The thing that sets it apart is the fantastic photography like this one from yesterday's post about Antartica:

My take on Buzz

2010-02-15T16:21:00.000-08:00

Imagine that to read this blog, you had to first sign into your Blogger account. And that to read a Wikipedia article, you first had to sign into your Wikipedia account. And, when you want to read your email from your AOL friends, you have to first sign into your AOL account, but to read your email from GMail friends required first signing into your GMail account. And imagine this was the case everywhere. You could even take this further and imagine that to read CNN, you first had to load the CNN browser.

To various degrees this is the current state of microblogging services (or whatever you call them). I can't read my friend's Facebook updates in google reader. I can't read the Boston Big Picture in Twitter. Even if my friends wire up their accounts so that their tweets end up in Facebook, my Facebook replies don't appear in their Twitter stream. It's a big bucket of suckage.

As a user, I don't care about how the electricity gets to my house, but I really really care that all my appliances can use that electricity, not just the ones that PG&E made. So I care that someone else cares about the how and standardizes this. As a publisher, I want to be able to pick my publishing platforms - maybe more than just one (Flickr+Twitter+Blogger) - based on how well their features meet my style. I don't want to have to choose my platform based on where my readers might be. As a reader, I want to pick my reader application(s), like Google Reader, Bloglines, or Facebook, but only have to pick one or maybe two and to pick them based on features and usefulness to me, not based on where the people I'm interested in reading publish their content.

Switch gears. Google Buzz launched last week. We've been trialling it internally at Google for some time now, but I had pretty much tuned it out. It was just one more social network with mostly inconsequential status updates of which I was overwhelmed with already. Now though, I realize that I had duped myself. Buzz is not necessarily just another walled garden (although, there is still that risk).

Time out. I am an employee of Google. I don't work on Buzz, heck I have less to do with it at the time of writing this than most Google employees having largely ignored it for so long. The opinions in this post, as well as elsewhere in this blog, are my own and not those of my employer. Seriously. Nuff Said.

Buzz could be a move to a more open standard for microblogging. This ReadWriteWeb article on how Buzz's API supports Open Data Standards says it better than I. I spent some time in the last few days reading up on PubSubHubBub, Salmon, WebFinger, etc. I'm no expert, but it's exciting. Whether Buzz succeeds or not matters little to me, but if this kind of open social networking standard takes off, I think we're all going to be a little bit saner in managing our digital lives.

Battery Voltage Regulation Prediction Software

2010-02-26T13:12:00.000-08:00

It's rare that I can talk about green energy and software issues in one post. Here's some software that someone needs to write.

Over at "This week in batteries", Venkat Srinivasan explains the tradeoffs in modern battery charging. Essentially, the problem is that the higher voltage you charge a battery to, the bigger capacity it has in terms of discharging. However, higher voltages at the same time reduce the lifespan of the battery so that the next charge will have a little less capacity. Virtually all battery chargers choose a fixed voltage to charge up to and then stop charging, and this chosen voltage is a number that gives a good balance between capacity and lifespan, but doesn't really maximize either. From the article:

Operating to 4.1V makes things better and extends the life, 4.0 V is even better and so on. So why don’t battery manufacturers cut the voltage off at, say, 4 V to get better battery life? Because every time you cut this voltage down you decrease the capacity of the battery and its run time. The 4.2V cutoff is a compromise between good run time and decent (read “not pathetic”) life.

Venkat goes on to suggest that this means you should charge your devices up to the maximum limit and then unplug them, so that they slowly drop a little below the max, to extend lifetime. He also mentions that Lenovo laptops even let you set the charge (as a percentage, not a voltage) if you want to play with these settings yourself.

This is a problem not just for laptops, but also for cell phones, plug-in cars, or any device that uses a battery. I'm certainly not a battery expert, but it seems to me that there is a better solution out there.

Most devices using an expensive battery have some amount of processing power and some amount of long-term memory (flash drive, hard drive, etc). Laptop, Cell Phone, and Vehicles certainly fall in to this category. If the device was able to predict roughly how long it would be used before the next recharge, then it would be able to charge to the lowest voltage required to stay alive until the next recharge.

Humans are creatures of habit, we often keep roughly the same schedule from day to day or week to week. If the device kept a history of these habits, it should be able to predict usage. For example, storing data like:

Plug in timestamp
Unplug timestamp
Running out of juice timestamp
Day of week, time of day
which user is logged in, or how much they weigh on the driver seat sensor
ip address the device is allocated to (or nearby wireless APs)
GPS location
applications that were run

Using a little bit of simple machine learning, the software could predict how much capacity is needed for the next unplug and chage accordingly. Thus if the laptop is always plugged in at a desk except on the weekend, a low voltage charge could be maintained and then ramped up all the way saturday morning. Or if the car is used for short trips to/from work, but on Friday night is driven to the next city for happy hour with friends, you can keep the voltage high for happy hour and low for the commute. If the device sees a completely new scenario (suddenly turned on in Japan at 3am on a different network), then it might switch temporarily to a high voltage/capacity until enough data comes in to know what to expect in this new scenario.

This approach would maximize both battery life and capacity while keeping the user blissfully unaware.

Grid Alternatives - The solar version of Habitat for Humanity

2008-01-22T22:05:00.000-08:00

Last week I attended a training session for a group known as Grid Alternatives. What they do, basically, is to get volunteers and donations to install solar panels on homes of low income families in the bay area.

All the labor is free (volunteers) and the panels are heavily discounted in CA due to various federal, state, and city rebates offered. They claim for every $1 donated they are able to achieve nearly $3 in construction value. If I read that correctly, their cost for constructing a solar install is 1/3 a commercial install, due to the rebates and free labor. They are also actually achieving this, claiming to have installed 70 homes worth of panels in the last year alone.

The training I went to was about 2.5 hours, required no advanced knowledge, and while I don't feel like I could go install a set of panels tomorrow, I do feel like I learned a bit about the process and am comfortable enough to want to volunteer some weekend in the future. It sounds like their bottleneck is not labor or leadership, but rather money to buy raw materials. As a person who wishes to put some panels on my home but is unable to because I live in an apartment, I am going to be donating some of my normal donations to these guys this year instead of some of the alternatives. I like charities like this which are local, make visible, real, understandable changes, and of course it hits upon two of my favorite causes: green power(climate change) and poverty. If you live in the bay area or even if not, I would highly recommend checking them out. Well worth a look. Also definitely get on their one-mailing-per-month mailing list and/or donate a few bucks. www.GridAlternatives.Org

Update: Feb 17, 2010:

I asked some questions recently to the team at Grid Alternatives about their financials. Non-profits have to file a tax form, Form 990, every year detailing how they spend their money. Anyone can read these on guidestar.org, so you can verify much of this stuff yourself. In 2010, they plan on installing 338 solar projects, with an average cost per project of only $7,890. This is after government rebates and includes overhead. Obviously some of the projects are bigger and some are smaller, but the average install is around 2.25 kW. This translates to $22,614 of energy bills saved over the life of the install, a roughly 3x return on the investment, not to mention the additional 90 tons of CO2 not put into the atmosphere (depending on grid mix). Even ignoring the environmental aspect, the economics work out surprisingly well. Thanks to Zach Franklin for the detailed numbers.

Swoopo and stable equilibriums

2010-02-05T11:10:00.000-08:00

If you've never heard of swoopo.com, it's an "auction" site that allows you to bid on items in 1c increments. Usually the items sell for much much less than they are worth. For example, this 1oz gold bar (worth around $1,400) sold for $216.98. The trick is that you can only bid exactly 1c more than the last bid and simply making a bid costs you $0.60. So, 21,698 bids were made on that gold bar by various people which cost them over $13,018 in total. The winner spent almost $700 in bids themselves. Most people who play this game are losing lots of money.

A similar (simpler) game is described as an auction for a $20 bill. The rule is that you pay your most recent bid, regardless of whether or not you win. You can argue that it always makes sense for you to bid. Initially, you are bidding $1 for a $20 bill, how awesome is that? However your opponent in the auction can now bid $2 for a $20 bill, which he will definitely do - why wouldn't he? At some point you have bid $19 for this bill, but your opponent recently just bid $18. If he doesn't bid $20, he loses $18 - if he does bid $20 and wins, he comes out even. So bidding $20 seems like the right choice. Unfortunately now you lose $19 bid lost if you don't bid and you lose only $1 if you do bid (bid = $21, but you win $20). So it makes sense for you to actually bid $21 for a $20 bill. This continues forever with the risk that both participants bid hundreds of dollars for this $20 bill.

I was having a lunch conversation with some folks the other day who argued that the best choice at any turn is to always bid, but that this is a paradox because you will lose your shirt playing this game. I think the paradox is easily resolved. The thing that causes the paradox is the assumption that the best decision is to always bid, which seems on the surface to be the right strategy but in fact is not. If you assume this is the right strategy, this game has no stable nash equilibrium, but I claim that the game does in fact have such an equilibrium strategy.

Imagine your opponent in this game (simplification - the game is a 2 player version of the $20 auction) is one instance of a set of players in the universe of possible players. As such a player, there is a distribution of points in the auction where that player will stop bidding. The number of players that will make it to $1 is high, say 99%, the number of players that make it past $20 is probably somewhat low, and the number of players that make it to $1 million is probably nearly zero. As a result, you can evaluate at each point in the game what is the expected number of additional bids that you will have to make to gain the $20 bill. If this is greater than 10 bids (an increase of $20 in your bidding), then you should not bid. If it is less, then you should bid. Depending on the distribution, you may choose not to even play the game or you may likely choose to play up to a few dollars or so because some reasonable fraction of other players give up early. If you played enough such games, you would expect to come out non-negative however on some individual games you would expect to lose money. My guess is that the real distribution for a $20 auction in the world of opponents would be such that not bidding at all makes sense, but if you make it a $1 million auction, then I would guess that due to finite budgets of your average opponent, it would make sense to bid up to some reasonable number and give up.

Interestingly, there are some distributions that would suggest you should never stop bidding. For example if the probability that your opponent continues to bid decreases by 50% every time, then at any point in the game, you would expect to have to bid only 2 more times, meaning you should always keep bidding. However, this is fine as long as your estimate of the distribution is correct because the odds of your opponent bidding 10 more times are tiny (1 in 1024). So you are essentially betting on a fair coin toss repeatedly with a 1:10 payoff.

I have no idea what the distributions are for swoopo auctions. If someone has the dataset, it would be interesting to analyze it and figure out the optimal strategy and see if it ever makes sense to bid (maybe it does in some cases).

rel=canonical part two

2009-12-15T20:09:00.000-08:00

Google today officially announced support for cross-domain rel=canonicals. This is a very important step. I talked about rel=canonical when we announced it 10 months ago. This tweak will be very useful in a variety of cases. A few interesting ones:

Any place where you want to move your site to a new domain but can't control server headers. This can be really useful to help avoid lock in on free hosts for example.
Companies that register several domain names as landing pages for offline advertising, a practice often used for tracking performance of the campaign, can now keep users on the original domain but keep spiders going to the right place so Google doesn't end up with 10 copies of the site.
Syndicating content - if your syndication partner agrees - you can now make sure that your "link juice" flows back to the original article in Google.

I think we'll see lots of creative uses of this tweak in the future as we've seen with the original rel=canonical. Let's just hope those creative talents are used for the power of good.

Favorite Google Doodle: A fun chrome extension

2009-12-08T15:00:00.000-08:00

Google announced extensions for Chrome Web Browser today, a much awaited feature for many. Go try out a few. If you are looking for recommendations, one quirky fun little extension that I would recommend is the Favorite Google Doodle Extension. It lets you select your favorite Google Doodle logo from Google's doodling history and set it as the logo for your Google search page whenever Google isn't running a special logo for that day:

Unfortunately, today isn't the best day since Google is actually running a special logo today celebrating the cartoonist E.C. Sagar, the man behind Popeye the Sailor. However, if you install and choose a logo today, you'll see it on the search results page, and likely tomorrow (depending on whether or not there is a special logo running then too). I've set might to be this fancy scientific logo for now. I found some other of my favorites too:

I will admit that I'm undeniably biased as a friend of mine actually wrote this extension. If you like it, don't forget to rate it too.

Life is NP-Hard

2008-03-03T00:11:00.000-08:00

I think that this is going to be one of my more interesting blog posts. It is philosophical in nature though and a bit long, so maybe it's boring, I don't know. Let me know in the comments if you like it or hate it. Lets get to it shall we?

NP-Hard Problems

In Software there is a set of Problems called NP-Hard problems. I think my audience would run screaming if I explained this in technical detail (either they already know it and would be bored or would find it boring in general). I'll give two examples though:

Subset Sum: Given a list of N integers, determine whether or not any non-empty subset of these integers sums up to zero (or any other number).
Traveling Salesman: Given a map of the world and a list of N cities find the shortest path for a traveling salesman to visit all of these cities.

The story as I understand it (and I may have this off) was that there were a bunch of really smart algorithms folks working on problems like these two over at Bell Labs(?) back in "the day". They were trying to find algorithms for solving these problems. The problem is that the only algorithms they could come up with took exponential time to solve as N grew. So, if they could solve the traveling salesman problem with 3 cities in 1 second, it might take 2 seconds to solve with 4 cities, 4 seconds to solve with 5 cities, 8 seconds with 6 citites and so on. By the time you hit 30 cities it takes you over 4 years to solve the problem. Well before you hit 1,000 cities no computer known to man can solve the problem before the sun explodes.

Thats a problem. It's also embarrasing if it is your problem and you can't solve it. Some folks tried the reverse approach. After getting tired of trying to find a faster solution, they tried to prove that there was no faster solution. This is a common approach for this kind of problem, it is good to know that you aren't stupid and you can prove it. Unfortunately they couldn't prove that there wasn't a faster solution either.

So, all of these smart folks started talking to each other. Someone then figured out that their problem was actually equivalent to someone else's - that is if you could solve one you could solve the other. They started asking around and determined that there were many of these problems and that in fact they were all working on the exact same problem, described in different ways. For example, the two problems I stated above, the Subset Sum problem and the Traveling Salesman problem, are the same exact problem.

Life is NP-Hard

Other than being mathematically the same problem, I see that most NP-Hard problems have some common characterstics:

There are partial solution, such as a path between all of the citites which may not be the path.
If you have two partial solutions, you can somewhat easily compare them and determine which one is better.

Many things in life have similar properties: If I look back at my life 1 year ago I can evaluate several things about my life now and my life then and directly compare them. Wealth is one thing, happiness (to a point) is another that I can do this with. The only problem is that I can't evaluate what the best possible state could have been today - what would have happened if I did X in the last year instead of the Y that I did. So, in a sense it is NP-Hard because the number of possible combinations of things in my life make it impossible for me to predict which combination will be the best, but I am somewhat (not completely) able to predict the outcome of a few different options. If I choose to go spend $100k on a new car, I have a good idea of how much that choice will affect my financially and a good idea of how much it will affect me in happiness. I don't know exactly, but I have a good idea (hence I don't buy said overpriced car).

Another example is the economy. I am not making a political statement, although it might sound a little like that right now. An economy is a state that can be directly evaluated and compared (the GDP of is $X today and $Y tomorrow), but the complexity of the state that made the economy the way it is makes it impossible to guarantee that it couldn't have been better (or worse). However, one can with some reasonable accuracy make some predictions about the path. For example, one might predict that lowering the Federal Interest rate will improve the economy and if that person was an expert, they could have high confidence in the effect of the choice.

OK, so I can't prove that the economy is mathematically equivalent to the traveling salesmen problem. I can't even prove that the sum subset problem is equivalent to traveling salesman. Still, I have a suspicion that they are equivalent or at least close

Solving NP-Hard Problems in Polynomial Time

Back to Software for a moment. It turns out that there is a common strategy for solving these NP-Hard problems. The strategy doesn't guarantee that you will find the best anwer, or even that you will find a good answer. But it guarantees to try and in practice usually it works very well. The strategy has a few different names, but a common name that is pretty layperson descriptive is "hill climbing". I'm going to steal some of the graphics from that wikipedia article and modify them, because I'm lazy and drawing 3d objects by mouse is kinda hard, so I'd better reference wikipedia.

Here is my best attempt at a non-technical explanation of hill climbing. Its actually pretty easy, so don't run away. Imagine you have one goal in life: namely to get as high (altitude not narcotic) as possible. Flying is out and to make things hard you are blind. But you do have a perfect GPS device that you can press a button on and it will tell you the exact height of the point you are standing on now.How would you try to get high? The simplest answer is hill climbing. Imagine that this image on the right (image here) is your world. You start out somewhere on this world. You take a step in any direction and see if you have gotten higher or not. If not, you step back and try a new direction. If so, you repeat the process. So, with every step you get progressively a little bit higher. If this image is your world, you would eventually get to the top, and it wouldn't take all that long either. That is hill climbing, and it solves NP-Hard Problems in Polynomial time. With travelling salesman, for another example, you would start with a random path through all cities, then try swapping the order of two cities in your original path. If the change gives you a shorter path, keep it, otherwise reverse it and try something else. It works pretty well.

The problem with hill climbing is that it doesn't always work perfectly. Imagine if instead our blind friend lived in the world on the left. There are two hills here, one being higher than the other. If our blind friend were to start climbing the left hill, he may very well get to the top of it, declare himself the highest man in the world since he can't climb any further, and he might be very wrong. How sad. This phenomenon in hill climbing is called "local maxima".

These "hills" are present in any problem. The height of the hill is it's utility: time to travel to all cities, wealth, etc. The x, y location are the parameters required to achieve that utility, although it is often far more than 2 dimensions that are at play.

The reason it works is that things are rarely completely random. Most of the time small changes in a situation have small effects on your utility function and large changes have large affects. Whether I choose to eat an apple or a banana has little affect on my happiness, but whether I choose to eat ice cream every day for the next month or excercise every day for the next month could have a large affect. The problem with large changes is that the larger they are, the less I can tell in advance what the outcome will be (remember, I'm blind on this hill). The ice cream tonight is stepping uphill - I know it will make me happier right now. Excercise is stepping downhill - I know it will cause pain and make me less happy right now, but it might be stepping downhill for the sake of eventually stepping up onto a much higher hill. On the other hand, it might not be because the downhill part is so long that I'll give up and walk back up my shorter hill by eating ice cream again.

Economics are another interesting example. A free economy, Adam Smith's laws of supply and demand, are a great way to allow hill climbing to work. If there is more demand for bread than apples, the price of bread increases until farmers decide to plant more wheat and less apples to increase their farm's revenue. The system prevents itself from going overboard - if the farmer produces too much wheat, it will suddenly become more valuable for him to produce more apples. Eventually the hill will be climbed when the perfect balance between apples and wheat is reached - and nobody needs to know what that balance is in advance (the "invisible hand" of economics). The problem with this is that there are local maxima at play in an economy. What if instead of growing wheat, the farmer could start researching a new apple that tasted twice as good. For many years, the farmer may be losing money (walking downhill) on this research until that better apple began to materialize. The longer the downhill stint, the harder it will be to get to a new hill. What if there exists a cheap way of producing limitless clean energy without coal or oil, but it takes billions of dollars of research money and a decade of research to discover it. Adam Smith would be hard pressed to get us there.

Self Help

So, now I'm given a mathematical basis for self-help material, yay. Climb Hills, but occassionally look for new ones. Makes alot of sense, but I find it comforting and useful to think of the world in this way.

PS: If you know the difference between NP-Hard and NP-Complete and caught me mixing them somewhere in there, don't complain in the comments, send me your resume, Google is interested. My rot13'ed email address is ttebgunh@tznvy.pbz .

Edit (10/21/2009):

An astute reader pointed out that I did indeed confuse NP-hard and NP-complete, and actually abused the whole notion altogether. Technically, the TSP problem is I stated is not a classical example, not exactly. Classically, NP-hard/complete problems are those with binary decisions as output. So, we aren't usually finding the shortest traveling path, we are answering the question of if the shortest path is less than distance X. That said, if you could tell me what the shortest path is, I could trivially tell you if it is less than X.

The class of problems that can be reduced into different versions of each other are NP-complete, whereas NP-hard simply means that it is at least as hard as NP-complete. This produces a small problem with respect to the blog post. I really wanted to talk about problems that could be transformed into each other, and problems where you want to optimize, not just determine if an optimization was possible. The first is NP-Complete, but "Life is NP-Complete" just lacks the same ring as "Life is NP-hard".

Simple Simhashing

2009-10-06T17:26:00.000-07:00

A friend and coworker of mine, Ryan Moulton, just wrote a very nifty knol called "Simple Simhashing". If you like software algorithms, it is most certainly worth a read. Simple simhashing is an algorithm that allows you to take any "thing" and come up with a simhash that should be the same for two "things" in probability relative to how similar those to "things" are. The really nifty part is that the algorithm is completely local and the properties are provable in an easy to understand way. This algorithm is actually used at Google in a few places, although I'll leave it to you to guess how.