Google Programming Contest Winner

asqui writes "The First Annual Google Programming Contest, announced about 4 months ago has ended. The winner is Daniel Egnor, a former Microsoft employee. His project converted addresses found in documents to latitude-longitude coordinates and built a two-dimensional index of these coordinates, thereby allowing you to limit your query to a certain radius from a geographical location. Good for difficult questions like "Where is the nearest all-night pizza place that will deliver at this hour?". Unfortunately there is no mention whether this technology is on its way to the google labs yet. There are also details of 5 other excellent project submissions that didn't quite make it."

Comments

I see one being implemented soon

[Masem]

From the hon. mentions:

Laird Breyer, for his project, Markovian Page Ranking Distributions: Some Theory and Simulations. This project examined various properties of the Markovian process behind Google's PageRank algorithm, and suggested some modifications to take into account the "age" of each link to reduce Pagerank's tendency to bias against newly-created pages.

This may help to defeat the current practice of overloading the PageRank results of a given key word as to point to a given page by having people link to that page with a link containing that keyword, aka "Googlebombing". I do think that the winner is a very interesting and useful project, this latter one will probably be implemented ASAP.

I sent something into the contest.

[thedanceman]

But I guess they thought there was no need for -thedanceman- on the google site.

What a great idea

[TedCheshireAcad]

If only more pizza restaurants in my area had web sites. Soon enough, I won't even have to pick up the phone to make my food come to me! I wonder if the delivery guy will bring the pizza up to me at my computer. Hmm...

Google Search

[iramkumar]

Search => Osama Bin Laden
Latitude/Longitude => 37/180, Pak
Capture ...

If this would have come out before we could have saved a country ...

Idea for a Google Query.....

[ReelOddeeo]

Where is the nearest server in my jurisdiction where I can download....

• MP3's
• Warez
• Pr0n
• Explosives making instructions

And worst of all....

• DeCSS

We've got to stop all of the terrorists in the categories mentioned above!

more details

[Alien54]

Daniel's project adds the ability to search for web pages within a particular geographic locale to traditional keyword searching. To accomplish this, Daniel converted street addresses found within a large corpus of documents to latitude-longitude-based coordinates using the freely available TIGER and FIPS data sources, and built a two-dimensional index of these coordinates. Daniel's system provides an interface that allows the user to augment a keyword search with the ability to restrict matches to within a certain radius of a specified address (useful for queries that are difficult to answer using just keyword searching, such as "find me all bookstores near my house"). We selected Daniel's project because it combined an interesting and useful idea with a clean and robust implementation.

This is impressive bit of database manipulation. Somehow I didn't think that all of the datatypes, etc would be so easily parsed.

Although I do recall telephone directories that used to give you results for a specified radius for certain types of businesses

Re:more details

[Lars T.]

Sounds like this improvement isn't much use outside the US.

Re:more details

[Chester K]

This is impressive bit of database manipulation. Somehow I didn't think that all of the datatypes, etc would be so easily parsed.

Although I do recall telephone directories that used to give you results for a specified radius for certain types of businesses

That's just a standard spatial query. It's easy to implement an R-Tree to be able to do (relatively) quick "give me points within x meters of this one" type of searches on a database. There's nothing extremely revolutionary about Daniel's project, anyone with some basic geometry knowledge and the patience to download the 33GB of TIGER data could have done it within the course of a few weeks. (Ironically enough I've been doing the same thing with 1.2 million addresses against TIGER data for the past month.)

But that's the true genius and beauty of it. Now that it's been said, it's such a mindbogglingly obvious and useful application of web search and spatial search technology that it's hard to believe nobody thought of it before.

I'd be honestly surprised if Google doesn't run with the ball and fold it into their main search engine. The only thing standing in the way is the storage space and CPU time to do it.

404 Page Not Found ?

[bigmouth_strikes]

I'm surprised that there are so many 404 Page Not Found errors in Google's search results, even on the top hits.

Shouldn't Google automatically check results that a user follows and flag those that cannot be displayed ?

Re:404 Page Not Found ?

[LinuxHam]

Shouldn't Google automatically check results

I would much prefer to see them improve the ease of browsing their cache. Specifically, if a cached site is 404, then present a cached version of the site where all clicks within the site simply link to the cached version, unlike today where all clicks are native (and therefore lead to more 404's). Granted that wouldn't be of any use for links to dynamic pages, but anything is better than what they have today.

Re:if i'd only known

[Indras]

like free development for google

Let me quote from the homepage of the annual contest:

"Grand Prize

$10,000 in cash

VIP visit to Google Inc. in Mountain View, California

Potentially run your prize-winning code on Google's multi-billion document repository (circumstances permitting)"

NetGeo

[*xpenguin*]

There's a public database called NetGeo which will convert IP addresses to latitude and longitude locations. I created a script called IP-Atlas to get a visual location of the lat and lon coords.

Re:About the "Former Microsoft Employee" bit..

[PrimeEnd]

If the guy had been employed at XYZ University, I'm sure it would have still shown up.

Actually he was employed by XYZFind Corp. Literally. And it didn't show up.

Daniel Egnor's "Iocaine Powder"

[po8]

In a weird coincidence, I just spent a half-hour last night lecturing about Daniel Egnor's Iocaine Powder , winner of the First International RoShamBo Programming Competition. Credit this guy with two award-winning pieces of extreme programming cleverness!

More Information About the Winner

[td]

I've met Dan Egnor, and this isn't the only cool thing he's done. He's the author of Iocaine powder, the world champion rock-paper-scissors program. He's also the proprieter of sweetcode a web log devoted to innovative open source projects (i.e. projects that don't just clone or tweak existing software.) But his best hack (not described on line, as far as I know) is a version of Pac Man that runs on a PDA and uses a GPS for a user interface -- if you run around an open field carrying the GPS+PDA, the pacman correspondingly runs around the maze chasing Blinky, Stinky and Dinky (or whatever their names are.)