Reversible Sketch Based on the XOR-Based Hashing
We provided a novel reversible sketch data structure which had exactly sub-linear finding time proportional to the sketch length. We first introduced the XOR-based hash Junctions over the Galois field GF(0,1,□,·), defined the full-ranked boolean matrix over GF(0,1, □,·) and the maximum dispersion among the hash Junctions. Then, we chose d non-singular boolean matrices randomly to implement the random projection from the source address space 0,1n to the hash address space 0,1m, and used the inverse matrix of one of the randomly chosen nonsingular matrices to implement the reversal mapping. Based on the reversible sketch, we implemented an algorithm that finds and estimates the frequent items online with good accuracy. The estimate procedure used a two-stage strategy which includes Identification step and Verification step. The Identification step generates the candidate frequent items and the Verification step further verifies these items.Using a large amount of real Internet traffic data, the experiments demonstrated great improvement at the finding speed and some improvement at the accuracy than the current representative sketch, e.g. Count-Min sketch. Our preliminary results hint at the possibility of using the reversible sketch as a building block for network anomaly detection and distributed real-time traffic analysis.
Wenfeng Feng Zhibin Zhang Zongpu Jia Ziyi Fu
Department of Computer Science and Technology, HeNan Polytechnic University, China
国际会议
2006 Asia-Pacific Services Computing Conference(IEEE亚太地区服务计算会议)
广州
英文
93-98
2006-12-12（万方平台首次上网日期，不代表论文的发表时间）