October 30th: Bay Area Earthquake

Mmm, earthquake. Kinda like milkshakes, except more fun:

About 20 minutes ago, a 5.6 quake shook my little apartment up a bit. My first noticable earthquake experience, not a very bad one. After the fact, it was kinda fun.

Sentinel Dome, Jeffrey Pine in Yosemite

Last night I returned from my first visit to Yosemite. I went up with Cristin and a group of Googlers, ate dinner in the dark atop Glacier Point, spent the night in a tent on the valley floor, and then hiked Sentinel Dome. Cristin took this amazing photo (and several others) from the valley of the mountain formation that I think was called "Three Brothers". The entire trip was memorable, but I'll write a little more detail about Sentinel Dome, as it is a little less of the "been there done that" story.


Yosemite's Sentinel Dome is the second highest point in the main Yosemite Valley (Update: I had said the park, but this is untrue as an astute reader pointed out), other than Half Dome. While Half Dome gets hundreds of visitors daily, we hiked the far easier trail to Sentinel Dome and saw maybe a half dozen people on the trail total. It is definitely not a popular spot despite the fact that it has a 360 degree view of the valley, and a short 2 mile (one way) hike from the parking lot. It is considered by some to be the best place in the continental US to see the night stars. It is also from here that Ansel Adams took one his most famous photograph of the Sentinel Dome Jeffrey Pine. It has since become one of the most photographed trees in the country.



The left image is Ansel Adams' photo, the right image was one taken in 2002. In the intervening years, there was a severe drought. Visitors to Sentinel Dome hauled buckets of water to the dome to water the tree, to no avail. The right picture is the tree after the drought. Some time in August 2003, the tree fell over in the wind. The image above of myself and Pedro is what it looks like today, just a log really. Sad, in fact there is some pocketknife carving on the side you can't see in the image. Still, it is quite a sight on top of the bare granite that is Sentinel Dome.

I have to wonder why this trail isn't more popular. It seems like one of Yosemite's rare secrets.

Fires in Southern California

If you haven't already heard, there are huge fires causing a natural disaster in Southern California right now. Worse than they've seen in the past and they are still fairly out-of-control. If you are wondering, I'm nowhere near this, fortunately. I just get the earthquakes.

Permanent Drought in Southwest US

This is a really great article in the NY Times (the NY Times writes great stories) about the drought that is affecting the Southwest. There are two quotes I particularly like:

When I asked if the drought in his models would be permanent, he pondered the question for a moment, then replied: “You can’t call it a drought anymore, because it’s going over to a drier climate. No one says the Sahara is in drought.”

And then some optimism, in a quote that is fun even out of context:

“A crisis is an interesting thing,” he said. In his view, a crisis is a point in a story, a moment in a narrative, that presents an opportunity for characters to think their way through a problem. A catastrophe, on the other hand, is something different: it is one of several possible outcomes that follow from a crisis. “We’re at the point of crisis on the Colorado,” Pulwarty concluded. “And it’s at this point that we decide, O.K., which way are we going to go?”

CFLs: emitting all that dangerous mercury

