最有效的方法来节省方式点并进行比较？

Question

我想知道你的意见.我创建了一个应用程序,用户在其中创建路径并跟踪此路径并保存数据库中的所有路径点.然后,应用程序对用户路点进行比较.

目前,我使用MSSQL服务器,使用两个表,一个用于路由,另一个用于存储路点(具有空间数据类型).使用SQL Server地理函数(如st_distance)在存储过程中进行比较...

我调查了其他选择.我实现的是使用对象的Oracle 11g.我将所有数据仅存储在一个对象表中,并将点的方式存储在具有纬度和经度属性的类型的Varray中.这种方式非常有效地保存和检索数据,但在比较时会变得复杂.

我正在寻找一种NoSQL解决方案,一些算法或方法来有效地做到这一点.你怎么看？

Answer 1

对所有n条记录使用STDistance等数据库函数是次优的.您的CPU开销将呈指数级增长.

你应该做的是检查你正在搜索的当前震中周围的矩形内的点数.这是一个例子(在MySQL中):

SELECT * FROM `points`
    WHERE `latitude` >= X1 AND `latitude` <= X2
    AND `longitude` >= Y1 AND `longitude` <= Y2

这提供了减少superset的点,然后通过使用Haversine公式计算顺向距离(相对于地球的曲率)来进一步减少这些点.

不要忘记在和上设置复合索引.latitudelongitude

这是PHP:

<?php
function haversine($latitude1, $longitude1,
                   $latitude2, $longitude2, $unit = 'Mi') {
    $theta = $longitude1 - $longitude2;
    $distance = (sin(deg2rad($latitude1)) * sin(deg2rad($latitude2))) +
    (cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * cos(deg2rad($theta)));
    $distance = acos($distance);
    $distance = rad2deg($distance);
    $distance = $distance * 60 * 1.1515;
    switch ($unit) {
    case 'Mi':
        break;
    case 'Km':
        $distance = $distance * 1.609344;
    }
    return (round($distance, 2));
}
?>

回顾一下:

这是一个示例图像,说明了该做什么:

第一次搜索将涉及边界框碰撞搜索(MySQL示例)以确定superset,不包括红点.第二个验证过程将涉及使用Haversine公式(PHP示例)计算点是否在适当的顺向距离内并且采用a subset(由黑点组成).