Cách hiệu quả nhất để lưu điểm và so sánh?

Question

Tôi muốn biết ý kiến ​​của bạn. Tôi đã tạo một ứng dụng, nơi người dùng tạo các tuyến đường và chúng tôi theo dõi tuyến đường này và lưu tất cả các điểm trong cơ sở dữ liệu. Sau đó, ứng dụng thực hiện so sánh các điểm của người dùng.

Hiện tại, tôi sử dụng Máy chủ MSSQL, sử dụng hai bảng, một cho Tuyến đường và một để lưu trữ các điểm cách (với kiểu dữ liệu không gian). Các so sánh được thực hiện trong quy trình được lưu trữ bằng cách sử dụng các chức năng địa lý của SQL Server như st_distance ...

Tôi đã điều tra các tùy chọn khác. Một trong đó tôi thực hiện là với Oracle 11g sử dụng các đối tượng. Tôi lưu trữ tất cả dữ liệu trong chỉ một Bảng đối tượng và cách các điểm được lưu trữ trong Biến thể của một loại có thuộc tính Latitude và Kinh độ. Bằng cách này, việc tiết kiệm và truy xuất dữ liệu rất hiệu quả, nhưng sẽ phức tạp hơn khi so sánh.

Tôi đang tìm giải pháp NoSQL, một số thuật toán hoặc phương pháp để thực hiện điều này một cách hiệu quả. Bạn nghĩ sao?

Answer 1

Sử dụng các hàm cơ sở dữ liệu như STDistance cho tất cả các bản ghi n là tối ưu. Chi phí CPU của bạn sẽ tăng theo cấp số nhân.

Điều bạn cần làm là kiểm tra số lượng điểm trong hình chữ nhật xung quanh tâm chấn hiện tại bạn đang tìm kiếm. Dưới đây là một ví dụ (trong MySQL):

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

này cung cấp một giảm superset điểm mà sau đó nên được giảm hơn nữa bằng cách tính toán khoảng cách orthodromic (đối với độ cong của Trái đất với) sử dụng Haversine formula.

Đừng quên để thiết lập một composite index trên latitude và longitude.

Dưới đây là trong 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)); 
} 
?> 

Để recap:

Dưới đây là một hình ảnh ví dụ minh họa phải làm gì:

Tìm kiếm đầu tiên sẽ liên quan đến tìm kiếm va chạm hộp giới hạn (ví dụ MySQL) để xác định superset, không bao gồm các điểm màu đỏ. Quá trình xác minh thứ hai sẽ liên quan đến tính toán nếu các điểm nằm trong khoảng cách chính xác phù hợp với công thức Haversine (ví dụ PHP) và lấy subset (bao gồm các điểm đen).