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."

if i'd only known

they wanted such boring submissions.
The winning idea was cool, but the rest looks
like free development for google rather
than something novel.

Re:if i'd only known

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)"

As previously designed by me

Here's one [emapsite.co.uk] i wrote earlier.

Dosn't do the document lookup thing, but we were using it for finding the neariest piza on a now defunct e-commerce website.

I see one being implemented soon

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.

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

What a great idea

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

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.....

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!

"Google Sets"

It really seems to me like the "Google Sets" feature recently made available at Google Labs [google.com] is an implementation of Zhenlei Cai's submission(although the details are extremely sketchy in the Google announcement). If this is true, I wonder why they couldn't implement the winning idea too?

more details

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 [census.gov] and FIPS [nist.gov] 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

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

Re:more details

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 ?

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 ?

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.

winner is...

The winner is... a former Microsoft employee.

Let me guess: he "rebranded" a piece of software that was under a BSD license?

All kidding aside, sounds pretty neat.

Geographical Approximation

I don't think the Pizza delivery analogy will pan out. They can pin it down to a country (usually), and maybe even a region of a country(rarely), but beyond that, it won't be possible to get very close. For example, in the country I work for, the whole class B address shows up as being in the UK, but it is broken up accross each european country, so even if you are in spain or france, it looks like a UK address. I'm sure many companies do the same. Also, the IP addresses from the cable ISP will cover a wide area of several cities or sometimes a whole country.

Not earth shattering, but useful

Credit to the guy for thinking of it. It could save a person the hassle of looking up all the address in mapquest. I've never had the need to do such a search on google, since it's easier to just do a yellowpage search. Most yellow page sites like superpages and switchboard already provide that kind of functionality. Google's directory search doesn't have search by distance yet, but I'm guessing it will be added in the future. They kinda have to considering the other directory sites have those features.

Service already exists

There is already a service like this at www.lasoo.com [lasoo.com] This service lets you enter an address and a business type, and will find all instances of that business within a certain radius of the address.

Last time I used Lasoo was on Mother's Day, to find the closet florist to my mom's house.

Nice

Whilst I'm very impressed with the winner the entry "Robust Hyperlinks" is something that do like a lot.

What would be cool, would be the option to right click on the hyperlink and have the option "Find alternative location".

Or even cooler, have IE (or your favourite browser) on putting up the 404 message have a hyperlink which does the same. Hell, easy enough to do with apache.

Funny.

I was looking for a similar tool yesterday when I was doing research for low power FM transmitter placement. I have a street address for the tower and was looking for an easy (or more accurate, as I am not an adept map reader) tool rather than looking at the USGS maps.

I knew I should have patented it...

I was thinking about doing exactly the same thing, a common thought?

But the idea of using it just to find business within a certain radius is very limited thinking.

Mobile phones will soon be broadcasting their position. You want interactive guided tours of a city? How about playing full size monopoly? Driving directions? Any sign you currently see could be removed and replaced with a virtual sign? Any number of VR worlds played out in meat space? etc etc

I think that the ability to automatically tell someone where you are will prove to be a boon.

Kudos to the developer for carrying through, rather than my lazy ass postulating :-)

runner up

the runner up entry

Zhenlei Cai, for his project, Discovery and Grouping of Semantic Concepts from Web Pages with Applications. This effort processed a corpus of documents and found words and phrases that tend to co-occur within the same document, producing a list of pairs of terms that seem to be closely related (such as "federal law" and "supreme court", or "Bay Area" and "San Francisco").

sounds a lot like Google sets [google.com]

Robust Hyperlinks has to be my favourite.

NetGeo

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

Cached Longitude and Latitude

Does this mean that when the time comes to leave this planet and move to Mars that we can still visit our favorite places via Google's Cache?

More uses

Search => Nearest horny drunk college girl
Results: Apt 2D

locatity of businesses and services

just had an idea for how to implement this using meta tags. I should probably submit it to the w3c if no-one else has already...

have a new meta tag class for "location" which would include the GPS (or long/lat, etc.) co-ordinates for the business, etc. along with human readable country, such as UK, FR, NL, US, NL, etc. and region.

then have another tag for how far the service provider/company does business for with rules for excluding and including areas.

so if a copmany operates, i.e. delivers, within a 3 mile radius then a search engine will know. if they operate in their local state/county it will know. if it operates regionally such as Europe wide or Globally it would be easy to locate a provider of goods and services which will be able to help. The exclusions could cover things like states which the product is deemed illegal or that the merchant doesn't wish to do business with.

Of course you'd need to let the search tools know where abouts you are in order to refine the results. But this needn't be the source of any privacy issues as the engine could submit a complete set of results and be filtered out at the client end dynamically if the user is paranoid.

what do you think?

Mb

watch out, google.

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

