This repository contains code for our SoCG'21 paper: A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem (arXiv, talk). It contains fast code for a parallel batch-dynamic data structure that maintains the Euclidean closest pair, as well as four parallel implementations of the static closest pair problem (based on Rabin's randomized algorithm, the divide-and-conquer algorithm, the sieve algorithm, and the incremental algorithm).
The code in this repository is being gradually reimplemented in the Pargeo project, an open-source collection of parallel algorithms in computational geometry. Please check back for further details.
We included a small example data set in the closest-pair/data folder. We include larger data sets at this dropbox link. More data sets also can be generated using the data generator in pbbsbench. A data set in the same format will also work, as long as they have a header pbbs_sequencePoint<k>d, where <k> specifies the dimensionality, a number between 2 and 9 inclusive, followed by lines of space-delimited point coordinates.
To compile the code, navigate to closest-pair/dynamicClosestPair/dynamic/, and input make clean first. For serial execution, just make; for parallel execution, use CILK=1 make; for the most optimal parallel performance, install jemalloc first and then use CILK=1 USEJEMALLOC=1 make.
To run the code,
./closestPair -b 10 ../../data/2D_UniformFill_10K.pbbs
where -b <batch> specifies the program to dynamically insert the data set in <batch> batches, and then remove them in <batch> batches. The main function starts from line 772 of closest-pair/dynamicClosestPair/dynamic/closestPair.C, which can be modified for other functionalities.
To compile the code, navigate to closest-pair/closestPair/rabin, and input make clean first. For serial execution, just make; for parallel execution, use CILK=1 make; for the most optimal parallel performance, install jemalloc first and then use CILK=1 USEJEMALLOC=1 make.
To run the code,
./closestPair ../../data/2D_UniformFill_10K.pbbs
The program will use Rabin's algorithm to solve the closest pair, and it can be done similarly for the rest of the algorithms in the following directories: closest-pair/closestPair/divideConquer, closest-pair/closestPair/sieve and closest-pair/closestPair/incremental.
Please feel free to contact the developers or the paper authors if you encounter any problems, we are happy to patch/fix the program.
If you use our work in a publication, we would appreciate citations:
@misc{wang2020parallel,
title={A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem},
author={Yiqiu Wang and Shangdi Yu and Yan Gu and Julian Shun},
year={2020},
eprint={2010.02379},
archivePrefix={arXiv},
primaryClass={cs.DS}
}