Geek Answers Handbook

Google / bing map data structure

I was wondering what data structure is in an application like google / bing maps. How is it that the results come back so quickly when searching for routes? What algorithms are used to determine this information?

thanks

+5
source share
6 answers

There are two parts to your question:

  • What data structure is used to store map information.
  • What algorithm is used to “navigate” from source to destination.

For this, I would add one more question:

  • Google/Bing "" . , , , .

. , Google Bing, , . , CS .

Ans 1) . - , ( ) - .

, , Edge Weighted Digraph.

, - Adjacency List, , , , , , , , . . ! ( ) ? , .

, , , , . , - .

, - , ​​ World of Warcraft/Syrim/GTA, , . , . , , (, , ..).

, . , , , , / . . , Adjacency List .

( Java) : Adj []. , Adj [] List [Edge]. O (log N). , List, O (1), O (N), , .

, , , "". , ( - ). , , . , A B (, , ), ( , ).

Ans 2) . Dijkstra Path Finding. , A *. , Dijkstra , , . , V, , E lg V, , . , , V E , Dijkstra .

Ans 1) : . , .

Quad Tree ( n-). . KML (Keyhole) . Keyhole , NVIDIA, "Google Earth", .

Quad Tree , 3D-, , .

, , . 4 Quad.

, , ( , , 4 , , , ). , , 4 . 4 . , , . "", .

, .

+7

, - , :

  • , 2D-;
  • (, ).

1 R-tree.

2 , A *.

+1

. , . , .

, - . , ( , ), . , .

, , Google, , - .

. : http://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html. , .

0

google. , . , - , , .

0

, google/bing.

To user: XHTML / CSS / Javascript. Like any site.

On the server: who knows? Are any Google developers here? This, of course, is not PHP or ASP.net ...

How is it that the results returned so quickly when they were looking for directions?

Since Google spent years, labor, and millions of dollars building an architecture to get the fastest server response time?

What algorithms are used to determine this information?

A travel planning algorithm.

-4
source

More articles:


All Articles