近接検索

Question

アプリケーションはどのように近接検索を実行しますか？たとえば、ユーザーが郵便番号を入力すると、アプリケーションは20マイル以内のすべてのビジネスを近接度順にリストします。

PHPやMySQLでそのようなものを構築したい。このアプローチは正しいですか？

1. 興味のある場所の住所を取得してデータベースに保存する
2. すべての住所をGoogleのジオコーディングサービスでジオコーディング
3. Haversine式を含むデータベースクエリを記述して、近接検索と順序付けを行います

これでいいですか？ステップ3では、すべてのクエリの近接度を計算します。すべてのビジネスといくつかの参照場所との間の距離をリストするPROXIMITYテーブルを用意する方が良いですか？

Answer 1

速度を重視するのに十分なレコードがある場合、事前にインデックスを作成する方法を次に示します。

片側約20マイルのビンのグリッドを定義します。各店舗のレコードにビン番号を保存します。検索時に、検索ポイントから半径20マイルと交差するすべてのビンの数を計算します。次に、それらのビンのいずれかにあるすべてのストアを取得し、前と同じように続行します。

Answer 2

これを使用して、何千ものポイントを実行します。 SQLでこれを実行する場合、[緯度と経度]列にインデックスを付けることが重要です。空間インデックスを使用してSQL 2008でこれを実行しようとしましたが、期待したパフォーマンスの向上は実際には見られませんでした。ただし、ZIPから一定の距離内で計算する場合は、ZIPセントロイドを使用するか、ZIPコードのポリゴン表現を使用するかを考慮する必要があります。

Haversine forumla は開始するのに適した場所です。

オンザフライで距離を計算するパフォーマンスの問題はありません。事前にポイントがわかっており、数百万のレコードがあるアプリケーションでは、事前に距離を計算します。

SELECT
        [DistanceRadius]=
        69.09 *
        DEGREES(
          ACOS(
            SIN( RADIANS(latitude) )*SIN( RADIANS(@ziplat) ) 
           +
            COS( RADIANS(latitude) )*COS( RADIANS(@ziplat) ) 
           *
            COS( RADIANS(longitude - (@ziplon)) )
          )
        )
        ,*
        FROM
            table

    ) sub
WHERE
    sub.DistanceRadius < @radius

Answer 3

これを約1200の場所で行っています。アプリケーションによっては、SQLの代わりにPHPに保存した方が良い場合もありますが、Haversine数式をオンザフライで使用します。 （実装は.netにあるため、マイレージは異なる場合があります）。

実際に実装した方法の最大の欠点は、すべての計算（最近まで）が非常に遅いデータ層で計算する必要があったことです（遅いと言うと、本当に瞬時ではないことを意味します2番目かそこら）が、それは提供された郵便番号に基づいてすべての1200の場所の距離を計算しなければならなかったという事実による。

選択したルートに応じて、経度と緯度を調べ、事前定義された範囲外のものを削除することにより、距離の計算を高速化する方法があります（たとえば、20マイル以内のすべての住所を見る場合） 20マイル離れた場所にあるすべての住所を計算できる経度範囲があります。）必要に応じてクエリを高速化できます。

実際には、データベースにすべての可能な組み合わせを保存することを検討しました。実際には、大規模なデータストアになる可能性がありますが、実際には大きな範囲にはありません。インデックスを使用すると、非常に高速で、アルゴリズムの最適化などを心配する必要はありません。C＃に方程式があり、すべての計算を行うために必要な情報をキャッシュできるため、これに反対しました。ビジネス層。どちらでも問題なく動作しますが、それはあなたの好みが何であるかということです。