Efficiently Inferring Top-k Largest Monitoring Data Entries Based on Discrete Tensor Completion

doi:10.1109/TNET.2021.3103527

	Efficiently Inferring Top-k Largest Monitoring Data Entries Based on Discrete Tensor Completion
	Tian, Jiazheng 1; Xie, Kun 1; Wang, Xin 2; Xie, Gaogang 3,4; Li, Kenli 1; Wen, Jigang 5; Zhang, Dafang 1; Cao, Jiannong 6
	2021-12-01
发表期刊	IEEE-ACM TRANSACTIONS ON NETWORKING
ISSN	1063-6692
卷号	29 期号:6 页码:2737-2750
摘要	Network-wide monitoring is important for many network functions. Due to the need of sampling to reduce high measurement cost, system failure, and unavoidable data transmission loss, network monitoring systems suffer from the incompleteness of network monitoring data. Different from the traditional network monitoring data estimation problem which aims to infer all missing monitoring data entries with incomplete measurement data, we study a challenging problem of inferring the top-k largest monitoring data entries. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top-k data entries. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top-k entry inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of topk largest entries with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. To quickly infer the top-k largest data entries when measurement data arrive sequentially, we also propose a sliding window based online algorithm using the discrete tensor completion model. Extensive experiments using five real data sets and one synthetic data set demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar top-k entry inference accuracy using significantly smaller time and storage space.
关键词	Top-k largest entry inference tensor completion
DOI	10.1109/TNET.2021.3103527
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62025201] ; National Natural Science Foundation of China[61972144] ; National Natural Science Foundation of China[61976087] ; China Education and Research Network (CRENET) Innovation Project[NGII20190118] ; Hunan Provincial Innovation Foundation for Postgraduate[CX20190305] ; NSF Electrical, Communications and Cyber Systems (ECCS)[1731238] ; NSF Electrical, Communications and Cyber Systems (ECCS)[2030063] ; NSF Communication and Information Foundations (CIF)[2007313]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000731147300029
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/17953
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Kun
作者单位	1.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Peoples R China 2.SUNY Stony Brook, Dept Elect & Comp Engn, Stony Brook, NY 11794 USA 3.Chinese Acad Sci, Comp Network Informat Ctr, Beijing 100190, Peoples R China 4.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100190, Peoples R China 5.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 6.Hong Kong Polytech Univ, Dept Comp, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Tian, Jiazheng,Xie, Kun,Wang, Xin,et al. Efficiently Inferring Top-k Largest Monitoring Data Entries Based on Discrete Tensor Completion[J]. IEEE-ACM TRANSACTIONS ON NETWORKING,2021,29(6):2737-2750.
APA	Tian, Jiazheng.,Xie, Kun.,Wang, Xin.,Xie, Gaogang.,Li, Kenli.,...&Cao, Jiannong.(2021).Efficiently Inferring Top-k Largest Monitoring Data Entries Based on Discrete Tensor Completion.IEEE-ACM TRANSACTIONS ON NETWORKING,29(6),2737-2750.
MLA	Tian, Jiazheng,et al."Efficiently Inferring Top-k Largest Monitoring Data Entries Based on Discrete Tensor Completion".IEEE-ACM TRANSACTIONS ON NETWORKING 29.6(2021):2737-2750.