postgresql - 数百万个点可使用的GEO实现

Question

我试图找出使用哪个GEO实现来根据long/lat找到某个点的最近点。我将有数百万甚至数十亿个不同的经纬度点需要进行比较。我一直在寻找许多不同的实现来完成我需要完成的工作。我研究过Postgis（看起来很流行，性能也很好）、Neo4J（图形数据库对我来说是一个新概念，我不确定它们的性能如何）、AWS dynamodb geohash（可伸缩性很好，但只有library是用Java编写的，我希望在node.js中编写一个库）等，但无法找出哪个性能最好。我只关注性能而不是功能的数量。我所需要做的就是将一个点与所有点进行比较，找到最接近的点（读操作），并且能够快速更改数据库中的一个点（写操作）。有人能根据这些要求建议一个好的实现吗

Answer 1

PostGIS具有多种地理哈希功能。如果使字符串足够长，搜索会变得更快（每个框+它的8个邻居的冲突更少），但是geohash生成在插入新点时会更慢。
问题还在于你想要多精确。随着纬度的增加，纬度/长“距离”变差，因为经度从赤道的约110公里缩小到两极的0公里，而纬度总是约110公里。在45度的中纬度，经度接近79km，距离误差为2（sqr（110/79））。球面距离为你提供真实的纬度/长对数之间的距离是非常昂贵的计算（很多三角法正在进行），然后你的地理哈希将不会工作（除非你转换所有的点到平面坐标）。
一个可行的解决方案是：
CREATE INDEX hash8 ON tablename(substring(hash_column FROM 1 FOR 8))。这为您提供了一个比您的分辨率大一倍的框上的索引，这有助于查找点并减少搜索相邻哈希框的需要。
在点的INSERT上，使用PostGIS将其长度为9（大约10米分辨率）的geohash计算成hash_列。你可以在这里使用BEFORE INSERT TRIGGER。
在函数中：
给定一个点，通过查找geohash值缩短为8个字符的所有点来查找最近的点，该值等于给定点8个字符的geohash（因此是上面的索引）。
使用球坐标计算到每个遇到的点的距离，保持最近的点。但是，由于您只寻找最近的点（至少最初是这样），所以不要使用球坐标搜索距离，而是使用下面的优化，这将使搜索速度更快。
如果给定点比最近的计算点更接近由8个字符的geohash确定的框的边缘，则进行计算。如果是，则对其8个邻居中的所有点使用7个字符的geohash重复该过程。这可以通过计算到各个框边和角的距离并只计算相关的邻居哈希框来进行高度优化；我把这个留给您去修改。
无论如何，这不会特别快。如果你确实要接近几十亿个点，你可能会想一想集群，它有一个相当“自然”的地理哈希解决方案（例如，在substring(hash_column FROM 1 FOR 2)上分解表，给你四个象限）。只需确保您考虑到跨边界搜索。
可以相当快地进行两个优化：
首先，“规范化”你的球面坐标（意思是：随着纬度的增加，补偿经度减少的长度），这样你就可以使用“伪笛卡尔”方法搜索最近的点。这只在点很接近的情况下才有效，但是由于您使用的是很多点，所以这不应该是一个问题。更具体地说，这应该适用于长度为6或更多的geohash框中的所有点。
假设椭球体（用于所有GPS设备），地球的长轴（A）为6378137米，椭圆度（E2）为。经度的一秒长度为

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个字符的geohash上建立索引并从那里进行搜索；相反，他们会从9个字符的hash开始并从那里向外工作。但是，初始哈希框中的“未命中”（因为没有其他点或您接近哈希框一侧）代价高昂，因为您必须开始计算到相邻哈希框的距离并拉入更多数据。实际上，您应该在一个散列框中工作，该散列框的大小大约是典型最近点的两倍；该距离是多少取决于您的点集。