不确定时间序列数据库中概率K最近邻查找

摘要

为了对不确定时间序列上的概率K进行最近邻查找,该文从降维和索引剪枝两方面进行了研究.针对不确定时间序列的高维度性和不确定性两方面的复杂性,基于点对线性近似降维方法,提出了关于安全剪枝、最近邻概率计算以及最近邻概率上限计算的3个定理,用以提高查找效率.在此基础上,给出了不确定时间序列概率K最近邻查找算法,解决了高维度不确定时间序列查找中的维灾问题,具有较高的查找效率.实验结果验证了算法的有效性和效率.%In order to search the probabilistic K-nearest neighbor in uncertain time-series databases, this paper investigates dimension reduction and index pruning. The complexity of the high dimensionality and the uncertainty of uncertain time series is considered. Based on piecewise linear approximation (PLA),three lemmas are proposed to improve searching efficiency,which are no-dismissal pruning, the computation for probability of K-nearest neighbors and its upper limit. A probabilistic K-nearest neighbors search for uncertain time series ( PKNNS) algorithm is proposed to avoid dimensionality curse. Experimental results show the efficiency and effectiveness.