Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Mining Big and Fast Data: Algorithms and Optimizations for Real-Time Data Processing
KTH, School of Electrical Engineering and Computer Science (EECS). (SCS)ORCID iD: 0000-0001-5872-7809
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In the last decade, real-time data processing has attracted much attention from both academic community and industry, as the meaning of big data has evolved to incorporate as well the speed of data. The massive and rapid production of data comes via numerous services, i.e., Web, social networks, Internet of Things (IoT) and mobile devices. For instance, global positioning systems are producing continuous data points using various location-based services. IoT devices are continuously monitoring variety of parameters, like temperature, heart beats, and others, and sending the data over the network. Moreover, part of the data produced by these real-time services is linked-data that requires tools for streaming graph analytics. Real-time graphs are ubiquitous in many fields, from the web advertising to bio-analytics. Developing analytical tools to process this amount of information at a real-time is challenging, yet extremely essential, for developing new services in areas such as web analytics, e-health and marketing.

Distributed stream processing engines (dspes) are often employed for real-time data processing, as they distribute work to many machines to achieve the required performance guarantees, i.e., low latency and high throughput. However, the scalability of dspes is often questioned when the input streams are skewed or the underlying resources are heterogeneous. In this thesis, we perform a scalability study for dspes. In particular, we study the load- balancing problem for dspes, which is caused by the skewness in the workload and heterogeneity in the cluster. In doing so, we develop several efficient and accurate algorithms to reduce the load imbalance in a distributed system. Moreover, our algorithms are integrated into Apache Storm, which is an open source stream processing framework.

Another dimension of real-time data processing involves developing novel algorithms for graph-related problems. The later part of the thesis presents several algorithms for evolving graphs. One of the most interesting features of real-world networks is the presence of community structure, which divides a network into groups of nodes with dense connections internally and sparse connections between groups. We study the community detection problem in the fully dynamic settings by formulating it as a top-k densest subgraph problem. In doing so, we achieve an extremely efficient approximation algorithm that scales to graphs with billions of edges. Further, we study the top-k graph pattern-mining problem in fully dynamic settings and develop a probabilistic algorithm using reservoir sampling. We provide the theoretical analysis for the proposed algorithms and show via empirical evaluation that our algorithms achieve up to several orders of magnitude improvement compared to the state-of-the-art algorithm.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2018. , p. 42
Series
TRITA-EECS-AVL ; 2018:27
Keywords [en]
Stream Processing, Load Balancing, Fully Dynamic Graphs, Real-Time Data Processing, Top-k Densest Subgraph, Frequent Subgraph Mining
National Category
Computer Systems
Research subject
Information and Communication Technology; Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-225487ISBN: 978-91-7729-729-1 (print)OAI: oai:DiVA.org:kth-225487DiVA, id: diva2:1195589
Public defence
2018-05-07, Sal B, Electrum building, Kistagången 16, Stockholm, 09:00 (English)
Opponent
Supervisors
Note

QC 20180409

Available from: 2018-04-09 Created: 2018-04-05 Last updated: 2018-04-10Bibliographically approved
List of papers
1. The power of both choices: Practical load balancing for distributed stream processing engines
Open this publication in new window or tab >>The power of both choices: Practical load balancing for distributed stream processing engines
Show others...
2015 (English)In: Proceedings - International Conference on Data Engineering, IEEE conference proceedings, 2015, p. 137-148Conference paper, Published paper (Refereed)
Abstract [en]

We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce Partial Key Grouping (PKG), a new stream partitioning scheme that adapts the classical 'power of two choices' to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 60% in throughput and up to 45% in latency when deployed on a real Storm cluster.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2015
Keywords
Balancing, Distributed parameter control systems, Engines, Distributed stream processing, Distributed streaming, Large datasets, Load balance, Load imbalance, Novel techniques, Orders of magnitude, Power-of-two, Network management
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-176121 (URN)10.1109/ICDE.2015.7113279 (DOI)2-s2.0-84940858966 (Scopus ID)9781479979639 (ISBN)
Conference
2015 31st IEEE International Conference on Data Engineering, ICDE 2015, 13 April - 17 April 2015
Note

