Ventajas de los árboles R en comparación con geohashes

18

Las geohashes se están utilizando ampliamente en productos como: Lucene, mongodb, etc. y se han convertido en una de las tecnologías más importantes de la actualidad.

¿Han reemplazado los Geohashes a los viejos árboles R o los árboles R tienen alguna ventaja en comparación con los Geohashes?

Jannat Arora
fuente

Respuestas:

11

Geohash es una forma muy simple y efectiva de indexar entidades espaciales, particularmente entidades puntuales. Las características de línea y polígono son un poco más difíciles de indexar, pero se pueden hacer. Geohash es una cuadrícula estática jerárquica de tamaño fijo, superpuesta sobre la superficie de la tierra. Las celdas de la cuadrícula del mismo nivel jerárquico no se superponen. R-Tree es una cuadrícula dinámica cuya ubicación y tamaño de celda cambian según las características que están indexando. R-Tree indexa las características de los cuadros delimitadores y las celdas cambian cada vez que inserta y actualiza datos. Geohash se usa principalmente para indexar entidades de puntos y las celdas no cambian con cada inserción y actualización de datos. Las celdas Geohash no adoptan las características como con R-tree.

Algunas de las ventajas de geohash (en comparación con r-tree) podrían ser:

  • implementación fácil
  • sin degradación del rendimiento con un número creciente de características
  • búsquedas de proximidad (parcialmente verdaderas)

Algunas de las desventajas de geohash (en comparación con r-tree) podrían ser:

  • precisión arbitraria de la cuadrícula
  • más difícil de indexar (y consultar) características de línea y polígono
  • el tamaño del índice podría ser grande con algunos métodos de indexación de líneas y polígonos
  • según las especificaciones, solo se puede usar con el sistema de coordenadas de longitud / latitud, aunque el mismo método podría aplicarse a otros sistemas de coordenadas también

Esos productos (bases de datos) que mencionó usan geohash porque geohash se usa principalmente para indexar puntos y hay muchas aplicaciones que necesitan dicha función. Las líneas y los polígonos no se usan con tanta frecuencia (a excepción de las aplicaciones SIG, por supuesto), entonces, ¿por qué molestarse con eso? Otra razón, por supuesto, es la facilidad de implementación. Geohash convierte las coordenadas bidimensionales en valores unidimensionales. Esto se llama reducción dimensional. El valor unidimensional es fácil de indexar con el árbol b estándar que se usa principalmente en esos productos.

Tengo que mencionar que existen algoritmos similares a geohash, pero la mayoría de ellos son propietarios y requieren licencia. Geohash es de dominio público. Esta podría ser también la razón de un uso tan grande en los últimos años.

Probablemente haya otras ventajas y desventajas, pero estas son las primeras que me vienen a la mente. Espero que mi explicación ayude un poco.

Mario Miler
fuente
No entendí por qué las geohashes dan precisión arbitraria de la cuadrícula. ¿Puedes explicar con un ejemplo? Te agradeceré lo mismo.
Jannat Arora
1
Geohash convierte las coordenadas de longitud y latitud en una cadena unidimensional. La longitud de esta cadena está directamente vinculada a la precisión convertida de la coordenada. Por favor, mire esto unterbahn.com/2009/11/… . Puede ver cómo la longitud de una cadena de geohash está vinculada a la precisión. Básicamente, geohash convierte el punto en un área de polígono (una cuadrícula geohash). El tamaño de esta área de polígono depende de la longitud de la cadena de geohash y de la latitud con la que está calculando el geohash.
Mario Miler