so as a former microsoft employee he's going to run his code on the google servers.
Nah, this one's too easy!

A project that really could be good for Google...

is something that prevents cheating.

So you think that Google's results are fair? You're wrong. The best ranked results are from sites that heavily cheat.

Since Google has aggressively removed fake generated sites linking to each other, new ways of cheating have been immediately adopted.

Apart from cloaking (what the Google crawler sees is different from what user see), generated sites now include fake generated english-like sentences in order to make Google think the text is real. Spam indexing is now distributed on multiple IPs. Content is dynamic, it changes everyday (random links and texts are generated) . Temporary sites are hosted on external (yet non-blacklisted) cheap colocated servers. Invisible frames are added, etc.

I'm not innocently talking about that because the company I'm working for is actively doing it. And it works. And they say "Spam? Uh? Who's talking about Spam? It bring us money, so it's not spam, it's our business".

There are ways to prevents cheating on Google. It's probably very complex, but it's realisable. If any human looks at our 'spam site', he will immediately discover that it's not a real site. It's a mess, just for keywords and links.

If such a project had been made for the Google content, it would have been wonderful.

Google is still the best search engine out there. Their technology rocks, and they are always looking for innovation. But what could make an huge difference between and other search engines is : fair results. Same wheel of fortune for everybody.

Yet this is not the case. Trust me, all well ranked web sites for common keywords belong to a few companies that are actively cheating.

A good source of innovation...

This is actually a nifty way of getting real good ideas from people. $10000 seems a bit cheap for an idea that can make google helluva lot more than that.

Geographically limited browsing

So does this now make it easier for governments to limit their citizens ability to get information than ever before?

As well as any other of the many geography based rules, laws, taxes, restrictions, etc that we have seen talked about on /. before???

Wow

What was failed to mention from his resume [ofb.net]:
Miscellaneous Projects

1995 - ongoing: Free Software

I wrote and maintain Gale30, an open source instant messaging system. Other free software projects of mine include Airhook, Liboop, and some XML processing tools.

2001 - ongoing: Sweetcode

I am the sole proprietor of Sweetcode, a web site that reports interesting free software. Sweetcode receives thousands of visitors daily; media reports include NTK, memepool, the Linux Weekly News, and others.

2000 - ongoing: SeattleWireless

I maintain the Node Map, a simple XML-based GIS which uses public mapping engines to display the location of community 802.11b wireless nodes in Seattle.

Anyone here who got the CDROM with data mailed?

I requested the CDROM collection with the Google data but still wait for them.

Did they actually send out those copies?
Or is it because I live in Germany?

Regards,
Marc

Daniel Egnor's "Iocaine Powder"

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

More Information About the Winner

I've met Dan Egnor, and this isn't the only cool thing he's done. He's the author of Iocaine powder [ofb.net], the world champion rock-paper-scissors program. He's also the proprieter of sweetcode [sweetcode.org] 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.)

Why I never would have written that program.

How many hosts implement their coordinates in their info any more?

5%? 10%?

80% omit it because admins are lazy, and 10% omit it for security reasons.

So Google just gave an award to a tool with half the batting average of a bad baseball player.

--Blair

Not IP based

I noticed a lot of the previous comments talking about the inaccuracies of using IPs to get geographical location. Well it should be pointed out that he parses for street addresses in the html document then converts those to geographical coordinates. So it would even work for people who have a business in Washington but are hosted in Utah.

Smooth Move Google

Did you all read the honorable mentions? Google stands to make some good money off of the ideas and implementations these folks have come up with. I'm assuming that all entries now are owned by Google, and man they might have some really cool new features after seeing the projects that were submitted. I only hope that they give at least some royalties to the developers.

Mapblast does this already

Mapbast [mapblast.com] gives you the lat/lon of any address you give in the corner of the map. It even will make your directions into GPS routes with a little tweaking. Combine with a $90 eTrex [garmin.com] for a cheap OnStar system.

Besides, it's line-drive directions are the coolest.

I'm a little disappointed.

Daniel received a bachelor's degree in Computer Science from Caltech in 1996. He has worked for Microsoft Corporation and XYZFind Corporation, and currently resides in New York City working for a large investment bank.

I was hoping the contest would create new opportunities for some young unknown, like: "Bob is a high school sophomore and currently resides in his parents' barn in Fargo and earns his keep stocking shelves at Toys 'R Us." Oh well, maybe next year.

it could have been the popular choice

i should have just made somehting that groups pages by cup size

isn't google already doing geo tracking?

i thought google already builds results also based on from where you (as a search engine user) are located.

when i lived in austria for a while results for common searches (movies, places to go out) frequently used to include sites with austrian content, which doesn't really happen any more now that i'm back in germany.

i thought it was a common practice, also considering that it's not that hard to implement (you could easily base this filtering logic on the TLD of a site and the IP of the requesting machine).

