# Optimal Algorithm for Profiling Dynamic Arrays with Finite Values

arXiv: https://arxiv.org/abs/1812.05306 · HTML: https://mlsanity.com/paper/1812.05306/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [Ensemble and Mixed Learning Techniques for Credit Card Fraud Detection](https://mlsanity.com/paper/2112.02627/) (2021)

## Abstract (arXiv)

How can one quickly answer the most and top popular objects at any time, given a large log stream in a system of billions of users? It is equivalent to find the mode and top-frequent elements in a dynamic array corresponding to the log stream. However, most existing work either restrain the dynamic array within a sliding window, or do not take advantages of only one element can be added or removed in a log stream. Therefore, we propose a profiling algorithm, named S-Profile, which is of O(1) time complexity for every updating of the dynamic array, and optimal in terms of computational complexity. With the profiling results, answering the queries on the statistics of dynamic array becomes trivial and fast. With the experiments of various settings of dynamic arrays, our accurate S-Profile algorithm outperforms the well-known methods, showing at least 2X speedup to the heap based approach and 13X or larger speedup to the balanced tree based approach.