|Table of Contents|

Probabilistic Knearest neighbor search in uncertain timeseries database


Research Field:
Publishing date:


Probabilistic Knearest neighbor search in uncertain timeseries database
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
nearest neighborssearchtime seriesuncertaintydimension reductionindexpruning
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.


[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.


Last Update: 2013-02-15