什麼數據結構用於快速變化的最近鄰居搜索？

Question

我想存儲從3到20個維度的50到10 000個向量。我想知道在哪種結構中存儲向量，以便能夠快速求解最近鄰或近似近鄰問題。我將使用歐幾里得，曼哈頓，馬克斯和加權曼哈頓度量。

我開始讀到這個問題，並發現（糾正我，如果我錯了），當維數比這個向量的數量小得多時，kd-trees會這樣做。性能可以是深度次線性的（O（log（n）））。

問題是，結構將變化非常迅速。每個矢量在程序過程中可以改變數千次。此外，矢量不需要保持它們的近似位置或比例。整個結構可以通過R^n「旅行」。

問題是，爲了保持kd-tree的高性能，需要時不時的重新平衡。此操作可能與重建整個樹一樣昂貴。

如何解決kd-tree快速變化的問題？

Answer 1

您應該對在不同數據結構上運行的算法執行amortized analysis。結果將根據您正在使用的特定數據結構的操作順序而變化。我建議也看看R-tree。查看靜態網格也可能是一個好主意，因爲如果數據結構的更新比查詢更頻繁，那麼更新該結構可能會相當好地執行。

如果對數據結構的更新太頻繁，那麼最好不要每次更改都更新數據結構，而是先使用過時的數據結構，然後對所有更改的元素執行搜索。這樣，您可以對數據結構進行批量更改，這可能會更有效。這是攤銷分析也可以回答的一件事。

你也應該看看可用於多維樹的文獻。他們肯定會找到更有效的數據結構操作建議，或者你還沒有想過的建議。但是我不能推薦文獻。