Proximity Search

Question

應用程序如何執行鄰近搜索？例如，用戶鍵入郵政編碼，然後應用程序列出按距離排序的20英里內的所有業務。

我想在PHP和MySQL中構建類似的東西。這種方法是否正確？

1. 找我感興趣的地點和商場地址在我的數據庫
2. 地理編碼的所有地址與谷歌的地理編碼服務
3. 寫數據庫查詢，包括haversine公式做了鄰近搜索和排序

可以嗎？在第3步中，我將計算每個查詢的鄰近度。有一個PROXIMITY表列出每個企業與幾個參考地點之間的距離是否更好？

Answer 1

如果有足夠的速度記錄，這裏有一種方法可以提前索引它們。

定義一邊約20英里的垃圾箱網格。存儲箱號與每個商店的記錄。在搜索時間，計算與搜索點相距20英里半徑的所有箱的數量。然後檢索所有商店中的所有商店，然後繼續進行。

Answer 2

我們爲約1200個位置進行此操作。我會盡快使用Haversine公式，儘管取決於您的應用程序，但將它存儲在PHP而不是SQL中可能會更好。 （我們的實現是在.net中，所以你的milage可能會有所不同）。

真的我們實現它的最大缺點是，每次計算（直到最近）都必須在數據層上計算，而這個數據層很慢（當我說速度很慢時，我的意思是非瞬時的一秒左右），但這是由於它必須根據提供的郵政編碼計算所有1200個地點的距離。

根據您選擇的路線，可以通過查看經度和緯度並移除預定義範圍之外的數據來加速數字距離計算（例如，如果您正在查看20以內的所有地址英里有一個經度範圍，你可以計算出所有地址必須落在20英里外）。如果需要，這可以加快你的查詢速度。

我們實際上是考慮將所有可能的組合存儲在我們的數據庫中。實際上，它聽起來像是一個大型的數據存儲，但實際上它並不在很大的範圍內。有了索引，它可以非常快速，而且您不必擔心算法優化等問題。我們決定不要這樣做，因爲我們在C＃中有公式，並且它允許我們緩存執行所有計算所需的信息業務層。要麼工作得很好，這只是你偏好的問題。

Answer 3

我們使用它來完成數千個點。如果您在SQL中執行此操作以在經度和緯度列上具有索引，這一點非常重要。我們嘗試在SQL 2008中使用空間索引來做到這一點，但我們確實沒有看到我們預期的性能提升。雖然如果你想在距離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