Real-time Method of Accurate Unique IPs Counting Across High Number of Distinct Dimensions and distinct Time Frames for Big Data Systems

A.V. Valialkin
VertaMedia Company
(224 West 35th St., Suite 1102-5, New York, NY 10001, USA,
Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.),
O.I. Konashevych, post-graduate
Pukhov Institute for Modelling in Energy Engineering
(15, General Naumov St., Kyiv, 03164, Ukraine,
Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.)

АННОТАЦИЯ

Описан метод, позволяющий подсчитать число уникальных IP адресов из большогоколичества различных наборов данных (кортежей). Методы, основанные на сканировании логов и вероятностном подсчете, привели к неудовлетворительным результатам. Предложенный метод позволяет избежать чрезмерного использования ресурсов (процессора, оперативной и постоянной памяти), как при использовании метода сканирования необработанных логов и вероятностного метода подсчета, а также избежать большой статистической погрешности, как при использовании вероятностного метода на малых количествах уникальных значений. Основная идея метода состоит в том, что подсчет уникальных IP адресов в различных кортежах в реальном времени проводится в оперативной памяти. Обработка данных выполняется на коротких интервалах и затем они передаются в постоянную память с помощью алгоритма слияния. Обработанные счетчики IP адресов поступают в обычную базу данных из файлов с пятиминутным, часовым, суточным, недельным или месячным интервалом.

КЛЮЧЕВЫЕ СЛОВА:

probability method, statistics, information technologies, queueing theory, big data, statistical process control.

СПИСОК ЛИТЕРАТУРЫ

1. Erdös, P. (1959), available at: http://cms.math.ca/10.4153/CJM- 1959-003-9 (accessed April 4, 2016).
2. Harchol-Balter, M. (2013), Performance Modeling and Design of Computer Systems. Queueing Theory in Action, Cambridge University Press, New York, USA.
3. Cox, D.R. and Isham, V.I. (1980), Point Processes, Chapman & Hall, London, UK.
4. Durrett, R. (2010), Probability: Theory and Examples (4th ed.) Cambridge University Press, Camridge, USA.
5. Available at: https://github.com/clarkduvall/hyperloglog (accessed October 21, 2015).
6. Flajolet, P., Fusy, E., Gandouet, O. and Meunier, F. (2007), HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, Proceedings of the 2007 International Conference on the Analysis of Algorithm(AOFA ’07), available at: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf (accessed April 4, 2016).
7. Knuth, D. (1998), “Section 5.2.4: Sorting by Merging”, The Art of Computer Programming 3 (2nd ed.), Addison Wesley, USA Sorting and Searching.
8. Dean, J. and Ghemawat, S. (2004), MapReduce: Simplified Data Processing on Large Clusters, available at: http://static.googleusercontent.com/media/research.google.com/es/us/archive/mapreduce-osdi04.pdf (accessed April 4, 2016).
9. Shewhart, W. (1931), Economic Control of Quality of Manufactured Product, D.Van Nostrand Company, New York, USA. ISBN 0-87389-076-0.

VALIALKIN Aliaksandr Valerievich, Backend developer, VertaMedia Company, USA. Belarussian State University of Informatics and Radioelectronics, Automated Control in Technical Systems, 2005. The field of research — systems design, systems performance optimization, high load systems.

KONASHEVYCH Oleksii Ihorovych is a post-graduate student of the Pukhov Institute for Modeling in Energy Engineering of NAS of Ukraine; graduated from the National Aviation University in 2005; in 2011 he graduated from Kyiv National Trade and Economic University, Advanced Training Institute. The field of research — blockchain technology.

Полный текст: PDF (русский)