BK-Index: A Multi-attribute Index algorithm for Network Traffic

Archiving raw network traffic is fundamental for network forensics and troubleshooting. In order to efficiently retrieve specific entries from large-scale archives, multi-attribute queries are essential. However, most previous work mainly focus on single-attribute indexing, leading to limited performance for multi-attribute queries and index updates. To this end, we propose BK-Index, a novel multi-attribute index algorithm for network traffic. BK-Index combines multi-dimensional k-ary search trees and bitmap structures to efficiently handle both high-cardinality and low-cardinality attributes. This hybrid approach significantly reduces multi-attribute retrieval response time. Additionally, BK-Index employs a periodic batch construction scheme for real-time index updates in high-speed network links, eliminating the need for costly dynamic index maintenance. A comprehensive suite of experiments conducted on actual campus network traffic data has elucidated the superior performance of the BK-Index in terms of multi-attribute indexing and retrieval compared with other state-of-the-art index methods.