Distributed mining of time-faded heavy hitters

DOI10.1016/J.INS.2020.09.048MaRDI QIDQ2054052zbMATH OpenOpenAlexFDO

Authors Marco Pulimeno, Italo Epicoco, Massimo Cafaro

Publication date 30 November 2021

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.01450

zbMATH Keywords

averaging protocolheavy hitterspeer-to-peersketchestime-fading model

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Distributed algorithms (68W15)

Abstract: We present extsc{P2PTFHH} (Peer--to--Peer Time--Faded Heavy Hitters) which, to the best of our knowledge, is the first distributed algorithm for mining time--faded heavy hitters on unstructured P2P networks. extsc{P2PTFHH} is based on the extsc{FDCMSS} (Forward Decay Count--Min Space-Saving) sequential algorithm, and efficiently exploits an averaging gossip protocol, by merging in each interaction the involved peers' underlying data structures. We formally prove the convergence and correctness properties of our distributed algorithm and show that it is fast and simple to implement. Extensive experimental results confirm that extsc{P2PTFHH} retains the extreme accuracy and error bound provided by extsc{FDCMSS} whilst showing excellent scalability. Our contributions are three-fold: (i) we prove that the averaging gossip protocol can be used jointly with our augmented sketch data structure for mining time--faded heavy hitters; (ii) we prove the error bounds on frequency estimation; (iii) we experimentally prove that extsc{P2PTFHH} is extremely accurate and fast, allowing near real time processing of large datasets.

Recommendations

• Distributed mining of frequent co-occurrence patterns across multiple data streams
• Fast and accurate mining of correlated heavy hitters
• A distributed approach for graph mining in massive networks
• A fast and distributed algorithm for mining frequent patterns in congested networks

Cites work

• A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution
• An improved data stream summary: the count-min sketch and its applications
• Data streams: algorithms and applications.
• Fast and accurate mining of correlated heavy hitters
• Finding repeated elements
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• scientific article; zbMATH DE number 2119721 (Why is no real title available?)
• Identifying correlated heavy-hitters in a two-dimensional data stream
• Identifying frequent items in a network using gossip
• Identifying frequent items in distributed data sets
• Mining frequent items in data stream using time fading model
• ProFID: practical frequent item set discovery in peer-to-peer networks

Cited in

(3)

• P2P-FISM: mining (recently) frequent item sets from distributed data streams over P2P network
• ProFID: practical frequent item set discovery in peer-to-peer networks
• Identifying frequent items in a network using gossip

Describes a project that uses

Uses Software

• CUDA
• igraph

This page was built for publication: Distributed mining of time-faded heavy hitters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054052)