多維分段樹

我必須解決的問題是stabbing queries的一維問題的4D版本：找到一個數屬於哪個區間。我正在尋找segment trees的multi-dimensional實現。理想情況下，它將使用Java，它將使用fractional cascading。多維分段樹

對於kd-trees（k-NN搜索）和範圍樹（給定邊界框，找到其中的所有點），存在多維實現，但對於分段樹，我只找到1D實現。

我很樂意考慮其他具有相似空間/時間複雜性的數據結構來解決同樣的問題。

來源

2013-04-05 Sim

有多少間隔？如果我們在討論範圍查詢和kd樹與4維範圍樹，函數log2（n）** 4（範圍樹）和n **（1-1/4）（kd樹）的均衡點，出人意料地大，大約2700萬。而且，k-d樹的最佳情況明顯更快，並且可能會有更好的常數。 [k-d樹的維基百科條目]（http://en.wikipedia.org/wiki/K-d_tree）提出了一種用於存儲區間而不是點（體積對象）的變體，但沒有給出時間限制。 – 2013-04-05 13:46:21

另外，線性大小而不是n log^4 n或n log^3 n的k-d樹將具有更好的緩存行爲。 – 2013-04-05 13:47:52

爲了擴充我的評論，我想到的二進制空間分區算法就是這樣。

選擇座標x和閾值t（隨機座標，中值座標等）。
分配一個新節點並將所有與半平面x = t相交的間隔分配給它。
遞歸構造（a）完全包含在下半空間x內的區間和（b）完全包含在上半空間x內的區間x >t。

插入查詢從根開始，檢查分配給當前節點的所有時間間隔，下降到適當的子節點並重復。對於小的子樹可能是值得的。

如果太多時間間隔被半平面x = t刺傷，您可以嘗試遞歸（a）與下半空間相交的間隔和（b）與上半空間相交的間隔空間。這會重複出現間隔，因此空間要求不再是線性的，您可能必須切換到對細分證明沒有任何效果的間隔集合的暴力破解。

來源

2013-04-05 14:14:16

回答

相關問題