Computations in Google Map

Comment:

Why Google cannot store the complete map easily? For instance, for 1000 nodes, we need to store just around 500 × 999 units of data.

Follow-up:

While the analysis for 1000 nodes is correct, when you scale it up to 1 million nodes, the data storage becomes very big. Indeed, the file size of the street map for the U.S.A. is around 9GB (for details, please visit: www.esri.com). Thus, for the entire world with all the details (e.g., restaurants, shops, timing data, etc.), the data size would be even larger. Of course, Google still can “easily” handle all these. But to run an algorithm (e.g., Dijkstra) over such a large piece of data is still quite daunting. That is why we really have to use the “pre-compute-then-table-lookup” approach as far as we can.

Comment:

What kind of programming language is used for implementing MapQuest and Google Map?

Follow-up:

For high-performance applications, I strongly believe that their engineers are still relying on the C language. However, for other system components such as user interface, Web, etc., they use a variety of other tools (e.g., Java, Perl, Python, etc.).

Links of Readings

Required Reading

• Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266(5187), 1021-1024.
• Benenson, Y., Gil, B., Ben-Dor, U., Adar, R., & Shapiro, E. (2004). An autonomous molecular computer for logical control of gene expression. Nature, 429(6990), 423-429.
• Conry-Murray, A. (2007). 5 keys to social networking success. Informationweek.
• Google. (2009). Google Flu Trend
• Google. (2009). Reducing our footprint. Going Green at Google.
• Hölzle, U. (2009). Powering a Google search. Official Google Blog.
• Himanen, P. (2001). The hacker ethic, and the spirit of the information age (1st ed.). New York: Random House.(via HKU Library)
• IBM Research. Carbon nanotubes.
• Kling, R. (1980). Computing people. Society, 17(2), 14.
• Layton, J. (2009). How MapQuest works. How Stuff Works.
• Messmer, E. (2007). Quantum cryptography to secure ballots in Swiss election. Network World.
• NVDIA. (2009). Graphics processing unit (GPU).
• O’Brien, M. (2006). How MapQuest Works.
• Schneier, B. (2009). Crypto-Gram Newsletter.
• United States Department of Energy. (2009). High performance computing.
• Watson, C. (1994). An image processing tutorial.
• Wing, J. (2006). Computational thinking. Communications of the ACM, 49(3), 33-35.

Recommended Reading 

• Feynman, R., Hey, A., & Allen, R. (2000). Feynman lectures on computation. Cambridge, MA: Perseus Books.
• Schneier, B. (2004). Secrets and lies: Digital security in a networked world. Indianapolis, Ind.: Wiley.
• Wing, J. M. (2008). Five deep questions in computing. Communications of the ACM, 51(1), 58-60.