最近的鄰居搜索1到200萬移動對象

Question

定期地，應用程序將會接收到大量移動對象（大約每秒100,00,000 [100萬]）的經度和緯度。 要求是檢測400米範圍內的任何物體，檢測必須在400毫秒（毫秒）內完成。

因此，每當應用程序接收到具有經度和緯度的任何新對象時，我首先需要將其添加到數據結構中，並檢查數據結構中的任何其他對象是否與400中新添加的對象的距離不超過400米女士。

從我的研究，我有以下2個選項： 選項1： Redis的GEO可以用於上述規定，如果對象的數量較少。但是，對於執行geoadd和georadius查詢的一百萬個對象將花費超過400毫秒，這是不可接受的。將來這些對象可能是每秒200萬。

選項2：使用八叉樹數據結構的，這將提供更好的性能，我認爲它的性能也將降低，同時更新與新對象八叉樹（將需要超過400毫秒的時間更長） 100萬的對象和搜索新對象附近的對象。

我認爲很多關於使用geohash分區數據。示例使用geohash的前綴並將數據保存在redis實例1中，並將其他數據保存在redis實例2中。但是，對於兩個對象在400 m範圍內但在相鄰象限內的情況，將失敗。

問題 有沒有人有任何想法根據經緯度劃分數據，仍然檢測鄰近的物體？或者減少地圖縮小范式中的問題？

任何人都可以提出一種不同的方法，考慮到將來的對象可能是每秒200萬？

Answer 1

兩點：

1）分區，可以讓象限重疊，這意味着內象限邊界400米的所有點都增加了兩個兩個象限。我認爲這應該允許有用的分區。

2）移動對象的專用索引可能優於四叉樹，例如MX-CIF-Quadtree。你也可以嘗試我自己的PH-Tree（Java sources）。它可以很好地與大數據集一起使用（最好使用它至少10^6個點）並且具有良好的更新性能。它實際上最適合於集羣數據。它基本上是一個前綴共享四叉樹，具有許多優化（例如，它從不需要重新平衡））。在3.5GHz的i7 3770K上，我可以插入每秒500K和1M點之間的樹木，最大樹木尺寸可達100M（我在此時停止測試，但樹應該輕鬆擴展到更大的數據集）。