作者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/cn.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