近似最近鄰歸約問題在泊松點過程上的再研究

摘要： 在已發(fā)表文獻中,研究了基于圖靈歸約求解ε-NN的問題,即給定查詢點q、點集P及近似參數(shù)ε,找到q在P中近似比不超過1+ε的近似最近鄰,并提出了一個具有O(logn)查詢時間復雜度的圖靈歸約算法,這里的查詢時間是調(diào)用神諭的次數(shù).經(jīng)過對比,此時間優(yōu)于所有現(xiàn)存的歸約算法.但是已發(fā)表文獻中提出的歸約算法的缺點在于,其預處理時間和空間復雜度中有O((d/ε)^d)的因子,當維度數(shù)d較大或...