Please use this identifier to cite or link to this item:
Title: On probabilistic models for uncertain sequential pattern mining
Authors: Muzammal, Muhammad
Raman, Rajeev
First Published: 1-Dec-2010
Presented at: 6th International Conference, ADMA 2010, Chongqing, China, November 19-21, 2010
Start Date: 19-Nov-2010
End Date: 21-Nov-2010
Publisher: Springer Verlag
Citation: Advanced Data Mining and Applications Lecture Notes in Computer Science Volume 6440, 2010, pp 60-72
Abstract: We study uncertainty models in sequential pattern mining. We consider situations where there is uncertainty either about a source or an event. We show that both these types of uncertainties could be modelled using probabilistic databases, and give possible-worlds semantics for both. We then describe ”interestingness” criteria based on two notions of frequentness (previously studied for frequent itemset mining) namely expected support [C. Aggarwal et al. KDD’09;Chui et al., PAKDD’07,’08] and probabilistic frequentness [Bernecker et al., KDD’09]. We study the interestingness criteria from a complexity-theoretic perspective, and show that in case of source-level uncertainty, evaluating probabilistic frequentness is #P-complete, and thus no polynomial time algorithms are likely to exist, but evaluate the interestingness predicate in polynomial time in the remaining cases.
Series/Report no.: Lecture Notes in Computer Science;
DOI Link: 10.1007/978-3-642-17316-5_6
ISSN: 0302-9743
ISBN: 978-3-642-17315-8
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2010, Springer Verlag. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
ADMA2010.pdfPost-review (final submitted)250.51 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.