Interval Merging Binary Tree

The general area of the paper is methods and data structures to efficiently avoid data duplication. In telecommunication networks operation support systems (OSS) process time series of counters related to the behaviour of network elements, such as failed location updates over the last 5 minutes. In certain scenarios KPI-s are duplicated in the course of transmission from the network element to the OSS system. As a result KPI-s aggregated from the individual counters will have incorrect values potentially resulting in thresholds agreed in SLA-s being falsely exceeded. We assume a time series of key-value pairs with the key encoding the ordered sequence number of the data and the individual. Items arrive occasionally out of order and some of them do not arrive at all. The filtering of duplicated keys should operate fast and exhibit relatively low memory footprint. For this purpose well known data constructs like hashes or binary search trees can be used, but usually they need to store all individual keys. This implies high memory footprint and slow operation, since the time complexity of a search or insert operation mostly proportional to the number of stored elements. We propose a special type of binary tree that overcomes both limitations within certain constraints.