PostGIS教程二十一：最近領域搜索
注意：本節涉及的功能只在PostGIS2.0及更高的版本可用。
一、什麼是最近鄰域搜索？
一個常見的空間查詢是："距離一個要素最近的是哪些要素？"
與距離查詢不同，最近鄰域搜索（Nearest Neighbour Search）沒有限制候選幾何圖形在什麼範圍之內，任何距離的要素都將被接受，只要它們是最近的。這引出了關於傳統的索引輔助查詢的一個問題，這些查詢需要一個搜索框，因此需要某種測量值來限定這個框。
執行最近鄰域搜索的簡單方法是按與要查詢的幾何圖形的距離對候選表進行排序，然後獲取最小距離對應的表記錄。
-- Closest street to Broad Street station is Wall St
SELECT streets.gid, streets.name
FROM
nyc_streets streets,
nyc_subway_stations subways
WHERE subways.name = Broad St
ORDER BY ST_Distance(streets.geom, subways.geom) ASC
LIMIT 1;
這種方法的問題是，它強制資料庫計算查詢幾何圖形和候選要素表中每個要素之間的距離，然後對它們進行排序。對於一個龐大的候選要素表，這不是一個合理的方法。
提高性能的一種方法是向搜索添加空間索引約束。這需要一個神奇的數字：我們可以在查詢幾何圖形周圍搜索的最小方框是什麼？並且仍然可以找到至少一個候選幾何圖形？
如果啟用計時，可以看到下面的方框輔助查詢和上面的簡單查詢之間的性能差異。
-- Closest street to Broad Street station is Wall St
SELECT streets.gid, streets.name
FROM
nyc_streets streets,
nyc_subway_stations subways
WHERE subways.name = Broad St
AND streets.geom && ST_Expand(subways.geom, 200) -- Magic number: 200m
ORDER BY ST_Distance(streets.geom, subways.geom) ASC
LIMIT 1;
這種方法的問題在於200米這個神奇的數字，如果在200米內沒有道路呢？我們可能不會得出結果：因為雖然總會有一個近鄰要素，但它可能不在200米之內。
二、基於索引的KNN
"KNN"代表"K nearest neighbours（K近鄰）"，其中"K"是要尋找的結果的數量。
KNN是一種基於純空間索引的近鄰搜索方法。通過在索引中上下移動，搜索可以在不指定任何半徑的情況下找到最近的候選幾何圖形，因此該技術適用於具有高度變數數據密度的大表，並且具有很高的性能。
注意：KNN功能僅在PostgreSQL 9.1或更高版本的PostGIS 2.0上可用。
KNN系統的工作原理是評估PostGIS R-Tree索引中幾何圖形邊界框之間的距離。
由於索引是使用幾何圖形的邊界框構建的，因此任何不是點的幾何圖形之間的距離都將不精確：它們將是幾何圖形邊界框之間的距離，而不是幾何圖形之間的距離。
基於索引的KNN查詢的語法在查詢的ORDER BY子句中放置了一個特殊的"基於索引的距離運算符"，在本例中為"<->"。有兩種基於索引的距離運算符:
- <-> —— 表示邊界框中心之間的距離
- <#> —— 表示邊界框邊界之間的距離
基於索引的距離運算符的一側必須是字面幾何值。
-- Closest 10 streets to Broad Street station are ?
SELECT
streets.gid,
streets.name
FROM
nyc_streets streets
ORDER BY
streets.geom <->
(SELECT geom FROM nyc_subway_stations WHERE name = Broad St)
LIMIT 10;
-- Same query using a geometry EWKT literal
SELECT ST_AsEWKT(geom)
FROM nyc_subway_stations
WHERE name = Broad St;
-- SRID=26918;POINT(583571 4506714)
SELECT
streets.gid,
streets.name,
ST_Distance(
streets.geom,
SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
) AS distance
FROM
nyc_streets streets
ORDER BY
streets.geom <->
SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
LIMIT 10;
第二個查詢的結果顯示了對非點幾何圖形的基於空間索引的查詢看上去有多奇怪。Wall St（華爾街）在我們的結果集中僅排名第三，儘管從Broad St車站到Wall St的絕對距離僅僅只有0.714米！
請記住，所有計算都是在邊界框上完成的。地鐵站點的邊界框就是該點本身，因此是準確的。但是街道的邊界框和街道線串幾何圖形本身是不一樣的，最近的前十條街道的邊界框是這樣的：
我們可以看到車站正好落在華爾街的線串上，並且在華爾街的邊界框中。但是這個索引順序是由<->操作符控制的，它計算邊界框中心之間的距離。邊界框中心如下：
現在很清楚為什麼華爾街沒有作為我們搜索結果的第一個記錄出現了。因為華爾街邊界框的中心確實比Exchange Place（交易所）的邊界框的中心離Broad St車站更遠。
那麼<#>運算符呢？如果我們計算邊界框邊界之間的距離，車站就會落在華爾街邊界框內，車站與華爾街的邊界框之間的距離為0，所以它作為返回結果的第一個條目返回對嗎？
-- Closest 10 streets to Broad Street station are ?
SELECT
streets.gid,
streets.name
FROM
nyc_streets streets
ORDER BY
streets.geom <#>
SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
LIMIT 10;
很遺憾，並不是。
有許多帶有大的邊界框的要素，這些邊界框也與車站重疊，所以車站與它們的邊界框的距離也為0。
要獲得高性能但精確的近鄰計算，正確的方法是使用一個子查詢提取前100個可能的結果（或者，如果你認為你的數據在分布上更均勻，則可以選擇一個較小的數字），計算所有這些結果與車站（Broad St）的真實距離，並從該集合返回最近的記錄。
-- "Closest" 100 streets to Broad Street station are?
WITH closest_candidates AS (
SELECT
streets.gid,
streets.name,
streets.geom
FROM
nyc_streets streets
ORDER BY
streets.geom <->
SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
LIMIT 100
)
SELECT gid, name
FROM closest_candidates
ORDER BY
ST_Distance(
geom,
SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
)
LIMIT 1;
請注意，在查詢點表時，由於邊界框與點完全相同，因此可以直接使用按空間索引排序的結果，而不必使用子查詢。
-- The 10 nearest stations to Broad St station
SELECT gid, name
FROM nyc_subway_stations
ORDER BY geom <-> SRID=26918;POINT(583571.905921312 4506714.34119218)::geometry
LIMIT 10;
推薦閱讀：