NDLI: Distributed data placement to minimize communication costs via graph partitioning

Please wait, while we are loading the content...

Maintaining a microbial genome & metagenome data analysis system in an academic setting

Offline cleaning of RFID trajectory data

SAGA: array storage as a DB with support for structural aggregations

Data perturbation for outlier detection ensembles

(k, d)-core anonymity: structural anonymization of massive networks

SensorBench: benchmarking approaches to processing wireless sensor network data

PStore: an efficient storage framework for managing scientific data

Geometric graph matching and similarity: a probabilistic approach

A case study in optimizing continuous queries using the magic update technique

DistillFlow: removing redundancy in scientific workflows

Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh

Skew-resistant parallel in-memory spatial join

Extending the SQL array concept to support scientific analytics

A subspace filter supporting the discovery of small clusters in very noisy datasets

Matching dominance: capture the semantics of dominance for multi-dimensional uncertain objects

Managing evolving shapes in sensor networks

Inverse predictions on continuous models in scientific databases

Schema matching over relations, attributes, and data values

Node classification in uncertain graphs

MR-microT: a MapReduce-based MicroRNA target prediction method

Mining statistically sound co-location patterns at multiple distances

SLACID - sparse linear algebra in a column-oriented in-memory database system

DivIDE: efficient diversification for interactive data exploration

A provable algorithmic approach to product selection problems for market entry and sustainability

Proactive adaptations in sensor network query processing

Helping scientists reconnect their datasets

Point cloud databases

Integrating fault-tolerance and elasticity in a distributed data stream processing system

Integrating non-spatial preferences into spatial location queries

Efficient data management and statistics with zero-copy integration

Local context selection for outlier ranking in graphs with multiple numeric node attributes

Distributed data placement to minimize communication costs via graph partitioning

Boosting the basic counting on distributed streams

Toward efficient and reliable genome analysis using main-memory database systems

Simulation workflow design tailor-made for scientists

Efficient processing of exploratory top-k joins

A system for efficient and simultaneous processing of moving K nearest neighbor and spatial keyword queries

A study of partitioning and parallel UDF execution with the SAP HANA database

Subspace anytime stream clustering

Efficient temporal shortest path queries on evolving social graphs

Data movement in hybrid analytic systems: a case for automation

Protection of sensitive trajectory datasets through spatial and temporal exchange

New approaches to storing and manipulating multi-dimensional sparse arrays

Exploring subspace clustering for recommendations

Data patterns to alleviate the design of scientific workflows exemplified by a bone simulation

Communication-efficient preference top-k monitoring queries via subscriptions

On efficiently generating realistic social media timeline structures

Distributed data placement to minimize communication costs via graph partitioning

Content Provider	ACM Digital Library
Author	Hadjieleftheriou, Marios Karloff, Howard Saha, Barna Golab, Lukasz
Abstract	With the widespread use of shared-nothing clusters of servers, there has been a proliferation of distributed object stores that offer high availability, reliability and enhanced performance for MapReduce-style workloads. However, data-intensive scientific workflows and join-intensive queries cannot always be evaluated efficiently using MapReduce-style processing without extensive data migrations, which cause network congestion and reduced query throughput. In this paper, we study the problem of computing data placement strategies that minimize the data communication costs incurred by such workloads in a distributed setting. Our main contribution is a reduction of the data placement problem to the well-studied problem of Graph Partitioning, which is NP-Hard but for which efficient approximation algorithms exist. The novelty and significance of this result lie in representing the communication cost exactly and using standard graphs instead of hypergraphs, which were used in prior work on data placement that optimized for different objectives. We study several practical extensions of the problem: with load balancing, with replication, and with complex workflows consisting of multiple steps that may be computed on different servers. We provide integer linear programs (IPs) that may be used with any IP solver to find an optimal data placement. For the no-replication case, we use publicly available graph partitioning libraries (e.g., METIS) to efficiently compute nearly-optimal solutions. For the versions with replication, we introduce two heuristics that utilize the Graph Partitioning solution of the no-replication case. Using a workload based on TPC-DS, it may take an IP solver weeks to compute an optimal data placement, whereas our reduction produces nearly-optimal solutions in seconds.
Starting Page	1
Ending Page	12
Page Count	12
File Format	PDF
ISBN	9781450327220
DOI	10.1145/2618243.2618258
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-30
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed Data Placement via Graph Partitioning

Distributed Data Placement via Graph Partitioning

On data placement strategies in distributed RDF stores

Engineering Graph Partitioning Algorithms to Minimize Communication Volume

Graph Edge Partitioning via Neighborhood Heuristic

Workflow Scheduling to Minimize Data Movement Using Multi-Constraint Graph Partitioning

Workflow Scheduling to Minimize Data Movement Using Multi-constraint Graph Partitioning

A stream partitioning approach to processing large scale distributed graph datasets

Exploiting graph partitioning for hierarchical replica placement in WMNs

Distributed data placement to minimize communication costs via graph partitioning

Similar Documents

Distributed Data Placement via Graph Partitioning

Distributed Data Placement via Graph Partitioning

On data placement strategies in distributed RDF stores

Engineering Graph Partitioning Algorithms to Minimize Communication Volume

Graph Edge Partitioning via Neighborhood Heuristic

Workflow Scheduling to Minimize Data Movement Using Multi-Constraint Graph Partitioning

Workflow Scheduling to Minimize Data Movement Using Multi-constraint Graph Partitioning

A stream partitioning approach to processing large scale distributed graph datasets

Exploiting graph partitioning for hierarchical replica placement in WMNs

Distributed data placement to minimize communication costs via graph partitioning