I wonder what this person worked on at Microsoft..

They have a product called Streets and Trips. You can enter in your address, and find out what is within a 5 mile radius lets say. Sounds pretty much like what this guy did.

Been There, Done That, Lots o' Issues

Parsing out addresses from web sites is notoriously unreliable. A company can have multiple addresses for multiple locations, franchises will have location finder code accessing databases instead of static HTML pages, locations can be in graphic text rather than parsable text, etc. Doubt that he solved all of those issues.

Worked at a company 3 years ago that sold similar technology to another major search company. It cross-referenced domain name addresses to business listings from InfoUSA. Maybe 60% coverage with 80% accuracy.

Speech Recognition

Zhenlei Cai, for his project, Discovery and Grouping of Semantic Concepts from Web Pages with Applications. This effort processed a corpus of documents and found words and phrases that tend to co-occur within the same document, producing a list of pairs of terms that seem to be closely related (such as "federal law" and "supreme court", or "Bay Area" and "San Francisco").

Am I the only one who thinks this would be useful for speech recognition? If you just detected a "federal" and you have two possibilities for the next word, "law" and "paw" say, the software would know it's more likely to be "law". Federal paw is probably fairly uncommon and yet this is exactly the mistake that current software makes.

Wired article

Here is a Wired article [wired.com] on it.

Re:good news for open source?

How is google open source?

Re:good news for open source?

It is great to see open source software such as google

Google's not open source. They support the open source community, but they don't release the code the their indexer. This is all the information that they give out about their code:

PageRank Explained

PageRank relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page's value. In essence, Google interprets a link from page A to page B as a vote, by page A, for page B. But, Google looks at more than the sheer volume of votes, or links a page receives; it also analyzes the page that casts the vote. Votes cast by pages that are themselves "important" weigh more heavily and help to make other pages "important."

Important, high-quality sites receive a higher PageRank, which Google remembers each time it conducts a search. Of course, important pages mean nothing to you if they don't match your query. So, Google combines PageRank with sophisticated text-matching techniques to find pages that are both important and relevant to your search. Google goes far beyond the number of times a term appears on a page and examines all aspects of the page's content (and the content of the pages linking to it) to determine if it's a good match for your query.

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

Christ, give it a break. I know there's an anti-anti-Microsoft backlash here, but for fuck's sake all he did was mention the previous employer with absolutely NO bias or connotations. If the guy had been employed at XYZ University, I'm sure it would have still shown up.

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

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.

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

Gates didn't write [halcyon.com] DOS.

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

And we certainly dont believe he got better at coding while he worked at MS.

You've never learned from the mistakes of others?

Being a former M$ employee tells me he learned quite a bit.

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

the part about him being a former MS employee was directly quoted from the submitter, not inserted there by michael. I know it's slashdot reader policy to not read the story, but at least read the fucking summary on the front page before flaming away...

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

Former MS employee, submits his project to Google, the ultimate linux site.

Come on...

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

Sigh...

In submitted articles, italics designate the submitted article, while normal text indicates Michael's or CmdrTaco's, etc., additions.

Note that this one was all italics, meaning the 'former Microsoft bit' was included by the person submitting the article.

Re:Not First Post!!!

I suppose the page-widening effect has its promoters and vindicators, but it is an effect only for IE (and only on Windows to boot).

Such page-widening "complaints" are not about the code thrown out by servers, but are complaints about the rendering engines of specific browsers.

Why don't you fix your browser and get over yourself?

Re:oh boy geocoding and buffer zones invented!

Here here! I've been doing that for years.

Back from the Dark Side

Actually when I saw that a former Microsoft employee had written something for Google, I had a flashback to that scene in Return of the Jedi where Vader makes up for a lifetime of evil deeds by tossing the Emperor off the platform. It's never too late for someone to turn back from the Dark Side. ;)

My Karma hit 50. Now maybe I can start posting intelligently.

Well, you're back down to 49 now!

GMD

Re:Some might think..

Though their operating systems may be riddled with bugs and security flaws of all sorts, look at their applications. They tend to be the epitome of quality software.

Yeah, right. That one dancing PaperclipDude was the "epitome of quality software".

Me: (starts writing a letter in Word)

PaperclipDude: "Hi there! It looks like you're writing a letter!"

No shit, Shirlock. What gave it away? The "Dear Sirs" opening line? Shees.

GMD

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

Well if no one cares, why did you bother even commenting on it?? Of course people here care!! It will drive half of /. readers half out of their mind with rage!!!

Re:answers.google.com

I found that site by typing in "answers" into AOL Search (back when Google had a press-release on the front page about their partnership with them.)

I wanted to try AOL Search out. Of course, Google was genius because I was instantly redirected back to a Google site....