關於空間索引的好書/文章

Question

我對空間索引的好文獻感興趣。利用它們等

Answer 1

我用一種土生土長的四叉樹的空間索引（以及之前我學到的單詞時，哪一個都在使用，在速度之間的比較，空間要求，空間查詢性能「quadtree 「）。對於普通類型的空間數據（我處理街道地圖數據），它們創建速度快，查詢速度快，但在查詢期間掃描太多的葉節點。具體來說，在合理節點大小（50-100）的情況下，我的四叉樹傾向於爲點查詢產生大約300個結果，即應用3-6葉節點（非常粗糙的球場;結果高度可變）。首選的數據結構是R *樹。我自己編寫並測試了一個實現了很好結果的實現。與我的QuadTree代碼相比，我構建R *樹的代碼非常慢，但葉節點上的邊界框最終組織得非常好;查詢空間的至少一半僅由一個葉節點回答（即，如果您執行隨機點查詢，則很有可能只返回單個葉節點），並且有90％的空間被覆蓋兩個節點或更少。因此，對於80個元素的節點大小，我通常會從點查詢中得到80或160個結果，平均值接近160（因爲少數查詢返回3-5個節點）。即使在地圖的密集城市地區也是如此。

我知道這是因爲我爲我的R *樹和其中的圖形對象編寫了一個可視化器，並且我在一個大型數據集（600,000個路段）上測試了它。它對點數據（以及邊界框很少重疊的其他數據）執行得更好。如果你實現一棵R *樹，我會敦促你想象結果，因爲當我寫下它時，它有多個錯誤會降低樹的效率（不影響正確性），而且我能夠調整一些決策來獲得更好的結果。一定要在大型數據集上進行測試，因爲它會揭示小型數據集無法解決的問題。這可能有助於減少用於測試的樹的扇出（節點大小），以查看樹在幾個級別深度時的工作情況。

我很樂意爲您提供源代碼，除非我需要我的僱主的許可。你知道是怎麼回事。在我的實現中，我支持強制重新插入，但是我的PickSplit和插入罰分已經被調整。

原始文件The R* tree: An Efficient and Robust Access Method for Points and Rectangles由於某種原因缺少點（「週期」中沒有句點也沒有點）。而且，它們的術語有點奇怪，例如當他們說「保證金」時，他們的意思是「周長」。

如果您需要可修改的數據結構，R *樹是一個不錯的選擇。如果在第一次創建樹後不需要修改樹，請考慮bulk loading algorithms。如果你只需要在批量加載後少量修改樹，普通的R樹算法就足夠好了。請注意，R *樹和R樹數據在結構上是相同的;只有插入算法（也許刪除？我忘記）是不同的。 R樹是1984年的原始數據結構;這裏有一個到R-tree paper的鏈接。

kd-tree看起來很有效率，不難實現，但它只能用於點數據。

順便說一句，我專注於葉節點的原因與其說是

1. 我需要處理的基於磁盤的空間索引。通常可以將所有內部節點緩存在內存中，因爲它們只是索引大小的一小部分;因此與未緩存的葉節點所需的時間相比，掃描它們所需的時間很少。
2. 我通過不爲空間索引中的元素存儲邊界框來節省大量空間，這意味着我必須實際測試每個元素的原始幾何圖形以回答查詢。因此，最大限度地減少觸摸的葉節點的數量更爲重要。

Answer 2

我開發了一種基於象限的快速搜索算法，並在幾年前在ddj.com上公佈了它。也許這是有趣的你：

加速搜索最近的線路 http://drdobbs.com/windows/198900559