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

Jiazheng Tian, Kun Xie, Wang Xin, Gaogang Xie, Kenli Li, Jigang Wen, Dafang Zhang, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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 top-k 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.
Original languageEnglish
Pages (from-to)2737-2750
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume29
Issue number6
DOIs
Publication statusPublished - Aug 2021

Keywords

  • Top-k largest entry inference
  • tensor completion

Fingerprint

Dive into the research topics of 'Efficiently Inferring Top-k Largest Monitoring Data Entries based on Discrete Tensor Completion'. Together they form a unique fingerprint.

Cite this