支持 google/bing 地图的数据结构
我想知道像 google/bing 地图这样的应用程序中的数据结构是什么。为什么搜索路线时返回结果这么快？ 使用什么样的算法来确定这些信息？
谢谢
I was wondering what the data structure is in an application like google/bing maps. How is it that the results are returned so quickly when searching for directions?
what kind of algorithms are being used to determine this information?
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您的问题有两个部分：
对此，我想补充另一个问题：
我将尝试按顺序解决每个问题。请注意，我不为 Google 地图或 Bing 团队工作，因此很明显，此信息可能不完全准确。我的这一点基于从一门关于数据结构和算法的优秀计算机科学课程中获得的知识。
Ans 1) 该图存储在边加权有向图中。地图上的位置是“顶点”，从一个位置到另一位置（从一个顶点到另一个顶点）的路径是“边”。
很明显，由于可能有数百万个顶点和一个数量级的边，所以真正有趣的是这个边加权有向图的表示。
我想说这将由某种邻接列表来表示，我这么说的原因是因为，如果你想象一张地图，它本质上是一个稀疏图。从一个地点到另一个地点的方法只有几种。想想你的房子吧！有多少条路（在我们的例子中是边）通向它？邻接表适合表示稀疏图，邻接矩阵适合表示稠密图。
当然，即使我们能够在内存中有效地表示稀疏图，但考虑到顶点和边的数量巨大，也不可能将所有内容一次性存储在内存中。因此，我会想象下面有某种流媒体库。
打个比方，如果你曾经玩过《魔兽世界》/《Syrim》/《GTA》等开放世界游戏，你会发现在很大程度上，没有加载屏幕。但很明显，不可能一次性将所有内容都放入内存中。因此，使用四叉树和视锥体剔除算法的组合，这些游戏能够动态加载资源（地形、精灵、网格等）。
我会想象类似的东西，但是对于图表。我没有对这个特定方面进行太多思考，但是为了构建一个非常基本的系统，人们可以想象一个内存数据库，它们在运行时根据需要查询并添加/删除图中的顶点和边。这给我们带来了另一个有趣的观点。由于需要在运行时删除和添加顶点和边，因此邻接列表的经典实现不会削减它。
在经典的实现中，我们只是将一个 List（Java 中的 Vector）存储在数组的每个元素中：Adj[]。我可以想象，用链表代替 Adj[] 数组，用二叉搜索树代替 List[Edge]。二叉搜索树将有助于 O(log N) 插入和删除节点。这是非常理想的，因为在 List 实现中，加法的复杂度为 O(1)，删除的复杂度为 O(N)，而当您处理数百万条边时，这是令人望而却步的。
这里要注意的最后一点是，在您实际开始导航之前，“没有”图表。由于可能有数百万用户，因此为每个人维护一张巨大的图是没有意义的（仅由于内存空间需求，这是不可能的）。我想当您统计导航过程时，会为您创建一个图表。很明显，由于您从位置 A 开始并转到位置 B（以及之后可能的其他位置），因此专门为您创建的图不应占用大量内存（假设流架构已到位）。
Ans 2）这是一个非常有趣的问题。解决这个问题最基本的算法是 Dijkstra 路径查找算法。存在更快的变体，例如 A*。我认为 Dijkstra 足够快，如果它可以与上面讨论的流架构正常工作的话。 Dijkstra 使用与 V 成比例的空间和与 E lg V 成比例的时间，这是非常好的图形，特别是对于稀疏图。请记住，如果流式架构尚未确定，V 和 E 将爆炸，Dijkstra 的空间和运行时要求将使其令人望而却步。
Ans 1) 流媒体问题：不要将此问题与上面讨论的流媒体架构混淆。这基本上是在问如何实现无缝缩放。
实现此目的的一个很好的算法是四叉树算法（您可以将其推广到 n 树）。您可以将较粗糙的图像存储在树的较高位置，并在向下遍历树时存储更高分辨率的图像。这实际上就是 KML（Keyhole）通过其映射算法所做的事情。 Keyhole 是一家公司，多年前就与 NVIDIA 合作开发了第一个类似“Google Earth”的软件。
四叉树剔除的灵感来自现代 3D 游戏，它用于快速剔除场景中不在视锥体中的部分。
为了进一步澄清这一点，想象一下您正在从高处查看美国地图。在此级别，您基本上将地图分为 4 个部分，并使每个部分成为四叉树的子级。
现在，当您放大时，您会放大其中一个部分（很明显，您可以在中心右侧放大，这样您的缩放实际上会触及所有 4 个部分，但为了简单起见，假设您放大了其中一个部分）部分）。因此，当您放大某个部分时，您会遍历该部分的 4 个子部分。这 4 个子项包含其父项的更高分辨率数据。然后，您可以继续缩小，直到看到一组叶子，其中包含最高分辨率的数据。为了实现从一种分辨率到下一种分辨率的“无缝”跳跃，可以利用模糊和淡入淡出效果的组合。
作为这篇文章的后续内容，我将尝试添加我在此处提出的许多概念的链接。
There are two parts to your question:
To this, I would add another question:
I will attempt to address each question in order. Do note, that I do not work for the Google Maps or the Bing team, so quite obviously, this information might not be completely accurate. I am basing this off of the knowledge gained from a good CS course about data structures and algorithms.
Ans 1) The map is stored in an Edge Weighted Directed Graph. Locations on the map are Vertices and the path from one location to another (from one vertex to another) are the Edges.
Quite obviously, since there can be millions of vertices and an order of magnitude more edges, the really interesting thing would be the representation of this Edge Weighted Digraph.
I would say that this would be represented by some kind of Adjacency List and the reason I say so is because, if you imagine a map, it is essentially a sparse graph. There are only a few ways to get from one location to another. Think about your house! How many roads (edges in our case) lead to it? Adjacency Lists are good for representing sparse graphs, and adjacency matrix is good for representing dense graphs.
Of course, even though we are able to efficiently represent sparse graphs in memory, given the sheer number of Vertices and Edges, it would be impossible to store everything in memory at once. Hence, I would imagine some kind of a streaming library underneath.
To create an analogy for this, if you have ever played an open-world game like World of Warcraft / Syrim / GTA, you will observe that to a large part, there is no loading screen. But quite obviously, it is impossible to fit everything into memory at once. Thus using a combination of quad-trees and frustum culling algorithms, these games are able to dynamically load resources (terrain, sprites, meshes etc).
I would imagine something similar, but for Graphs. I have not put a lot of thought into this particular aspect, but to cook up a very basic system, one can imagine an in memory database, which they query and add/remove vertices and edges from the graph at run-time as needed. This brings us to another interesting point. Since vertices and edges need to be removed and added at run-time, the classic implementation of Adjacency List will not cut it.
In a classic implementation, we simply store a List (a Vector in Java) in each element of an array: Adj[]. I would imagine, a linked list in place of the Adj[] array and a binary search tree in place of List[Edge]. The binary search tree would facilitate O(log N) insertion and removal of nodes. This is extremely desirable since in the List implementation, while addition is O(1), removal is O(N) and when you are dealing with millions of edges, this is prohibitive.
A final point to note here is that until you actually start the navigation, there is "no" graph. Since there can be million of users, it doesn't make sense to maintain one giant graph for everybody (this would be impossible due to memory space requirement alone). I would imagine that as you stat the navigation process, a graph is created for you. Quite obviously, since you start from location A and go to location B (and possibly other locations after that), the graph created just for you should not take up a very large amount of memory (provided the streaming architecture is in place).
Ans 2) This is a very interesting question. The most basic algorithm for solving this problem would be Dijkstra Path Finding algorithm. Faster variations such as A* exist. I would imagine Dijkstra to be fast enough, if it could work properly with the streaming architecture discussed above. Dijkstra uses space proportional to V and time proportional to E lg V, which are very good figures, especially for sparse graphs. Do keep in mind, if the streaming architecture has not been nailed down, V and E will explode and the space and run-time requirements of Dijkstra will make it prohibitive.
Ans 1) Streaming question: Do not confuse this question with the streaming architecture discussed above. This is basically asking how the seamless zoom is achieved.
A good algorithm for achieving this is the Quad Tree algorithm (you can generalize this to n-tree). You store coarser images higher up in the tree and higher resolution images as you traverse down the tree. This is actually what KML (Keyhole) did with its mapping algorithm. Keyhole was a company that partnered with NVIDIA many years back to produce one of the first "Google Earth" like softwares.
The inspiration for Quad Tree culling, comes from modern 3D games, where it is used to quickly cull away parts of the scene which is not in the view frustum.
To further clarify this, imagine that you are looking at the map of USA from really high up. At this level, you basically split the map into 4 sections and make each section a child of the Quad Tree.
Now, as you zoom in, you zoom in on one of the sections (quite obviously you can zoom right in the center, so that your zoom actually touches all 4 sections, but for simplicity's sake, lets say you zoom in on one of the sections). So when you zoom in to one section, you traverse the 4 children of that section. These 4 children contain higher resolution data of its parent. You can then continue to zoom down till you hit a set of leaves, which contain the highest resolution data. To make the jump from one resolution to the next "seamless" a combination of blur and fading effects can be utilized.
As a follow-up to this post, I will try to add links to many of the concepts I put in here.
对于此类应用程序，您需要某种数据库来表示地图要素及其之间的连接，然后需要：
对于 1，一个示例是 R-tree 数据结构。
对于 2，您需要一个图搜索算法，例如 A*。
For this sort of application, you would want some sort of database to represent map features and the connections between them, and would then need:
For 1, an example would be the R-tree data structure.
For 2, you need a graph search algorithm, such as A*.
从谷歌作者那里查找一篇关于高速公路维度的论文。这个想法是预先计算重要节点之间的最短路径，然后通过这些节点路由所有内容。从洛杉矶到芝加哥，除了在两端的高速公路上下车外，您不会使用住宅区街道。
Look up a paper about Highway Dimension from google authors. The idea is to precompute the shortest path between important nodes and then route everything through those. You are not going to use residential streets to go from LA to Chicago save for getting on and off the freeway at both ends.
我不确定内部数据结构，但它可能是某种基于二维坐标的树结构，仅显示一定数量的级别。这些级别将对应于缩放系数，因此您可以忽略下面的微不足道的事物，例如低于当前级别的 5 个级别以及高于当前级别的事物。
无论其结构如何，您都可以按照以下方式使用它：
http://code .google.com/apis/maps/documentation/reference.html
I'm not sure of the internal data structure, but it may be some kind of 2D coordinate based tree structure that only displays a certain number of levels. The levels would correspond to zoom factors, so you could ignore as insignificant things below, say, 5 levels below the current level, and things above the current level.
Regardless of how it's structured, here's how you can use it:
http://code.google.com/apis/maps/documentation/reference.html
我认为这是一个计算几何问题。当您单击地图中的特定坐标并使用该信息时，可以获得该位置的纬度和经度。根据经纬度和缩放级别，可以识别该地点。
一旦确定了这两个地点，您唯一的问题就是确定最近的路线。现在这个问题是找到两点之间的最短路径，它们之间有多边形块（对应于不包含道路的地方），唯一可能的连接是道路。这是一个已知问题，并且存在有效的算法来解决这个问题。
我不确定这是否是谷歌正在做的事情，但我希望他们在这些方面做点什么。
我这个学期正在学习计算几何。这是课程链接： http://www.ams.sunysb .edu/~jsbm/courses/545/ams545.html。如果您有兴趣，请查看它们。
I would think of it as a computational geometry problem. When you click on a particular coordinate in the map and using that information, can get the latitude and longitude of that location. Based on the latitude and longitude and the level of zoom, the place can be identified.
Once you have identified the two places, the only problem for you is to identify the nearest route. Now this problem is finding the shortest path between two points, having polygon blocks between them(which correspond to the places which contains no roads) and the only possible connections are roads. This is a known problem and efficient algorithms exist to solve this.
I am not sure if this is what google is doing, but I hope they do something on these lines.
I am taking computational geometry this semester. Here is the course link: http://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html. Check them if you are interested.
致用户：XHTML/CSS/Javascript。就像任何网站一样。
在服务器上：谁知道呢？这里有 Google 开发人员吗？它肯定不是 PHP 或 ASP.net...
因为谷歌花费了数年时间、人力和数百万美元来构建架构以获得最快的服务器反应时间？
旅程规划算法。
To the user: XHTML/CSS/Javascript. Like any website.
On the server: who knows? Any Google devs around here? It certainly isn't PHP or ASP.net...
Because Google spent years, manpower and millions of dollars on building up the architecture to get the fastest server reaction time possible?
A journey planner algorithm.