b*****c
发帖数: 1103 | 1 给定10万点，再给query set，怎样预处理能使每次query复杂度降低？
近似算法也行，点的坐标都是正整数，
kd树也太慢了，fortune's algorithm代码太长，比赛时连打字不够时间啊 |
d******u
发帖数: 397 | |
l**********e
发帖数: 336 | 3 各种tree的算法，如果维度高了，都不太work的。这些点是在什么维度？
【在 b*****c 的大作中提到】
: 给定10万点，再给query set，怎样预处理能使每次query复杂度降低？
: 近似算法也行，点的坐标都是正整数，
: kd树也太慢了，fortune's algorithm代码太长，比赛时连打字不够时间啊
|
l**********e
发帖数: 336 | 4 补充下，如果维度高的话，hashing不错，比如LSH～～
【在 l**********e 的大作中提到】
: 各种tree的算法，如果维度高了，都不太work的。这些点是在什么维度？
|
b*****c
发帖数: 1103 | 5 2维，现在是维度低也很难下手啊，我要的是低于几百行代码的算法，比赛时用
【在 l**********e 的大作中提到】
: 各种tree的算法，如果维度高了，都不太work的。这些点是在什么维度？
|
b*****c
发帖数: 1103 | 6 n=100,000, n*sqrt(n) too much, barely passed 95% test cases
【在 d******u 的大作中提到】
: kd树慢？
: 那用R树？
|
g**u
发帖数: 504 | 7 划一些网格，把点归类放好，查的时候就只要看一小部分点了，是不是可行？
【在 b*****c 的大作中提到】
: 给定10万点，再给query set，怎样预处理能使每次query复杂度降低？
: 近似算法也行，点的坐标都是正整数，
: kd树也太慢了，fortune's algorithm代码太长，比赛时连打字不够时间啊
|
l**********e
发帖数: 336 | 8 你的意识是，不光给query之后search要快，training stage也要快？
【在 b*****c 的大作中提到】
: n=100,000, n*sqrt(n) too much, barely passed 95% test cases
|
b*****c
发帖数: 1103 | 9 sqrt(n)是每次query的，n*lg(n)是预处理的，主要还是query太慢
【在 l**********e 的大作中提到】
: 你的意识是，不光给query之后search要快，training stage也要快？
|
