多維座標（搜索，插入）的數據結構？

是否有專爲快速插入和搜索多維座標而設計的數據結構（對於所有實際用途而言，比2維或3維更多，小於1k維和1M點）？甚至更好，對於任意距離度量？多維座標（搜索，插入）的數據結構？

我知道關於kd-trees，這對於插入是很好的，但據我所知，平衡它們並不重要，並且搜索在高維方面效率不高。無序映射/哈希表乍一看是一個很好的解決方案，但據我所知，哈希和碰撞有問題（例如，轉換爲字符串通常會截斷數值精度，處理非相鄰點的碰撞可能會昂貴）。也許像每個維度上的紅黑樹都適合插入，並且對於搜索來說不是太糟糕（遞歸地沿着維度進行過濾）。

我只是不想重新發明輪子，我確信這是數據科學中最常見的需求。作爲答案，很高興能夠鏈接論文/教程。理想情況下，答案會在C/C++/Python/Java/Matlab中有現有的實現。

來源

2017-06-12 Sheljohn

您可以詳細瞭解您正在使用的實際數據嗎？也許提供一些具體的例子。 –

@JaysonBoubin我沒有想到任何特定的數據。如果它有助於假設點在一些有界子空間中，或者它們不是密集聚類的，那麼這些可以是有效的假設，否則它們只是浮點數列表。你有沒有想到什麼？ – Sheljohn

您正在尋找的數據結構是R-Tree。

你可以在這裏找到Java實現。 https://github.com/davidmoten/rtree

來源

2017-06-14 08:28:54

這似乎是正確的答案;然而[回答鏈接到外部資源應提供一些上下文]（https://stackoverflow.com/help/how-to-answer）。你能簡單地解釋爲什麼[R-trees]（https://en.wikipedia.org/wiki/R-tree）是合適的嗎？ – Sheljohn

多維座標（搜索，插入）的數據結構？

回答

相關問題