Please use this identifier to cite or link to this item:
Title: CPT+: Decreasing the time/space complexity of the Compact Prediction Tree
Authors: Gueniche, T.
Fournier-Viger, P.
Raman, Rajeev
Tseng, V.
First Published: 9-May-2015
Presented at: The 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Ho Chi Minh City
Start Date: 19-May-2015
End Date: 22-May-2015
Publisher: Springer
Citation: Lecture Notes in Computer Science Volume 9078, 2015, pp 625-636
Abstract: Predicting next items of sequences of symbols has many applications in a wide range of domains. Several sequence prediction models have been proposed such as DG, All-k-order markov and PPM. Recently, a model named Compact Prediction Tree (CPT) has been proposed. It relies on a tree structure and a more complex prediction algorithm to offer considerably more accurate predictions than many state-of-the-art prediction models. However, an important limitation of CPT is its high time and space complexity. In this article, we address this issue by proposing three novel strategies to reduce CPT’s size and prediction time, and increase its accuracy. Experimental results on seven real life datasets show that the resulting model (CPT+) is up to 98 times more compact and 4.5 times faster than CPT, and has the best overall accuracy when compared to six state-of-the-art models from the literature: All-K-order Markov, CPT, DG, Lz78, PPM and TDAG.
DOI Link: 10.1007/978-3-319-18032-8_49
ISSN: 0302-9743
ISBN: 978-3-319-18031-1
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
Description: Accepted as "REGULAR PAPER WITH LONG PRESENTATION" 27 of 405 submisisons accepted in this category.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

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

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