An argument I've heard before against CFL lightbulbs is that they contain mercury vapor and hence are worse for the environment than incandescent bulbs. Take, for a moment, the facts in this statement as truth. We are definitely talking apples and oranges. Mercury Vapors (as best as I know) are not a greenhouse gas. Hard to say which is "worse for the environment". Doesn't matter anyway because while CFLs do contain 4 mg of mercury (GE's bulbs are 2mg if you care), incandescents release even MORE mercury, according to the EPA:

The biggest source of mercury vapors is the US's favorite way to make electricity - burning coal. Over the 5 year expected lifetime of a single CFL bulb, the energy required to light one incandescent releases 10 mg of mercury into the atmosphere. 10 mg > 4 mg. And if you properly dispose of your CFLs, they won't release any mercury.

Pelamis: Ocean Wave Energy

One of the fun parts of working at Google that anyone can participate in is that we have alot of fun speakers talk on alot of fun topics. Last November, a company creating a machine to capture energy from Ocean Waves came to talk at Google. They have a snakelike machine that rides right on top of the waves far into the ocean, so that they are practically invisible. Waves are created by wind over large distances, wind is created by sun over large distances, so ultimately waves are an effective solar power source. Turns out that collecting this solar energy from the waves is alot easier (cheaper) than directly from the sun. Wave energy has the potential to generate up to 2,000TWh/year or enough to offset 2 billion tonnes of CO2. Check out the video below:

Around 26:00 on the 1 hour video, they show a video of the machine in action (admittedly a smaller-scale version in the lab). These guys (Ocean Power Delivery) are really serious too, they have gotten their machine industrially verified for survivability, and have actually built one of them in the UK with existing contracts to build 3MW of power. Cool stuff.

Second Earth

Holding up my blog action day promise, I must post about something environmental. I'm kinda environmental'ed out at the moment, but I did see a fun science article about a planet we've recently discovered that could be a second earth. It is about 20 light years away.

Ad Hoc Restaurant

Last night, I went with the Mountain View Cooking Club to Ad Hoc Restaurant in Napa Valley (Click for a Map). Ad hoc is a restaurant by Thomas Keller who also created what some consider the best restaurant in the country (also in Napa Valley), French Laundry, where a meal is $240/head.

Ad Hoc is also pricey, at $45/head. They serve only one menu choice which varies daily, although as we found out they do substitutions for allergies or whatnot. The menu is four courses, served family style where everyone serves themselves from a common container. Our menu consisted of an excellent vegetable soup with bacon(my favorite vegetable) and fried bread. We were then served a Chicken and Shrimp dish atop a bed of lentils, cooked and seasoned perfectly. The third course was a cheese course with a "flagship cheddar" that according to our waiter won 2nd place awards for cheddar. It was indeed the best cheddar I've ever tasted. The final course was a divine Smore with Chocolate Ice Cream. The graham cracker, the ice cream, the marshmallow were all made at Ad Hoc from raw ingredients. Very good. The cooking club is considering trying to recreate this last one.

The staff wears t-shirts and jeans, and while many of the patrons are dressed well, it seems like a casual dress is equally welcomed, I was wearing jeans. It was a comfortable atmosphere, loud, but not too loud, very friendly staff happy to talk at end about the food. A fairly small dining area, maybe 15 tables or so. All in all, it was quite a treat. A pricey treat and a bit of a drive, but still fun.

The IPCC is Wrong

Shortly after my minor run in with Al Gore, he won the Nobel Peace prize. He is getting alot of the credit, but in reality the prize was half awarded to him and half to the IPCC, the Intergovernmental Panel on Climate Change. The IPCC is a group of scientists set up through an effort from the United Nations. One of its main activities is to publish special reports on topics relevant to the implementation of the UN Framework Convention on Climate Change (UNFCCC). The IPCC has published 4 reports in 1990, 1995, 2001, and most recently early in 2007.

One of the things that these reports do is to publish models of climate change that attempt to predict the future. The publish a range of values, worst and best case. Folks who don't care about climate change tend to argue with these numbers, claiming that we've never seen this before so any number is really just a guess with no historical data to back it up. On the other end of the spectrum, there are folks like me who tend to believe reports from an organization this serious and scientific.

Of course, as with any theory you can test it by waiting to see if your estimate matches reality. That has now happened. It turns out that the IPCC was very wrong in their estimates, especially one estimate - the speed at which the greenland icecap would melt. The IPCC painted a grim picture where the Greenland ice caps would probably be completely gone by around year 2,100. I probably won't live that long, but there are people alive today who will. You have to forgive me for trusting models that really ignored many variables and tried to do its best. You see, the IPCC's model was so badly incorrect, that by the time it was published it was clear that it was a bit off. By now, summer is nearly over and the most recent satellite data shows how bad the IPCC's estimate really was.



The real data shows that the Greenland ice sheet has shrunk by about 30% compared to the same time in 2005. The rest of the sheet that is still around has decreased in thickness by over 50% since 2001. Many well respected scientists are now suggesting that we may have an iceless northern icecap as early as the summer of 2013, in just under 5 years, not the century that the IPCC suggests. See, in the graph above, the IPCC estimate is red, the blue area is the best/worst case range of estimates, and the dark black line is reality. Reality tells us that the IPCC was way too optimistic.

Why was the IPCC so wrong? The IPCC was afraid to include in their models variables that weren't as well understood because they did not want to be discredited if they overestimated climate change. They wanted a conservative estimate. Here are things that they ignored:

1. Albedo Feedback. White snow and ice reflect alot of sunlight back into space, that is energy the earth doesn't absorb. As it melts, that snowy surface turns into darker water or rock which absorbs alot more energy.
2. Carbon Cycle Feedback: As CO2 concentrations increase, plant life on the land and in the sea becomes less capable of absorbing CO2.
3. Permafrost Feedback: As the artic warms, permafrost melts and organic matter that was previously basically frozen starts to get converted by bacteria into methane, which bubbles up and enters the atmosphere. Methane is 25 times more powerful as a greenhouse gas than carbon dioxide.
4. Glacier Flow: Heated air melts ice from the top, that water collects in pools and since it is both heavier than ice and warmer, melts its way through to the bottom of the glaciers and then the glaciers are lubricated and flow into the ocean more easily, where the warmer water in the ocean speeds up their melting.

You can find more information here, read the full report if you have the time. Some of the scientists quoted in the report believe that we are beyond the tipping point, whereby it may be impossible to maintain a steady state or even return to a steady state. You can see why in the graph below. I on the other hand am grimly optimistic that we can (although pessimistic that we will) stop this.

Micro Wind Power, Shawn Frayne

Shawn Frayne, an inventor based nearby in Mountain View, just won a Popular Mechanics award for a gearless wind power generation device that works 10-30x more efficiently on small scales than micro-turbines. It harnesses harmonic oscillation of a material within a wind stream to move magnets within coils of wire thus generating electricity. In the video you can see by clicking the link below, he shows a really small demo unit that someone could probably pretty easily build themselves. Take a look.

Click to show the Video

Click to hide this Video

Blog Action Day

Apparently Monday is Blog Action Day. So, I'll be posting something environmental I guess. Are you surprised?

Farmers Market Strawberries

I walked past the local farmer's market today and bought a little bit of produce. Some fresh leaf lettuce which I plan to make into a salad soon and a small container of strawberries. I expected both to be good fresh produce, but I didn't expect what I discovered... but let me set up the story slightly.

In high school, I had a good friend Dan. I don't recall the context, but I said to Dan "lets play it by ear". Dan had a realization at that moment that he shared with me. For his entire life, he had believed that the saying was "play it by year". He hadn't thought to double check before whether or not he had things right, "play it by ear" wasn't the kind of thing you think about much.

I had a similar experience with these strawberries. I grew up understanding that strawberries had a characteristic thick sweet initial flavor with a sweet-tart finish. Try a grocery store strawberry and see what I mean. I knew that the tart could be hidden with other flavors added, like whipped cream. What I didn't know was that a strawberry existed that only had the thick sweet flavor all the way through and not the sweet-tart finish. Like Dan, I never asked that question. These strawberries have a smoothness like honey, with that unique strawberry flavor.

Al Gore

I unexpectedly passed Al Gore on the stairs at work while I was headed to dinner. I wish something had popped into my head to say to him, but instead I smiled and walked by. He has done more to raise awareness for the environment than any other elected president. ;)