QC 20151127

Available from: 2015-11-27 Created: 2015-11-02 Last updated: 2018-04-05Bibliographically approved
2. PARTIAL KEY GROUPING: Load-Balanced Partitioning of Distributed Streams
Open this publication in new window or tab >>PARTIAL KEY GROUPING: Load-Balanced Partitioning of Distributed Streams
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce PARTIAL KEY GROUPING (PKG), a new stream partitioning scheme that adapts the classical “power of two choices” to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 175% in throughput and up to 45% in latency when deployed on a real Storm cluster. PARTIAL KEY GROUPING has been integrated in Apache Storm v0.10.

Keywords
Load balancing, stream processing, power of both choices, stream grouping
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-225486 (URN)
Note

QC 20180412

Available from: 2018-04-05 Created: 2018-04-05 Last updated: 2018-04-12Bibliographically approved
3. When Two Choices Are not Enough: Balancing at Scale in Distributed Stream Processing
Open this publication in new window or tab >>When Two Choices Are not Enough: Balancing at Scale in Distributed Stream Processing
2016 (English)In: 2016 32ND IEEE INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE), 2016, p. 589-600Conference paper, Published paper (Refereed)
Abstract [en]

Carefully balancing load in distributed stream processing systems has a fundamental impact on execution latency and throughput. Load balancing is challenging because real-world workloads are skewed: some tuples in the stream are associated to keys which are significantly more frequent than others. Skew is remarkably more problematic in large deployments: having more workers implies fewer keys per worker, so it becomes harder to "average out" the cost of hot keys with cold keys. We propose a novel load balancing technique that uses a heavy hitter algorithm to efficiently identify the hottest keys in the stream. These hot keys are assigned to d >= 2 choices to ensure a balanced load, where d is tuned automatically to minimize the memory and computation cost of operator replication. The technique works online and does not require the use of routing tables. Our extensive evaluation shows that our technique can balance real-world workloads on large deployments, and improve throughput and latency by 150% and 60% respectively over the previous state-of-the-art when deployed on Apache Storm.

Series
IEEE International Conference on Data Engineering, ISSN 1084-4627
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-193258 (URN)10.1109/ICDE.2016.7498273 (DOI)000382554200050 ()2-s2.0-84980322422 (Scopus ID)978-1-5090-2020-1 (ISBN)
Conference
32nd IEEE International Conference on Data Engineering (ICDE), MAY 16-20, 2016, Helsinki, FINLAND
Note

QC 20161007

Available from: 2016-10-07 Created: 2016-09-30 Last updated: 2020-03-05Bibliographically approved
4. Load Balancing for Skewed Streams on Heterogeneous Clusters
Open this publication in new window or tab >>Load Balancing for Skewed Streams on Heterogeneous Clusters
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Streaming applications frequently encounter skewed workloads and execute on heterogeneous clusters. Optimal re- source utilization in such adverse conditions becomes a challenge, as it requires inferring the resource capacities and input distribution at run time. In this paper, we tackle the aforementioned challenges by modeling them as a load balancing problem. We propose a novel partitioning strategy called Consistent Grouping (CG), which enables each processing element instance (PEI) to process the workload according to its capacity. The main idea behind CG is the notion of small, equal-sized “virtual workers” at the sources, which are assigned to physical workers based on their capacities. We provide a theoretical analysis of the proposed algorithm and show via extensive empirical evaluation that our proposed scheme outperforms the state-of-the-art approaches, like key grouping. In particular, CG achieves 3.44x better performance in terms of latency compared to key grouping.

Keywords
Load Balancing, Stream Processing, Distributed Systems, Heterogenous clusters
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-223352 (URN)
Note

QC 20180411

