Efficient Sentinel Mining Using Bitmaps on Modern Processors

This paper proposes a highly efficient bitmap-based approach for discovery of so-called sentinels. Sentinels represent schema level relationships between changes over time in certain measures in a multidimensional data cube. Sentinels are actionable and notify users based on previous observations, for example, that revenue might drop within two months if an increase in customer problems combined with a decrease in website traffic is observed. We significantly extend prior art by representing the sentinel mining problem by bitmap operations, using bitmapped encoding of so-called indication streams. We present a very efficient algorithm, SentBit, that is 2-3 orders of magnitude faster than the state of the art, and utilizes CPU specific instructions and the multicore architectures available on modern processors. The SentBit algorithm scales efficiently to very large data sets, which is verified by extensive experiments on both real and synthetic data.