寻找地图上两组点之间的最短距离(大型数据集)

Question

我在两张独立的表格中有两组点，如: t1 : Point_1、Lat、Lat、Long .Point_n _Lat_ Long和t2 : Pt_1 _Long.两个表之间没有任何关系的Pt_m _Lat_Lat_Long。什么是(最少资源)识别t1中每个pt在t2中最接近的三个点的最佳方法，特别是当t1和t2很大的时候？也许是Geohashing？我尝试并似乎很好地处理小数据集的是：

t1
| extend blah=1
| join kind=fullouter (t2 |extend blah=1) on blah
| extend distance = geo_distance_2points(Long,Lat,Long1,Lat1)
|sort by spbldrom_code, distance asc
| extend rnk = row_number(1,point <> prev(point))
| where rnk<=3
|project point, pt, distance, rnk

请原谅我的粗野，我正在学习。谢谢!

Answer 1

1. 尝试通过过滤不相关或格式不正确的行和列来减少联接运算符两侧的数据大小。也许您可以使用geo_point_in_polygon\circle()来丢弃不相关的数据。

https://learn.microsoft.com/en-us/azure/data-explorer/kusto/query/shufflequery

1. 尝试使用广播连接或洗牌连接：https://learn.microsoft.com/en-us/azure/data-explorer/kusto/query/broadcastjoin

1. 您可以通过两种方式使用S2\Geo散列\h3散列函数：

每一表，将附近的点合并成一个有代表性的点。其思想是使用散列单元格中心点作为驻留在单元格中的所有点的代表。这将减少表的大小。类似于：

          datatable(lng:real, lat:real)
          [
             10.1234, 53,
             10.3579, 53,
             10.6842, 53,
          ]
          | summarize by hash = geo_point_to_s2cell(lng, lat, 8)
          | project geo_s2cell_to_central_point(hash)

计算每个点的散列值，并在散列值上加入。类似于：

        let t1 =
            datatable(lng:real, lat:real)
            [
              10.3579, 53,
              10.6842, 53,
            ];
        let t2 =
            datatable(lng:real, lat:real)
            [
              10.1234, 53,
            ];
        t1 | extend hash = geo_point_to_s2cell(lng, lat, 8)
        | join kind=fullouter  hint.strategy=broadcast (t2 | extend hash = geo_point_to_s2cell(lng, lat, 8)) on hash

也许分区操作符也可以加速查询：https://learn.microsoft.com/en-us/azure/data-explorer/kusto/query/partitionoperator

Answer 2

我发现了我认为是一个更好的方法来做这件事，并想分享它。

首先，

• /geo散列的问题是：

让我们假设在两个表中有两组坐标点，T1和T2，以及如何计算T1中每个点在T2中最接近的点。现在，假设T1中有一个点非常接近geo-散列单元格的边框，而T2中的另一个点靠近同一边框，但位于相邻的geo-散列单元格中。使用基于哈希id的联接方法，该算法将永远不会计算这两个点之间的距离，尽管它们非常接近，因此最终结果将错过这两个点。

• 两个表的连接计算点间距离的更好方法是根据截断的坐标生成一个连接键。因此，对于每个表中的每个点，我们根据点间距离的相关性创建这个键(我们关心的最大点间距离是多少)。

例如:对于坐标为( 45.1234；-120.5678 )的点，连接键可以是25.1-120.6 (截断和连接)。使用这个四舍五入的方法，我们将捕获表2中的所有内容，在表1中的app 15公里半径范围内，使用25-120，因为连接键将捕获150公里内的所有内容。这将大大减少连接表，并避免geo-散列方法的警告。。

在这一点上，我更擅长写散文，而不是代码:)，不过，我希望我上面描述的内容是有意义的。它当然适用于我的项目，同时避免了资源问题(cpu/mem)。

Answer 3

很高兴你找到了适合你的方法。您可以尝试的另一个选项也是考虑到相邻单元。

H3哈希具有这样的功能：https://learn.microsoft.com/en-us/azure/data-explorer/kusto/query/geo-h3cell-rings-function

就像这样：

let h3_resolution = 8;
let t1 = datatable(lng1:real, lat1:real)
[
    40.75864778392896, -73.97856558479198,
    40.74860253711237, -73.98577679198793,
    40.741092676839024, -73.9902397446769,
];
let t2 = datatable(lng2:real, lat2:real)
[
    40.75594965648444, -73.98157034840024,
    40.766085141039774, -74.01798702196743
];
t1 
| extend hash = geo_point_to_h3cell(lng1, lat1, h3_resolution)
| join kind = inner (
    t2 
    | extend rings = geo_h3cell_rings(geo_point_to_h3cell(lng2, lat2, h3_resolution),1)
    | project lng2, lat2, hash_array = array_concat(rings[0], rings[1])
    | mv-expand hash_array to typeof(string)
) on $left.hash == $right.hash_array
| project-away hash, hash_array
| extend distance = geo_distance_2points(lng1, lat1, lng2, lat2)
| project p1 = tostring(pack_array(lng1, lat1)), p2 = pack_array(lng2, lat2), distance
| sort by distance asc 
| summarize closest_3_points = make_list(p2, 3) by p1