Data uncertainty is inherent in many real-world applications such as sensor data monitoring and mobile tracking. Mining sequential patterns from uncertain/inaccurate data, such as sensor readings and GPS trajectories, is important to discover hidden knowledge in such applications. This paper addresses the problem of pattern matching with periodical wildcards for uncertain sequences. We present a dynamic programming approach, called CoDP, to compute the exact probability that a pattern is a subsequence of an uncertain sequence , and this approach can be further applied to substring matching for uncertain sequences. The efficiency and effectiveness of our algorithm have been verified through extensive experiments on both real and synthetic data.
PisantiN.CrochemoreM.GrossiR. and SagotM.-F., Bases of motifs for generating repeated patterns with wild cards, IEEE/ACM Trans Comput Biol Bioinform2 (2005), 40–50.
2.
OnB.-W. and LeeI., Meta similarity, Appl Intell35(3) (2011), 359–374.
3.
PasquierC.SanhesJ.FlouvatF. and Selmaoui-FolcherN., Frequent pattern mining in attributed trees: algorithms and applications, Knowledge and Information Systems46 (2016), 491–514.
4.
DeshpandeA.GuestrinC.MaddenS.R.HellersteinJ.M. and HongW., Model-Driven Data Acquisition in Sensor Networks, in: Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004, pp. 588–599.
5.
ChenH.KuW.S.WangH. and SunM.T., Leveraging Spatio-Temporal Redundancy for RFID Data Cleansing, in: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indiana, USA, 2010, pp. 51–62.
6.
LeiP.-R., A framework for anomaly detection in maritime trajectory behavior, Konwledge and Information Systems47 (2016), 189–214.
7.
AggarwalC.C. and YuP.S., A Survey of Uncertain Data Algorithms and Applications, IEEE Trans. Knowl. Data Eng.21(5) (2009), 609–623.
8.
GuoD.HuX.XieF. and WuX., Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph, Appl Intell39 (2013), 57–74.
9.
XieF.WuX. and ZhuX., Document-Specific Keyphrase Extraction Using Sequential Patterns with Wildcards, in: 2014 IEEE International Conference on Data Mining (ICDM), Shenzhen, China, 2014, pp. 1055–1060.
10.
WuY.WangL.RenJ. et al., Mining sequential patterns with periodic wildcard gaps[J], Applied Intelligence41(1) (2014), 99–116.
11.
WuY.FuS.JiangH. and WuX., Strict approximate pattern matching with general gaps, Appl Intell42 (2015), 566–580.
12.
AggarwalC.C.LiY.WangJ. and WangJ., Frequent Pattern Mining with Uncertain Data, KDD’09, Paris, France, 2009, 29–38.
13.
LeungC.K.-S.MacKinnonR.K. and TanbeerS.K., Fast Algorithms for Frequent Itemset Mining from Uncertain Data, in: 2014 IEEE International Conference on Data Mining (ICDM), Shenzhen, China, 2014, pp. 893–898.
14.
GeJ.XiaY.WangJ.NadungodageC.H. and PrabhakarS., Sequential pattern mining in databases with temporal uncertainty, Knowledge and Information Systems51 (2017), 821–850.
15.
TongY.ChenL. and DingB., Discovering Threshold-based Frequent Closed Itemsets over Probabilistic Data, in: IEEE 28th International Conference on Data Engineering, 2012, pp. 270–281.
16.
WangL.WuP. and ChenH., Finding Probabilistic Prevalent Colocations in Spatially Uncertain Data Sets[J], IEEE Transactions on Knowledge & Data Engineering25(4) (2013), 790–804.
17.
LeeG. and YunU., A new efficient approach for mining uncertain frequent patterns using minimum data structure without false positives[J], Future Generation Computer Systems68 (2017), 89–110.
18.
ZhaoZ.YanD. and NgW., Mining Probabilistically Frequent Sequential Patterns in large Uncertain Databases, IEEE Transactions on Knowledge and Data Engineering26(5) (2014), 1171–1184.
19.
LiY.BaileyJ.KulikL. and PeiJ., Efficient Matching of Substrings in Uncertain Sequences, in: Proceedings of the 14th SIAM International Conference on Data Mining (SDM’14), pp. 767–775.
20.
GeT. and LiZ., Approximate Substring Matching over Uncertain Strings, Proceedings of the VLDB 2011 Endowment4(11) (2011), 772–782.
21.
DalviN. and SuciuD., Efficient query evaluation on probabilistic databases, The VLDB Journal16(4) (2007), 523–544.
22.
BryneJ.ValenE.TangM.MarstrandT.WintherO.Da PiedadeI.KroghA.LenhardB. and SandelinA., Jaspar, the open access database of transcription factor-binding profiles: new content and tools in the 2008 update, Nucleic acids research, 2008.
