Me preguntaba cuál es la estructura de datos en una aplicación como google/bing maps. ¿Cómo es que los resultados se devuelven tan rápido cuando se buscan instrucciones? ¿Qué tipo de algoritmos se están utilizando para determinar esta información?estructura de datos para admitir google/bing maps
gracias
me preguntaba lo que los datos estructura está en una aplicación como mapas Google/Bing.
Para el usuario: XHTML/CSS/Javascript. Como cualquier sitio web
En el servidor: ¿quién sabe? Cualquier desarrollador de Google por aquí? Ciertamente, no es PHP o ASP.net ...
¿Cómo es que los resultados se devuelven tan rápidamente en la búsqueda de direcciones ?
¿Porque Google gastó años, mano de obra y millones de dólares en construir la arquitectura para obtener el tiempo de reacción del servidor más rápido posible?
¿Qué tipo de algoritmos se están utilizando para determinar esta información?
No estoy seguro de la estructura de datos interna, pero puede ser algún tipo de estructura de árbol 2D basado en que sólo muestra un cierto número de niveles de coordenadas. Los niveles corresponderían a factores de zoom, por lo que podría ignorar cosas insignificantes a continuación, por ejemplo, 5 niveles por debajo del nivel actual, y cosas por encima del nivel actual.
Independientemente de cómo se estructura, así es como se puede usar:
http://code.google.com/apis/maps/documentation/reference.html
Para este tipo de aplicación, usted quiere algún tipo de base de datos para representar las características del mapa y las conexiones entre ellos, y necesitaría entonces:
Para 1, un ejemplo sería la estructura de datos R-tree.
Para 2, es necesario un algoritmo de búsqueda gráfica, tales como A*.
Lo consideraría un problema de geometría computacional. Al hacer clic en un determinado coordenadas en el mapa y el uso de esa información, se puede obtener la latitud y la longitud de esa ubicación. Según la latitud y la longitud y el nivel de zoom, el lugar puede identificarse.
Una vez que haya identificado los dos lugares, el único problema para usted es identificar la ruta más cercana. Ahora este problema es encontrar la ruta más corta entre dos puntos, tener bloques de polígono entre ellos (que corresponden a los lugares que no contienen carreteras) y las únicas conexiones posibles son las carreteras. Este es un problema conocido y existen algoritmos eficientes para resolver esto.
No estoy seguro de si esto es lo que está haciendo Google, pero espero que hagan algo en estas líneas.
Estoy tomando la geometría computacional este semestre. Aquí está el enlace del curso: http://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html. Compruébalos si estás interesado.
Busque un artículo sobre Highway Dimension de autores de google. La idea es calcular previamente la ruta más corta entre nodos importantes y luego enrutar todo a través de ellos. No utilizará calles residenciales para ir de LA a Chicago, salvo para subir y bajar de la autopista en ambos extremos.
Hay dos partes a su pregunta:
Para esto, me gustaría añadir otra pregunta:
Intentaré resolver cada pregunta en orden. Tenga en cuenta que no trabajo para Google Maps o para el equipo de Bing, así que, obviamente, esta información puede no ser completamente precisa. Estoy basando esto en el conocimiento obtenido de un buen curso de CS sobre estructuras de datos y algoritmos.
Resp. 1) El mapa está almacenado en un gráfico dirigido ponderado por el borde. Las ubicaciones en el mapa son Vértices y la ruta de una ubicación a otra (de un vértice a otro) son los bordes.
Obviamente, dado que puede haber millones de vértices y un orden de magnitud más de bordes, lo realmente interesante sería la representación de este Digrafio con borde Edge.
Yo diría que esto estaría representado por algún tipo de Lista de adyacencia y la razón por la que digo es porque, si imaginas un mapa, es esencialmente un gráfico disperso. Solo hay algunas maneras de ir de un lugar a otro. ¡Piensa en tu casa! ¿Cuántas carreteras (bordes en nuestro caso) llevan a eso? Las listas de adyacencia son buenas para representar gráficos dispersos, y la matriz de adyacencia es buena para representar gráficos densos.
Por supuesto, a pesar de que podemos representar de manera eficiente los gráficos dispersos en la memoria, dada la gran cantidad de vértices y bordes, sería imposible almacenar todo en la memoria a la vez. Por lo tanto, me imagino algún tipo de biblioteca de transmisión por debajo.
Para crear una analogía para esto, si alguna vez ha jugado un juego de mundo abierto como World of Warcraft/Syrim/GTA, observará que, en gran parte, no hay pantalla de carga. Pero, obviamente, es imposible poner todo en la memoria a la vez.Por lo tanto, utilizando una combinación de cuatrimotos y algoritmos de eliminación de triturado de troncos, estos juegos son capaces de cargar dinámicamente recursos (terreno, sprites, mallas, etc.).
Me imagino algo similar, pero para Gráficos. No he pensado mucho en este aspecto en particular, pero para cocinar un sistema muy básico, uno puede imaginar una base de datos en memoria, que consulta y agrega/elimina vértices y bordes del gráfico en tiempo de ejecución según sea necesario. Esto nos lleva a otro punto interesante. Como los vértices y bordes deben eliminarse y agregarse en el tiempo de ejecución, la implementación clásica de la Lista de adyacencia no lo cortará.
En una implementación clásica, simplemente almacenamos una Lista (un Vector en Java) en cada elemento de una matriz: Adj []. Me imagino, una lista vinculada en lugar de la matriz Adj [] y un árbol de búsqueda binaria en lugar de List [Edge]. El árbol de búsqueda binario facilitaría la inserción O (log N) y la eliminación de nodos. Esto es extremadamente deseable ya que en la implementación de la Lista, mientras que la adición es O (1), la eliminación es O (N) y cuando se trata de millones de bordes, esto es prohibitivo.
Un último punto a tener en cuenta aquí es que hasta que realmente inicie la navegación, hay un "no" gráfico. Dado que puede haber un millón de usuarios, no tiene sentido mantener un gráfico gigante para todos (esto sería imposible debido solo al requisito de espacio de memoria). Me imagino que a medida que estableces el proceso de navegación, se crea un gráfico para ti. Obviamente, como usted comienza desde la ubicación A y va a la ubicación B (y posiblemente a otras ubicaciones después de eso), el gráfico creado para usted no debe ocupar una gran cantidad de memoria (siempre que la arquitectura de transmisión esté en su lugar).
Ans 2) Esta es una pregunta muy interesante. El algoritmo más básico para resolver este problema sería el algoritmo Dijkstra Path Finding. Existen variaciones más rápidas, como A *. Me imagino que Dijkstra será lo suficientemente rápido, si pudiera funcionar correctamente con la arquitectura de transmisión que mencioné anteriormente. Dijkstra usa un espacio proporcional a V y un tiempo proporcional a E lg V, que son figuras muy buenas, especialmente para gráficos dispersos. Tenga en cuenta que, si la arquitectura de transmisión no se ha definido, V y E explotarán y el espacio y los requisitos de tiempo de ejecución de Dijkstra lo harán prohibitivo.
Resp. 1) Transmitiendo la pregunta: No confunda esta pregunta con la arquitectura de transmisión que se discutió anteriormente. Esto es básicamente preguntar cómo se logra el zoom sin interrupciones.
Un buen algoritmo para lograr esto es el algoritmo Quad Tree (puede generalizar esto a n-tree). Almacena imágenes más gruesas en el árbol e imágenes de mayor resolución mientras recorre el árbol. Esto es realmente lo que KML (Keyhole) hizo con su algoritmo de mapeo. Keyhole fue una compañía que se asoció con NVIDIA muchos años atrás para producir uno de los primeros softwares "Google Earth".
La inspiración para el descarte de Quad Tree proviene de los modernos juegos 3D, donde se utiliza para eliminar rápidamente partes de la escena que no están en la vista triturada.
Para aclarar más esto, imagina que estás mirando el mapa de EE. UU. Desde muy arriba. En este nivel, básicamente divide el mapa en 4 secciones y convierte cada sección en un elemento secundario del Quad Tree.
Ahora, a medida que acercas, acercas una de las secciones (obviamente, puedes acercar el centro, para que tu zoom toque realmente las 4 secciones, pero por simplicidad, digamos que acercas el zoom en una de las secciones). Por lo tanto, cuando se acerca a una sección, recorre los 4 niños de esa sección. Estos 4 niños contienen datos de mayor resolución de su padre. Luego puede continuar reduciendo la imagen hasta que llegue a un conjunto de hojas, que contienen los datos de mayor resolución. Para hacer el salto de una resolución a la siguiente "perfecta", se puede utilizar una combinación de desenfoque y desvanecimiento.
Como seguimiento de esta publicación, intentaré agregar enlaces a muchos de los conceptos que incluí aquí.
Muhammad: si quiere agregar su (s) dirección (es) de correo electrónico en alguna parte, le sugiero que la agregue a su perfil. También parece que tiene dos identidades SO, que lo confundirán a usted y a otras personas. –
Jon: Tienes razón, creé accidentalmente dos perfiles. ¿Cómo puedo vincular los dos? Obtuve la insignia de "Profesor" en mi perfil no registrado: | –
Le sugiero que envíe un correo electrónico a [email protected] explicando su problema. –
Whoa. Ese artículo de Wikipedia tiene Problemas Múltiples. –