NDLI: Just Join for Parallel Ordered Sets

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

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

On Computational Thinking, Inferential Thinking and Data Science

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Cache-Adaptive Analysis

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

A Multicore Path to Connectomics-on-Demand

Robust and Probabilistic Failure-Aware Placement

Just Join for Parallel Ordered Sets

Universal Shape Formation for Programmable Matter

Lock-free Transactions without Rollbacks for Linked Data Structures

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

The Cost of Unknown Diameter in Dynamic Networks

Parallel Shortest Paths Using Radius Stepping

Parallel Algorithms for Summing Floating-Point Numbers

A Practical Solution to the Cactus Stack Problem

Extending TM Primitives using Low Level Semantics

Parallel Algorithms for Asymmetric Read-Write Costs

The Power of Migration in Online Machine Minimization

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

Asymptotically Optimal Gathering on a Grid

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Brief Announcement: Preserving Happens-before in Persistent Memory

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Parallel Approaches to the String Matching Problem on the GPU

Better Bounds for Coalescing-Branching Random Walks

Fast and Robust Memory Reclamation for Concurrent Data Structures

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Parallelism in Randomized Incremental Algorithms

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Brief Announcement: Transactional Data Structure Libraries

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Brief Announcement: Benchmarking Concurrent Priority Queues:

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

Brief Announcement: Relaxed Byzantine Vector Consensus

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Just Join for Parallel Ordered Sets

Content Provider	ACM Digital Library
Author	Sun, Yihan Blelloch, Guy E. Ferizovic, Daniel
Abstract	Ordered sets (and maps when data is associated with each key) are one of the most important and useful data types. The set-set functions union, intersection and difference are particularly useful in certain applications. Brown and Tarjan first described an algorithm for these functions, based on 2-3 trees, that meet the optimal Θ(m log (n/m+1)) time bounds in the comparison model (n and m ≤ n are the input sizes). Later Adams showed very elegant algorithms for the functions, and others, based on weight-balanced trees. They only require a single function that is specific to the balancing scheme---a function that joins two balanced trees---and hence can be applied to other balancing schemes. Furthermore the algorithms are naturally parallel. However, in the twenty-four years since, no one has shown that the algorithms, sequential or parallel are asymptotically work optimal. In this paper we show that Adams' algorithms are both work efficient and highly parallel (polylog span) across four different balancing schemes---AVL trees, red-black trees, weight balanced trees and treaps. To do this we use careful, but simple, algorithms for Join that maintain certain invariants, and our proof is (mostly) generic across the schemes. To understand how the algorithms perform in practice we have also implemented them (all code except Join is generic across the balancing schemes). Interestingly the implementations on all four balancing schemes and three set functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of our implementation to other existing libraries and algorithms.
Starting Page	253
Ending Page	264
Page Count	12
File Format	PDF
ISBN	9781450342100
DOI	10.1145/2935764.2935768
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Intersection Red-black tree Parallel algorithm Set functions Treap Balanced binary search tree Avl tree Join Weight-balanced tree Difference Split Union
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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