查找地图上两组点之间的最短距离（大型数据集）

Question

我在两个单独的表中有两组点，如下所示： t1： Point_1 |纬度 |长 .......... Point_n |纬度 |经度和 t2 : Pt_1 |纬度 |长 .......... Pt_m |纬度 |经度两个表之间没有关系。 （最少资源） 为 t1 中的每个点识别 t2 中前 3 个最接近点的最佳方法是什么，特别是当 t1 和 t2 很大时？也许地理哈希？我尝试并似乎适用于小型数据集的是：

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

尝试通过过滤掉不相关或格式错误的行和列来减少连接运算符两侧的数据大小。也许您可以使用 geo_point_in_polygon\circle() 来丢弃不相关的数据。
尝试使用广播连接或随机连接： https://docs.microsoft.com/en-us/azure/data-explorer/kusto/query/broadcastjoin https://docs.microsoft.com/en-us/azure/data-explorer/kusto/query/shufflequery
您可以通过两种方式使用 s2\geohash\h3 哈希函数：

一个。每个table，将附近的点合并为一个代表点。这想法是使用哈希单元中心点作为所有的代表驻留在单元格中的点。这将减少 tables 大小。类似于：

          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)

b。计算每个点的哈希值并加入哈希值。类似于：

        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://docs.microsoft.com/en-us/azure/data-explorer/kusto/query/partitionoperator

Answer 2

我发现了我认为更好的方法并想分享它。

首先，曲面细分的问题/geo-hashing是这样的：
假设您有两组坐标在两个 tables T1 和 T2 中的点，以及如何为 T1 中的每个点计算 T2 中的最近点。现在假设您在 T1 中有一个点非常靠近 geo-hash 单元格的边界，而 T2 中的另一个点靠近同一边界，但在相邻的 geo-hash 单元格中。使用基于hash id的join方法，算法永远不会计算这两点之间的距离，虽然它们很近，所以最终结果会错过这一对。
连接两个 table 以计算 inter-points 距离的更好方法是根据截断坐标生成连接键。因此，对于每个 table 中的每个点，我们根据点间距离的相关性（我们关心的最大 inter-point 距离是多少）创建此键。
示例：对于坐标为 ( 45.1234; -120.5678 ) 的点，连接键可以是 25.1-120.6（截断和连接）。通过这种舍入并使用 join 方法，我们将在 table 1 中那个点的 app 15 km 半径范围内捕获 table 2 中的所有内容。将 25-120 作为连接键将捕获 150Km 内的所有内容.这将显着减少加入的 table 并避免 geo-hashing 方法的警告。

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

Answer 3

很高兴您找到了适合自己的方法。您可以尝试的另一种选择是也考虑相邻小区。

H3 哈希具有这样的能力：https://docs.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

查找地图上两组点之间的最短距离（大型数据集）

Find shortest distance between two sets of points on the map (large datasets)

kql

azure-data-explorer

kusto-explorer