[1]钱爱玲,丁晓峰,卢炎生,等.不确定时间序列数据库中概率K最近邻查找[J].南京理工大学学报(自然科学版),2013,37(01):38.
 Qian Ailing,Ding Xiaofeng,Lu Yansheng,et al.Probabilistic Knearest neighbor search in uncertain timeseries database[J].Journal of Nanjing University of Science and Technology,2013,37(01):38.
点击复制

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

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
37卷
期数:
2013年01期
页码:
38
栏目:
出版日期:
2013-02-28

文章信息/Info

Title:
Probabilistic Knearest neighbor search in uncertain timeseries database
作者:
钱爱玲1丁晓峰2卢炎生2李永锋1楼宋江1
1.台州学院 数学与信息工程学院,浙江 台州 317000;2.华中科技大学 计算机科学与技术学院,湖北 武汉 430074
Author(s):
Qian Ailing1Ding Xiaofeng2Lu Yansheng2Li Yongfeng1Lou Songjiang1
1.School of Mathematics and Information Engineering,Taizhou University,Taizhou 317000,China; 2.School of Computer Science,Huazhong University of Science and Technology,Wuhan 430074,China
关键词:
最近邻查找时间序列不确定性降维索引剪枝
Keywords:
nearest neighborssearchtime seriesuncertaintydimension reductionindexpruning
分类号:
TP311.13
摘要:
为了对不确定时间序列上的概率K进行最近邻查找,该文从降维和索引剪枝两方面进行了研究。针对不确定时间序列的高维度性和不确定性两方面的复杂性,基于点对线性近似降维方法,提出了关于安全剪枝、最近邻概率计算以及最近邻概率上限计算的3个定理,用以提高查找效率。在此基础上,给出了不确定时间序列概率K最近邻查找算法,解决了高维度不确定时间序列查找中的维灾问题,具有较高的查找效率。实验结果验证了算法的有效性和效率。
Abstract:
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.

参考文献/References:

[1]Ding Xiaofeng.Research on the methods of uncertainty data indexing and querying in mobile environments[D].Wuhan:Computer Science Department,Huazhong University of Science and Technology,2008.
[2]於东军,谌贻华,于海瑛.融合自组织映射与WangMendel方法的模糊规则提取[J].南京理工大学学报,2011,35(6):759-763. Yu Dongjun,Chen Yihua,Yu Haiying.Fuzzy rule extraction by fusing SOM and WangMendel method[J].Journal of Nanjing University of Science and Technology,2011,35(6):759-763.
[3]Lian Xiang,Chen Lei.Probabilistic inverse ranking queries in uncertain databases[J].The International Journal on Very Large Data Bases,2011,20(1):107-127.
[4]胡文彬,李千目,张宏.基于领域知识的不确定关系模式集成[J].南京理工大学学报,2010,34(4):409-414. Hu Wenbin,Li Qianmu,Zhang Hong.Uncertain relation schema integration based on domain knowledge[J].Journal of Nanjing University of Science and Technology,2010,34(4):409-414.
[5]Guttman A.Rtrees:A dynamic index structure for spatial searching[A].ACM/Management of Data[C].Massachusetts,USA:ACM Press,1984:47-57.
[6]Faloutsos C,Ranganathan M,Manolopoulos Y.GEMINI framework[A].ACM/Management of Data[C].Minneapolis,USA:ACM Press,1994:419-429.
[7]Michel V,Damien F.The curse of dimensionality in data mining and time series prediction[J].Lecture Notes in Computer Science,2005,3512:758-770.
[8]Roussopoulos N,Kelley S,Vincent F.Nearest neighbor queries[A].ACM/Management of Data[C].San Jose,USA:ACM Press,1995:71-79.
[9]Hjaltason G R,Samet H.Distance browsing in spatial databases[J].ACM Transactions on Database System,1999,24(2):265-318.
[10]Lian Xiang,Chen Lei.Ranked query processing in uncertain databases[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(3):420-436.
[11]Dalvi N,Dan S.Probabilistic databases:Diamonds in the dirt[J].Communications of the ACM,2009,52(7):86-94.
[12]Chen Qiuxia,Lian Xiang,Chen Lei,et al.Indexable PLA for efficient similarity search[A].ACM/Very Large Data Bases[C].Vienna,Austria:ACM Press,2007:435-446.

备注/Memo

备注/Memo:
基金项目:国家自然科学基金(61100060)
作者简介:钱爱玲(1967-),女,博士,副教授,主要研究方向:时间序列数据库、数据挖掘、数据分析,Email:alinghust@126.com。
更新日期/Last Update: 2013-02-15