使用哪种GEO实现数百万点

Question

我试图找出使用哪个GEO实现来找到基于long/lat到某一点的最近点.如果不是数十亿不同的纬度/经度点,我需要比较数百万.我一直在寻找许多不同的实现来完成我需要完成的工作.我已经研究过Postgis(看起来非常受欢迎并且表现良好),Neo4J(图形数据库对我来说是一个新概念,我不确定它们是如何实现的),AWS dynamodb geohash(Scales非常好,但只有库是用Java,我希望在node.js中编写一个库等,但无法弄清楚哪个会表现最好.我纯粹关注与众多功能相对应的性能.我需要的是将一个点与所有点进行比较并找到最接近的(读取操作),并且还能够快速更改数据库中的一个点(写入操作).任何人都可以根据这些要求建议一个良好的实施

Answer 1

PostGIS具有多种地理位置功能.如果你的字符串足够长,搜索会变得更快(每个盒子的碰撞次数减少+ 8个邻居),但插入新点时geohash生成速度会变慢.

问题是你想要的准确程度.在纬度增加时,纬度/长度"距离"恶化,因为经度从赤道约110km收缩到极点0,而纬度总是约110km.在45度的中纬度,经度接近79km,距离误差为2(sqr(110/79)).在纬度/长度对之间给出真正距离的球面距离计算起来非常昂贵(大量的三角函数正在进行)然后你的地理位置不起作用(除非你将所有点转换为平面坐标).

可能有效的解决方案如下:

• CREATE INDEX hash8 ON tablename(substring(hash_column FROM 1 FOR 8)).这为您提供了两倍于分辨率的框的索引,这有助于查找点并减少搜索相邻哈希框的需要.
• 在INSERT某一点上,使用PostGIS计算其长度为9(大约10米分辨率)的geohash到hash_column中.你可以在BEFORE INSERT TRIGGER这里使用.

在一个功能:

• 给定一个点,通过查找geohash值缩短为8个字符等于给定点8-char geohash的所有点(因此上面的索引)来找到最近的点.
• 使用球面坐标计算到每个遇到点的距离,保持最近点.但由于您只是在寻找最近的点(至少在初始阶段),所以不要使用球面坐标搜索距离,而是使用下面的优化,这样可以使搜索速度更快.
• 计算给定点是否接近由8-char geohash确定的框的边缘而不是最接近的计算点.如果是这样,请在其8个邻居的所有点上使用7-char geohash重复此过程.这可以通过计算到各个盒子侧面和角落的距离并仅评估相关的邻居哈希盒来高度优化; 我留给你修补.

无论如何,这不会特别快.如果你真的想要达到数十亿的积分,你可能会想到聚类,它有一个相当"自然"的地理分析解决方案(substring(hash_column FROM 1 FOR 2)例如,打破你的桌面,给你四个象限).只需确保您考虑跨境搜索.

可以相当快地进行两次优化:

首先,"标准化"您的球面坐标(意思是:通过增加纬度来补偿经度减小的长度),以便您可以使用"伪笛卡尔"方法搜索最近的点.这只有在点靠近时才有效,但由于你使用了很多点,这应该不是问题.更具体地说,这适用于长度为6或更长的geohash框中的所有点.

假设WGS84椭球(用于所有GPS设备),地球的主轴(a)为6,378,137米,椭圆度(e2)为0.00669438.经度的二分之一长度为

longSec := Pi * a * cos(lat) / sqrt(1 - e2 * sqr(sin(lat))) / 180 / 3600

要么

longSec := 30.92208078 * cos(lat) / sqrt(1 - 0.00669438 * sqr(sin(lat)))

对于纬度的第二个:

latSec := 30.870265 - 155.506 * cos(2 * lat) + 0.0003264 + cos(4 * lat)

使局部坐标系"平方"的校正因子是将经度值乘以longSec/latSec.

其次,由于您正在寻找最近的点,因此不要搜索距离,因为计算上昂贵的平方根.相反,如果你愿意的话,搜索平方根内的项,平方距离,因为它具有选择最近点的相同属性.

在伪代码中:

CREATE FUNCTION nearest_point(pt geometry, ptHash8 char(8)) RETURNS integer AS $$
DECLARE
  corrFactor double precision;
  ptLat    double precision;
  ptLong     double precision;
  currPt     record;
  minDist    double precision;
  diffLat    double precision;
  diffLong   double precision;
  minId      integer;
BEGIN
  minDist := 100000000.; -- a large value, 10km (squared)
  ptLat := ST_Y(pt);
  ptLong := ST_X(pt);
  corrFactor := 30.92208078 * cos(radians(ptLat)) / (sqrt(1 - 0.00669438 * power(sin(radians(ptLat)), 2)) *
                (30.870265 - 155.506 * cos(2 * radians(ptLat)) + 0.0003264 + cos(4 * radians(ptLat))));
  FOR currPt IN SELECT * FROM all_points WHERE hash8 = ptHash8
  LOOP
    diffLat := ST_Y(currPt.pt) - ptLat;
    diffLong := (ST_X(currPt.pt) - ptLong) * corrFactor; -- "square" things out
    IF (diffLat * diffLat) < (minDist * diffLong * diffLong) THEN -- no divisions here to speed thing up a little further
      minDist := (diffLat * diffLat) / (diffLong * diffLong); -- this does not happen so often
      minId := currPt.id;
    END IF;
  END LOOP;
  IF minDist < 100000000. THEN
    RETURN minId;
  ELSE
    RETURN NULL;
  END IF;
END; $$ LANGUAGE PLPGSQL STRICT;

不用说,这在C语言函数中要快得多.另外,不要忘记进行边界检查以查看是否需要搜索相邻的geohash框.

顺便说一句,"空间纯粹主义者"不会在8-char geohash上索引并从那里搜索; 相反,他们会从9-char哈希开始,然后从那里向外工作.但是,您的初始哈希框中的"未命中"(因为没有其他点或您接近哈希框侧)是昂贵的,因为您必须开始计算到相邻哈希框的距离并提取更多数据.在实践中,你应该使用一个大约是典型最近点大小两倍的哈希框; 该距离取决于您的点集.