空間索引Spatial Indexing

大家第一次接觸到index應該是在上資料庫這門課的時候。之所以資料庫需要index，主要是因為數據量和應用層面的操作這兩個原因，缺一不可。回憶下資料庫最基本的操作：增刪改查以及稍複雜些的比如連接操作，基本都需要先鎖定數據位置，再執行操作。而定位這個步驟，如果沒有index，基本都是O(n)的時間複雜度，這是一個非常「耗時」的操作。雖然從複雜度角度並不能算高，但是資料庫訪問是非常基礎非常頻繁的操作，性能直接影響到終端用戶。所以非常微小的提升都是非常必要的。（如果是對於數據挖掘的演算法，這類演算法的用戶通常是研究人員，那演算法的速度快慢則顯得非常次要，而accuracy則更為重要）。上面說，數據量大是使用index的一個原因，那為什麼現在大量的機器學習演算法，那些需要海量數據的演算法不需要index呢？因為這些數據都是用來training或testing，而在這些步驟中，不需要預先定位數據位置。除了個別演算法，比如KNN演算法的prediction步驟，需要找到K個最近鄰來判斷給定item的label屬性。「找」這個操作就需要定位。注意這裡的定位不再是指在存儲器上的位置，而是在空間中的位置，這裡的空間，是由數據的維度張成的空間。空間數據，也即是這些擁有多維度的數據。這是空間數據的一個比較延展性的說法。但通常，空間數據都focus on 幾何類型數據，比如點，線，面，球等，當然這些點、線都是可以任意維度的。對於空間數據的搜索，我們需要空間索引spatial index來提升搜素效率（速度）。目前主流資料庫（SQL server, MySQL, PostgreSQL，etc）都已加入了對spatial data的支持，這其中最主要的就是數據類型和索引的支持。

R-tree

空間索引系列演算法中最最最重要的就是R-tree了。R-tree由Guttman大神在1984年SIGMOD上提出。有時間的話我還是建議大家去感受下原文：

Guttman A. R-trees: A dynamic index structure for spatial searching[M]. ACM, 1984.

R-tree主要吸納了B+tree的思想，對數據進行分割。已達到對數級訪問時間。Guttman首先提出了MBR的概念，即Minimum Bounding Box。MBR的含義是用一個最小的矩形（通常默認矩形的邊平行於坐標軸），來框住這個幾何體。

這樣我們需要找到這個幾何體中的一部分是，我們只需要先找到這個MBR即可。而找MBR這件事，則容易了很多。接下來，我們只需要用一個更大的MBR框住內層的小MBR，通過先找外層的MBR，我們可以很快找到內層MBR的大概位置。這個一層一層構建MBR的操作，非常類似B+tree的層。最後，我們就建立了一個空間上的分割。下圖是一個二維R-tree的栗子。

後續的研究比如R*-tree等對R-tree的提升主要是針對MBR的分割演算法方面的。

kd-tree

kd-tree的原理比R-tree要直接不少，對於k-dimension的數據，kd-tree的每一層，依次選一個維度把空間二分。對。。就這麼簡單。。。

Grid index

grid index即將要考慮的空間鋪好網格，以便快速鎖定區間。grid index尤其適合做最近鄰搜索。畢竟只要考慮query所在grid的附近8個(2維時)grid就可以了。

oct-tree

八叉樹是將3維空間的分成8份，依次再將每個子空間分成8份的操作，直到不需要再分為止。如果只在二維分的話，則每次分成四份，叫Quadtree。

The curse of dimensionality

雖然上述空間索引都很有效，但是當維度急劇提升時，空間索引的效率也會急劇下降。以R-tree為例，如果我們固定每個MBR最大容量為100，整個空間中有1M（million）個點，每個點的每個維度的範圍是[0,1]。我們需要：1M/100 = 10000 個MBR。假設數據是均勻分布的。那麼，設MBR邊長為x，維度為n，則 。

2D: 所有數據平鋪在平面，每個MBR邊長：0.01

3D：所有數據分散在3維空間，密度開始變得稀疏，每個MBR開始變大，邊長：0.046

4D：邊長：0.1

...

100D：邊長：0.912

在該栗子下的MBR邊長公式：nD：邊長：

可以看到，隨著維度的增大，MBR的邊長會越來越大，MBR之間的overlap也會越來越高，這樣，R-tree的效率就會變得很低。這也是為什麼高維度話題一直保持著較熱的研究興趣。今年(2018)SIGMOD做高維度的也大有人在，比如這一篇：

Wang, Yiqiu, et al. "Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search."Proceedings of the 2018 International Conference on Management of Data. ACM, 2018.

Space filling curve

space filling curve 是給高維度數據降維度的一種方法，通過給空間填充曲線，可以給每個點assign這條曲線上的位置。這樣就從高維度多個坐標變成了曲線上的單一位置坐標。事實上你可以當作是空間排序演算法。衡量space filling curve的最重要標準是，高維度相近的數據，在低維度上是否還相近。

目前space filling curve中效果最好的是 Hilbert curve，用的比較多實現比較簡單的是Z-curve。要注意的是不管哪種curve，都是基於positive integer類型數據的，如果你的數據類型是float，那麼要先整體平移到第一區間（正數），提升magnitude（保留一定原來的小數部分）在做rounding（變成整數）的預處理。

高維度下的利器：LSH（Locality Sensitive Hashing）

LSH是一系列可以將數據從高維度映射到低維度，同時提供理論性保證，使得在高維度相近的數據在低維度也大概率相近的哈希家族。理論性保證的形式為：

意思是，如果兩個點p和q在高維度相近，那麼他們在經過LSH映射到低維度後，在同一個桶內（即仍然相似）的概率高於p1。若p和q在高維度不相鄰，那麼他倆被映射到同一個桶內的概率應小於p2。

比較典型的LSH家族有：

基於Hamming distance 的 bit wise hashing

基於Jaccard distance 的 minHash

基於Cosine distance 的 SimHash

同時，為了降低上述p2，可以經過多個hash取and操作（concatenation LSH），但這樣又會降低p1，此時可增加hash table的數量取or，來提p1。詳細的做法，建議大家wiki。（如果以後有時間我會補一下）

DSH(Data Sensitive Hashing)

LSH是針對空間的，那麼有沒有針對數據的呢。2014年從高大神(我老闆的partner，現NTU副教授)在SIGMOD提出了基於數據敏感的哈希家族DSH，使得數據的分割更加均勻，尤其適合KNN類問題。類似LSH，也是有理論性保證的。詳細的就不擴展了，原文如下：

Gao J, Jagadish H V, Lu W, et al. DSH: data sensitive hashing for high-dimensional k-nnsearch[C]//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014: 1127-1138.

關於實現

做這一塊不像是AI，到處都有寫好的代碼而且基本是是python，matlab這些幾行搞定一個演算法。。（默默的羨慕一波）。而我們這些，所有的實現都應當使用C++，因為以上的技術都是針對效率的，效率嘛，不用C++說不過去啊。而且別人的演算法，一般都沒有現成的代碼，經常還需要自己小心實現出來。。。

安利一下相關的庫：

Boost Geometry 的各類spatial index （就是宏太多，有點煩），還好有mailing list，不懂可以發郵件問

CGAL 的space filling curve和其他幾何計算

CPLEX 的integer linear programming