Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mathematics at Google

research.google.com

Post reply on HN
Print view View original

41–50 of 51 posts

Re: Mathematics at Google

#41

Post by andrewcooke »

JumpCrisscross wrote: post #33
killerbat00 wrote: post #27

Earlier quoted context omitted.

Vannevar Bush's ideas about information organization and consumption in the future were eerily accurate. Reading about the history of Memex and the roots of the Information Architecture field in general is something I highly recommend for anyone interested in Information Science, etc.

Recommended book(s)?

bush is mentioned in mirowski's "machine dreams", and it's not very complementary. that book is one of my favourites, but it's a post-modern, opinionated, soft-science (he's a history / philosophy / economics guy) take on post-war economics (and a whole pile of surrounding subjects). i suspect most people will hate the book as much as i love it, but you might be interested (perhaps you can find a library copy to check out....)

Re: Mathematics at Google

#42

Post by sb »

psykotic wrote: post #32
dxbydt wrote: post #31

The article has a section on the math used in Google Maps, which points to http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf which says - there are 24 million places in the USA, connected by 29 million roads. You need 4 hours 15 minutes to pre-process this information. From then on, it only takes 7 milliseconds to find the shortest path from one place to another by running the Multilevel Query Algorithm, wh…

Good luck precomputing all those pairwise shortest paths. Storing the table might not be too bad. But standard algorithms like Floyd-Warshall are O(n^3) in the number of vertices. There are faster algorithms based on fast matrix multiplication but the precomputation time would still be prohibitive. Keeping it up to date would be even worse. The construction of a new highway could require updating the shortest paths f…

Hm, thanks for the nice remark on the game stuff, I kind of like that.

While agree with your primary criticism, I think the principle of locality applies well to this problem. While there are 24 million places (supposedly, never checked that from the paper), I'm positive that most maps queries are served to the areas with higher population density. Therefore, it might make sense to use the look-up table approach for densly populated areas to reduce the search time. (OTOH, the computer scientist in me reminds me that the 7ms might pale in comparison to latency times for mobile phones receiving the map information...)

Re: Mathematics at Google

#43

Post by psykotic »

sb wrote: post #42
psykotic wrote: post #32

Earlier quoted context omitted.

Good luck precomputing all those pairwise shortest paths. Storing the table might not be too bad. But standard algorithms like Floyd-Warshall are O(n^3) in the number of vertices. There are faster algorithms based on fast matrix multiplication but the precomputation time would still be prohibitive. Keeping it up to date would be even worse. The construction of a new highway could require updating the shortest paths f…

Hm, thanks for the nice remark on the game stuff, I kind of like that. While agree with your primary criticism, I think the principle of locality applies well to this problem. While there are 24 million places (supposedly, never checked that from the paper), I'm positive that most maps queries are served to the areas with higher population density. Therefore, it might make sense to use the look-up table approach for…

> Therefore, it might make sense to use the look-up table approach for densly populated areas to reduce the search time.

Yes, that's my favorite way to apply hierarchical path finding. In the two-level path finding system I wrote for my homebrew MUD as a kid, I precomputed all pairwise shortest paths within each zone (a zone had on the order of 100 rooms) and then all pairwise shortest paths between zone-to-zone transitions (a typical zone had around 5 transitions and each transition belongs to two zones). With these tables, here's all you need to do to find a shortest path between a given pair of rooms:

If the two rooms are in the same zone, consult the intra-zone table for their zone and you're done. Otherwise, for both rooms, find the shortest paths to all transitions in their current zone using the intra-zone tables. Let's say there are 5 transitions in both zones. Then for each of the 20 transition pairs, consult the inter-zone table to find the shortest path between them. That gives you a small set of candidate paths (at most 20 in this example) and you pick the shortest among them.

That's 5 + 5 + 20 = 30 fast table lookups and a comparison of 20 numbers to find the shortest path between any pair of rooms.

The storage cost for this is (100 * 5 / 2) * ((100 * 5 / 2) - 1) / 2 bytes ~= 30 kilobytes for the inter-zone table and 100 * (100 * 99 / 2) bytes ~= 500 kilobytes for the intra-zone tables. That wasn't a trivial amount of memory in those days but it wasn't prohibitive either. Compare that to 10,000 * 99,999 / 2 bytes ~= 50 megabytes for directly storing shortest paths between all pairs of rooms. You couldn't store all that in memory and having to read from disk would more than wipe out the 30:1 advantage in the number of lookups versus the two-level approach.

