English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a theoretically-efficient and practical parallel batch-dynamicdata structure for the closest pair problem. Our solution is based on a serialdynamic closest pair data structure by Golin et al., and supports batches ofinsertions and deletions in parallel. For a data set of size $n$, our datastructure supports a batch of insertions or deletions of size $m$ in$O(m(1+\log ((n+m)/m)))$ expected work and $O(\log (n+m)\log^*(n+m))$ depthwith high probability, and takes linear space. The key techniques for achievingthese bounds are a new work-efficient parallel batch-dynamic binary heap, andcareful management of the computation across sets of points to minimize workand depth.  We provide an optimized multicore implementation of our data structure usingdynamic hash tables, parallel heaps, and dynamic $k$-d trees. Our experimentson a variety of synthetic and real-world data sets show that it achieves aparallel speedup of up to 38.57x (15.10x on average) on 48 cores withhyper-threading. In addition, we also implement and compare four parallelalgorithms for static closest pair problem, for which we are not aware of anyexisting practical implementations. On 48 cores with hyper-threading, thestatic algorithms achieve up to 51.45x (29.42x on average) speedup, and Rabin'salgorithm performs the best on average. Comparing our dynamic algorithm to thefastest static algorithm, we find that it is advantageous to use the dynamicalgorithm for batch sizes of up to 20\% of the data set. As far as we know, ourwork is the first to experimentally evaluate parallel closest pair algorithms,in both the static and the dynamic settings.

A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem