作者oe725 ( )
看板DataScience
標題[問題] 麻煩推薦鄰近點搜尋演算法
時間Tue Jun 22 15:17:39 2021
作業系統:不限
問題類別:鄰近點搜尋
使用工具: Python
問題內容:
XY平面座標上，共有N個點，定某一點為TargetPoint，
找出與該點歐氏距離小於d的其他點
因為我要遍尋所有N個點，所以需要一個可以快速搜尋的演算法
我自己是有硬幹一個方法，不過效率欠佳(找一次要0.072秒，當N==2000時，就要144秒)
請問各位前輩有推薦的搜尋演算法嗎?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.241.212.240 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/DataScience/M.1624346261.A.389.html
1F：推 yoyololicon: KD tree不行？ 06/22 16:27
2F：→ truehero: kdtree 啦~再不行就上gpu阿 06/22 19:09
3F：→ Pieteacher: meta heuristic algorithm 06/22 19:32
4F：推 imchou239: 之前有稍微查過這個問題 06/26 19:02
5F：→ imchou239: 推薦 Foundations of Multidimensional and Metric 06/26 19:04
6F：→ imchou239: data structure, Hanan Samet 2006 06/26 19:04
7F：→ imchou239: 以2D問題來說 06/26 19:05
8F：推 imchou239: 第一章跟第三章有詳細的資料結構與分析 06/26 19:07
9F：推 wang19980531: Faiss 07/01 16:53
10F：推 laladeer: 暴力搜尋的話可以考慮Fast Point Feature Histograms的 07/31 08:44
11F：→ laladeer: 概念，加速滿有效的 07/31 08:44