I'm sure you see the analogy with road networks and highways: a transition is like a highway exit, etc. The important point is that there is a way of decomposing the connectivity graph into subgraphs such that only a small number of edges enter and leave each subgraph.

You can see in my calculation that almost all the space is taken up by the intra-zones tables. It would certainly help to compute intra-zone shortest paths on demand with caching, as you suggest.

Re: Mathematics at Google

#44

Post by j2kun »

tlammens wrote: post #35
j2kun wrote: post #21

Earlier quoted context omitted.

At least I gave the source :) And I don't claim I'm any better.

Correction, you added the source after my comment ;) But indeed, you didn't make that claim.

I noticed that I didn't add the source, but when I wrote it I thought the source was self-evident from my mention of "Fry" and the animation style.

Re: Mathematics at Google

#45

Post by j2kun »

SIULHT wrote: post #29
j2kun wrote: post #19

Earlier quoted context omitted.

I would expect them to read it once, and bounce it back to the author saying something along the lines of "Cite your sources, please." That's certainly within Google's power, no?

But if it's on the web, doesn't it belong to Google now?

Aw crap. That was in the ToS wasn't it?

Re: Mathematics at Google

#46

Post by gms »

carlosaguayo wrote: post #24
gms wrote: post #16

Earlier quoted context omitted.

What do you expect them to do? Somehow do an image-similarity search throughout the web for every image used in papers by their employees?

No, but you would expect some kind of seriousness... Universities don't need to run image-similarity through papers published by their students right? Plagiarism is a big thing.

Right. They tell them the policy and make sure it is understood, then they trust them because they cannot police every single image.

Re: Mathematics at Google

#47

Post by psykotic »

dhimes wrote: post #39
psykotic wrote: post #38

Earlier quoted context omitted.

> btw, you've edited your response like 6 times now...everytime I try to reply there's new info in there! Sorry! The lack of preview for HN comments is hell for my iterative writing style.

A lot of us write in an offline text editor and paste the results when we are more-or-less finished (the finish line is an asymptote for people like us!).

Dijkstra is cursing us from beyond the grave.

Re: Mathematics at Google

#48

Post by jacobr »

psykotic wrote: post #38
dxbydt wrote: post #36

Earlier quoted context omitted.

>For road navigation you might precompute the shortest path between every pair of interstate highway exits in the USA like this paper is doing. Oh, so they are populating a lookup table, not for the entire nodeset but just the tuples denoting interstate highways. All I was advocating was a much larger ( and more expensive) lookup table :) btw, you've edited your response like 6 times now...everytime I try to reply th…

> btw, you've edited your response like 6 times now...everytime I try to reply there's new info in there! Sorry! The lack of preview for HN comments is hell for my iterative writing style.

Increase the "delay" in your settings to get a delay until the comment is visible to others.

Re: Mathematics at Google

#49

Post by franze »

pav3l wrote: post #4

Do they still heavily rely on PageRank? With the amount of traffic data Google has, I would expect more statistical approaches based on what users click (rather than graph algorithms based on how the web is linked) to be the backbone for ranking their results.

i'm always disgusted when a googler publishes anything about pagerank. yes, google is still using links as a single in their search result, but the original pagerank paper is from 1998, we can sure as hell be sure that they iterrated/rewrote it a few thousand times since then.

every time a (any) googler now publishes a paper (or presentation) about (the old) page rank a horde of too well paid SEOs is pointing to it for the importance of pagerank, and why linking out is bad, and whatever bullshit (i.e.: later in this thread the based on nothing hypothesis about "nofollow") they come up with. everytime it happens, the SEO bullshit dance starts anew. (in my opinion pagerank is thought-cancer, please see my old TC article for more about this http://techcrunch.com/2010/07/07/startups-linking-to-your-co... )

Re: Mathematics at Google

#50

Post by iamaaronlol »

Muzza wrote: post #30
gms wrote: post #7

Earlier quoted context omitted.

It's one guy who happens to work for Google, rather than the whole company.

Using the same logic, a company can never be said to "do" anything. Everything is (ultimately) done by a real person.

The difference is in whether or not the individual is representing a company.
Post reply on HN