Standing an Egg on Equinox

Continuing a theme from the last post of playing MythBusters using science. When I was a little kid, my schoolteachers would tell me about the equinox - it is one of 2 days of the year where the day and night are the same length. It also is the 2 days where the earth's axis is perpendicular to the sun. To demonstrate how this is special, they wave their hands about the sun's affect on gravity and tell me that on this day and this day alone, I can stand a raw egg on it's end!

Even better, as a good science experiment should be, the teacher either demonstrates with their own egg or hand me one and have me try. After alot of patience, it works. The egg stands on it's end. Science is proven, the egg experiment proves that the sun is doing somehing hand wavey with gravity.

Teacher, I'm sorry but you missed a step. If you happen to try to stand on one foot on the equinox and succeed, that doesn't necessarily mean you can only stand on one foor on that day out of the year. Turns out that you can stand an egg on end any friggin time. Really. Try it NOW. Don't trust me, do your own experiment. The trick is you need a little patience. On non-eqiunox days, you don't believe it can be done, so you don't try very hard. On equinox days you will fidget with this egg for god-knows how long until it stands, dammit! There are things called blind studies that would fix this confounding variable in your experiment, if you are still not convinced.

Carbon Dioxide and Plants

When you are in 2nd grade, your science teacher teaches you that trees take in carbon dioxide and "turn it" into oxygen. When you are in high school, your chemistry teacher teaches you that matter is neither created nor destroyed and that ordinary chemical reactions can't change atoms, just their rearrangement. You learn that carbon dioxide is a carbon with two oxygens CO2 and that oxygen in the air is two covalently bonded oxygen elements or O2.

