数学2012research.google.com
Google 中的数学
Mathematics at Google
进阶 · 约 35 分钟读完前置知识：线性代数、图论与最短路算法、基础概率论
导读
这是 Google 发布的一份关于「数学在 Google 的应用」的出版物（演讲/讲义材料），梳理了 PageRank、Gmail、Google Maps 等产品背后用到的数学与算法。评论中提到地图部分引用了高速公路层级（highway hierarchies）论文：对美国约 2400 万个地点、2900 万条道路做约 4 小时 15 分钟预处理后，多点查询算法可在 7 毫秒内算出最短路，比 Dijkstra 快约 2000 倍。
HN 关注点：这些数学成果背后的历史脉络（从 Memex、超文本到 PageRank），以及地图最短路算法的实际性能数字是否可信。
HN 评论精选
这几条评论里：支持 1 质疑 2 补充 1
补充梳理 PageRank 的思想谱系：从引文索引、Memex 超文本构想一路到万维网，Google 是两条同源线索的交汇。
看到讨论 PageRank 让我想起一段有趣的轶事：PageRank 的想法源自 Science Citation Index 的成功——它按论文被引用次数来排序。而研究学术引用结构的想法，则来自受 1948 年那篇《As We May Think》启发的人。但那篇文章的主题其实是一个叫 memex 的想象技术，用自动索引系统和微缩胶片实现，这是对超文本的最早描述，启发了后来的多项技术。我印象中第二个成功商用的超文本消费应用就是万维网（第一个是苹果的 HyperCard）。所以 Google 的起点，是把受《As We May Think》启发的一套技术，用在同样受它启发的另一种技术上。文章见链接，注意它写于晶体管发明后一年，但作者当时已有二十年计算经验。
btilly查看英文原文
Seeing PageRank discussed reminds me of a piece of fun trivia. The idea for PageRank came out of the success of the Science Citation Index, which ranks papers according to how often they have been cited. The idea of trying to study the structure of citations in academia came out of people who were inspired by a 1948 essay, As We May Think. But that essay's main topic was an imagined technology called memex, to be implemented with an automated indexing system and microfilm. This technology is the first description of hypertext, which inspired multiple technologies. The second successful consumer application that I'm aware of that used hypertext was the web. (The first was HyperCard from Apple.) Thus Google started as the application of one set of techniques inspired by As We May Think to a technology that was also inspired by As We May Think. See http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/?single_page=true for the essay itself. Do keep in mind that it was written one year after the transistor was invented, but the author already had 2 decades of experience with computing.
质疑对地图算法的性能数字提出（半开玩笑的）质疑：理论上的暴力查表方案是否更优。
文中有一节讲 Google Maps 用到的数学，指向一篇 highway hierarchies 论文：美国有 2400 万个地点、2900 万条道路相连，预处理需要 4 小时 15 分钟；之后用 Multilevel Query Algorithm（Dijkstra 的强化版，比 Dijkstra 快 2000 倍）只需 7 毫秒就能找到两点间最短路。这靠谱吗？2400 万选 2 约是 288 万亿，那干脆做全路径搜索、建一张 288 万亿条目的查找表，存进 HDFS，上面加一层 LRU 缓存，就根本不用跑任何图查询算法了，理应远快于 7 毫秒……只是随口想想。
dxbydt查看英文原文
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, which is a souped up version of Dijkstra and runs 2000 times faster than Dijkstra's Shortest Path algorithm. Is that right ? 24 million choose 2 is 288 trillion, so do an all paths search, then have a lookup table with 288 trillion entries, store that in HDFS, slap an LRU caching layer atop that, and you wouldn't have to run any graph query algorithm at all, so should be able to do much better than 7 ms ... just thinking out loud.
支持认为这份材料是把抽象数学与日常生活联系起来的好教学素材。
这是一份很棒的出版物！我兼职做数学辅导，孩子们总问数学在「现实生活」里到底用在哪。而孩子们都熟悉 Google，这份材料应该能引起他们的共鸣。
cjdrake查看英文原文
This is a fantastic publication! I do some part-time mathematics tutoring, and kids are always wondering where math is used in "real life". Since kids are all familiar with Google, this should resonate with them.
质疑指出幻灯片中的图疑似未注明出处地取自他人博客。
看那页标题为 Gmail（5）的幻灯片，把里面的图和我的博客文章里的第一张图对比一下（链接）。这说明 Google 和所有人一样，也会不加署名地拿别人的内容。
j2kun查看英文原文
Look at the slide entitled Gmail (5), and compare the picture with the first graph on my blog post http://jeremykun.wordpress.com/2011/08/11/the-perceptron-and-all-the-things-it-cant-perceive/ It just goes to show, Google steals content without attribution just like everyone else.
历次讨论
- 2012Hacker News 讨论帖188 分 · 50 评
同领域还值得读
一种新的相关系数
A New Coefficient of Correlation
提出了一种新的相关性系数（由 Sourav Chatterjee 提出），能够检测变量之间任意形式（不限于线性）的相关关系，且计算简单高效，主要基于排序和距离计算。
数学2021 · 682 分 · 158 评 · 引用 1进阶 · 约 60 分钟编辑精选数学的两种文化
The Two Cultures of Mathematics (2000)
这是数学家 Timothy Gowers 于 2000 年发表的一篇随笔，他把数学研究大致分成两种文化：一类是“解题者”，热衷于攻克具体难题、发展技巧（如组合数学）；另一类是“理…
数学2009 · 307 分 · 102 评入门 · 约 35 分钟编辑精选重新定义统计显著性
Redefine statistical significance
提议将统计显著性阈值从常用的 p<0.05 收紧到 p<0.005，以降低假阳性率、缓解可重复性危机。
数学2017 · 303 分 · 114 评入门 · 约 45 分钟编辑精选统计建模：两种文化（2001）
Statistical Modeling: The Two Cultures (2001)
讨论统计学中两种建模文化：一种假设数据由某种随机模型生成，侧重推断与系数解释；另一种把数据生成机制视为未知，侧重预测精度，主张使用算法建模。
数学2015 · 254 分 · 36 评进阶 · 约 60 分钟编辑精选通信的数学理论 (1948)
A Mathematical Theory of Communication (1948)
这是香农 1948 年的经典论文《通信的数学理论》，奠定了信息论的基础。
数学2016 · 169 分 · 53 评入门 · 约 90 分钟编辑精选