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 (русский)