Unfortunately, perhaps because you grew up not questiong that trees change carbon dioxide to oxygen, you don't reconcile the statements from your science class and chemistry class. The obvious question if both are correct is what do the trees do with the C in CO2? The answer is they use that carbon to make wood, leaves, flowers, acorns, etc. So, the amount of carbon that a tree takes out of the atmosphere can be no more (by mass) than the amount of carbon and hence the total mass of the tree. A plant in your office that weighs 2 pounds after you shake the dirt off and dry it out has taken 2 pounds (or less, some can come from the soil) of carbon out of the atmosphere during its whole lifetime. So much for cleaning all that air in in your office, some quick google searches turned up that humans about 400 lbs of carbon by breathing during 1 year (I didn't research this number much, so don't trust it).

Trees are not machines that magically turn CO2 into O2. An old-growth forest (aka, not growing) tends to be carbon neutral (not negative) because some new trees are growing, and some have died and are decomposing (which releases carbon dioxide trapped in the tree's wood/leaves/etc). Of course deforesting or burning that forest means that you release more CO2 and stop absorbing it, so it is still good to leave it standing.

So... planting trees doesn't really reduce global warming, at least not after the tree is grown up.

Reservoir Sampling

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

Problem Statement

Now that that is out of the way, Reservoir Sampling is a fun algorithm. 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.

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: guess the length and hope to undershoot. It will either not work in one pass or 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.

Classic Reservoir Sampling

Another option is reservoir sampling. In the example I've given you, the algorithm above is a little simpler, but reservoir sampling can be extended in other ways which I will get to, but first the basic algorithm:

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? The second 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.

Weighted Reservoir Sampling Variation

Take the same problem above but add the extra challenge: How would you sample from a weighted distribution where each element is given a weight? This is sorta tricky. The above algorithm can be found on the web easily, but I don't know where I can find a weighted reservoir sampling version, so I made one up. I'm 100% sure someone has figured this out before me though, I don't take credit.

Start the same way by filling in the first 1,000 elements of the reservoir except keep a sum of the weights seen so far. Call this seen_weight. Also, make sure to store the weights of the individual elements stored in the reservoir. Call these weights a different array named weight[]. Lastly, to keep things efficient, store a variable for the total weight of the elements in the reservoir called reservoir_weight. On step i, generate a random number between 0 and 1 and use this pseudocode:

prob_sum = 0;
for(x = 0, x < (1-(weight[x] * 
                seen_weight /
                reservoir_weight /
                (seen_weight + input_weight)
               )))/reservoir_size, ++x) {
  if (prob_sum > R) {
   // replace
   reservoir[x] = input_element
   reservoir_weight += input_weight - weight[x]
   weight[x] = input_weight
   break
 }
}
seen_weight += input_weight

