BICP: Block-Incremental CP Decomposition with Update Sensitive Refinement
BICP: Block-Incremental CP Decomposition with Update Sensitive Refinement
复制标题
BICP：具有更新敏感细化的块增量 CP 分解
DOI：
10.1145/2983323.2983717
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sapino, Maria Luisa
中科院分区：
文献类型：
--
作者：
Huang, Shengyu;Candan, K. Selçuk;Sapino, Maria Luisa
由于许多应用程序依赖多维数据集进行决策，张量（或多维数组）正在成为一种流行的数据表示形式，以支持不同类型的数据，例如传感器流和社交网络。因此，张量分解构成了许多数据分析和知识发现任务的基础，从聚类、趋势检测、异常检测到相关性分析。在数据随时间演变并且需要持续维护基于张量的分析结果的应用中，每次更新时重新计算整个张量分解将导致较高的计算成本并产生大量的内存开销。在本文中，我们提出了一种基于两阶段块增量 CP 的张量分解技术 BICP，该技术在存在动态演变的张量数据的情况下高效且有效地维护张量分解结果。在第一阶段，BICP 不会对每个子张量重复进行 ALS，而是仅修改包含更新数据的张量的分解。此外，当更新相对于块大小相对较小时，BICP 依赖增量因子跟踪来避免重新分解更新后的子张量。在第二阶段，BICP 将以块为中心的细化过程限制为仅针对那些对于更新至关重要的块。实验结果表明，该方法在保证高精度的同时，显着减少了执行时间。
With many applications relying on multi-dimensional datasets for decision making, tensors (or multi-dimensional arrays) are emerging as a popular data representation to support diverse types of data, such as sensor streams and social networks. Consequently, tensor decomposition forms the basis for many data analysis and knowledge discovery tasks, from clustering, trend detection, anomaly detection, to correlation analysis. In applications where data evolves over time and the tensor-based analysis results need to be continuously maintained, re-computation of the whole tensor decomposition with each update will cause high computational costs and incur large memory overheads. In this paper, we propose a two-phase block-incremental CP-based tensor decomposition technique, BICP, that efficiently and effectively maintains tensor decomposition results in the presence of dynamically evolving tensor data. In its first phase, instead of repeatedly conducting ALS on each sub-tensor, BICP only revises the decompositions of the tensors that contain updated data. Moreover, when updates are relatively small with respect to the block size, BICP relies on a incremental factor tracking to avoid re-decomposition the updated sub-tensor. In its second phase, BICP limits the block-centric refinement process to only those blocks that are critical given the update. Experiment results show that the proposed method significantly reduces the execution time while assuring high accuracy.
登录
查看更多内容
基于 HOSVD 的多面动态模型规范形式的定义
DOI：
10.1109/icmech.2006.252604
发表时间：
2006
期刊：
2006 IEEE International Conference on Mechatronics
影响因子：
--
作者：
P. Baranyi;L. Szeidl;P. Várlaki;Y. Yam
通讯作者：
Y. Yam
DOI：
10.1137/1.9781611972801.60
发表时间：
2009-09
期刊：
ArXiv
影响因子：
--
作者：
Charalampos E. Tsourakakis
通讯作者：
Charalampos E. Tsourakakis
DOI：
10.1136/ebmh.11.4.102
发表时间：
2008-10
期刊：
Evidence Based Mental Health
影响因子：
--
作者：
P. Cochat;L. Vaucoret;J. Sarles
通讯作者：
P. Cochat;L. Vaucoret;J. Sarles
2PCP：十亿级稠密张量的两相CP分解
DOI：
10.1109/icde.2016.7498294
发表时间：
2016
期刊：
2016 IEEE 32nd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Xinsheng Li;Shengyu Huang;K. Candan;M. Sapino
通讯作者：
M. Sapino
基于块的数组存储上的高效静态和动态数据库内张量分解
DOI：
10.1145/2661829.2661864
发表时间：
2014
期刊：
Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management
影响因子：
--
作者：
Mijung Kim
通讯作者：
Mijung Kim