Available from: 2018-02-17 Created: 2018-02-17 Last updated: 2018-04-11Bibliographically approved
5. Fully dynamic algorithm for top-k densest subgraphs
Open this publication in new window or tab >>Fully dynamic algorithm for top-k densest subgraphs
2017 (English)In: CIKM '17 Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, Association for Computing Machinery (ACM), 2017, p. 1817-1826Conference paper, Published paper (Refereed)
Abstract [en]

Given a large graph, the densest-subgraph problem asks to find a subgraph with maximum average degree. When considering the top-k version of this problem, a nattive solution is to iteratively find the densest subgraph and remove it in each iteration. However, such a solution is impractical due to high processing cost. The problem is further complicated when dealing with dynamic graphs, since adding or removing an edge requires re-running the algorithm. In this paper, we study the top-k densest-subgraph problem in the sliding-window model and propose an efficient fully-dynamic algorithm. The input of our algorithm consists of an edge stream, and the goal is to find the node-disjoint subgraphs that maximize the sum of their densities. In contrast to existing state-of-the-art solutions that require iterating over the entire graph upon any update, our algorithm profits from the observation that updates only affect a limited region of the graph. Therefore, the top-k densest subgraphs are maintained by only applying local updates. We provide a theoretical analysis of the proposed algorithm and show empirically that the algorithm offen generates denser subgraphs than state-of-the-art competitors. Experiments show an improvement in efficiency of up to five orders of magnitude compared to state-of-the-art solutions.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2017
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-220424 (URN)10.1145/3132847.3132966 (DOI)000440845300180 ()2-s2.0-85037375605 (Scopus ID)9781450349185 (ISBN)
Conference
26th ACM International Conference on Information and Knowledge Management, CIKM 2017, Pan Pacific Singapore HotelSingapore, Singapore, 6 November 2017 through 10 November 2017
Note

QC 20171220

Available from: 2017-12-20 Created: 2017-12-20 Last updated: 2018-08-28Bibliographically approved
6. Mining Frequent Patterns in Evolving Graphs
Open this publication in new window or tab >>Mining Frequent Patterns in Evolving Graphs
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Given a labeled graph, the frequent-subgraph mining (FSM) problem asks to find all the k-vertex subgraphs that appear with frequency greater than a given threshold. FSM has numerous appli- cations ranging from biology to network science, as it provides a compact summary of the characteristics of the graph. However, the task is challenging, even more so for evolving graphs due to the streaming nature of the input and the exponential time complexity of the problem. In this paper, we initiate the study of approximate FSM problem in both incremental and fully-dynamic streaming settings, where arbitrary edges can be added or removed from the graph. For each streaming setting, we propose algorithms that can extract a high-quality approximation of the frequent k-vertex subgraphs for a given threshold, at any given time instance, with high probability. In contrast to the existing state-of-the-art solutions that require iterating over the entire set of subgraphs for any update, our algorithms operate by maintaining a uniform sample of k-vertex subgraphs with optimized neighborhood-exploration procedures local to the updates. We provide theoretical analysis of the proposed algorithms and emprically demonstrate that the proposed algorithms generate high-quality results compared to baselines.

Keywords
Fully Dynamic Algorithms, Sampling, Frequent Pattern Mining
National Category
Other Engineering and Technologies
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-224143 (URN)
Note

QC 20180312

Available from: 2018-03-09 Created: 2018-03-09 Last updated: 2018-04-05Bibliographically approved

Open Access in DiVA

Anis Uddin(639 kB)365 downloads
File information
File name FULLTEXT02.pdfFile size 639 kBChecksum SHA-512
99b5f77c5c46d121e6b2b197904d39b1644f84191a29bf8c0e73cabcad933b1bb38a8f51f30a68a0e2125670137491f5d013d40dbb486a1a5d9eef788ac0c573
Type fulltextMimetype application/pdf

Authority records BETA

Nasir, Muhammad Anis Uddin

Search in DiVA

By author/editor
Nasir, Muhammad Anis Uddin
By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 382 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 4274 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf