CPT+: Decreasing the time/space complexity of the compact prediction tree

Ted Gueniche, Philippe Fournier-Viger*, Rajeev Raman, S. Tseng

*Corresponding author for this work

研究成果: Conference contribution同行評審

31 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings
編輯Tru Cao, Ee-Peng Lim, Tu-Bao Ho, Zhi-Hua Zhou, Hiroshi Motoda, David Cheung
發行者Springer Verlag
頁面625-636
頁數12
ISBN(列印)9783319180311
DOIs
出版狀態Published - 1 一月 2015
事件19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015 - Ho Chi Minh City, Viet Nam
持續時間: 19 五月 201522 五月 2015

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
9078
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015
國家Viet Nam
城市Ho Chi Minh City
期間19/05/1522/05/15

指紋 深入研究「CPT+: Decreasing the time/space complexity of the compact prediction tree」主題。共同形成了獨特的指紋。

引用此