The only magic here is: (1-(weight[x] * seen_weight / reservoir_weight / (seen_weight + input_weight))))/reservoir_size. We treat the seen_weight so far as the weight for the current reservoir, so if we have a seen weight of 9 and a new element comes in with weight 1, It will get added in with 1/(9+1) weight. weight[x] * seen_weight / reservoir_weight does this magic by calculating the fraction of weight in the reservoir allocated to element x, and then multiplying that by seen_weight. After this step, the new reservoir will have a weight of (seen_weight + input_weight) so we divide by this - then since we are only talking about a single element at a time, we divide by the reservoir size too.

Distributed Reservoir Sampling Variation

This is the problem that got me looking at 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. Then, a final process must take the 10 output reservoirs and merge them with another sample. The trick is that the final process must take into account the reservoir weights of each of the input reservoirs. Basically, the final process should reservoir sample every element in the 10 input reservoirs but assign each element a weight of weight[x] * seen_weight / reservoir_weight where weight[x] is the element's original weight, seen_weight is the total weight counted in generating that particular reservoir and reservoir_weight is the sum of the weights of the elements in the reservoir. Proving this works is a little harder, so I will frustrate you by leaving it as an excercise for the dear reader.

41Pounds

I've written about greendimes before. I just ran across a competitor! Not much to report, they are offering the same service description for $41 which covers you for 5 years. Check it out - 41pounts.org

Path of Technology

I was thinking a bit today about technology. Alot of people tend to have the notion that in various tech industries, technology follows something like moore's law - getting exponentially better over time. All that is needed is some quantity of "research" whatever that is. Moore's law is that the speed of computers will double every 18 months.

There are historically other paths that science and technology have taken in the past in different industries, and to ignore these alternate possibilities seems rash:

1. Chaos: The study of weather in the 60s(?) promised to allow long-term weather forecasting so that we could all schedule our picnic outdoors 3 months in advance and not worry about rain. Then chaos theory showed us why this is more or less an impossible thing to predict in the long term.
2. Large Capital Cost: The Apollo missions ended with the Cold War. Things may eventually change, but space exploration, especially manned, has reverted. We haven't been to the moon in decades.
3. Physical/Social Danger: Nuclear Energy promised to give us unlimited cheap clean energy forever. Instead, there has been no new nuclear power plants built in the US in about 15 years. Chernobyl, concerns about Yucca Mountain, public dissent killed off the nuclear industry.

Any one of these possibly scenarios could still play out in technologies of today. Bioinformatics and Drug Design could end up being a chaotic space in the limit. Creating an alternative fuel vehicle requires large capital outlays to make sure that there is a good vehicle and sufficient places to refuel it. A few high profile privacy violations could ultimately have chilling effects on social networking and the internet.

Who knows what the future will bring.

CF Flood Lights

Apparently you can now buy CF (compact flourescent) flood lights. I had some 50 watt floods in my apt and took one to Lowes to see if they had CF versions. The answer is yes, they look nearly identical and only pull 14 watts.

Santa Cruz Monarch Butterflies, now with Map

Starting now, the Santa Cruz Butterflies have started to land in Natural Bridges State Park. Every year, Monarch butterflies swarm a really really small area of land during their migration. Really, the area that they land in is probably the size of the infield of a baseball field. The totally amazing part is that these butterflies have never been here before. Their parent's parents have, but since the lifespan of a butterfly is so short, their annual migration spans several generations. Nobody knows how they find their way to the exact same spot every year, but they do and it is amazing to see.

The butterflies start to arrive in October, but really start clustering in late October (a few weeks away) or November. The leave in January. Worth a trip if you are in the bay area. I was just down there on Sunday.

Getting to the park and then the butterflies is quite easy. I've included a map to the monarch butterflies in Santa Cruz below:

There are two parking options shown on the map, $6 parking in the southern official entrance or park on the street on the north side of the park for free and walk a little further through the pedestrian entrance to save a few bucks. Take a stroll down the short butterfly trail, and don't forget your camera!
View Larger Map