Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


The parallel external memory (PEM) model has been used as a basis for the design and analysis of a wide range of algorithms for private-cache multi-core architectures. As a tool for developing geometric algorithms in this model, a parallel version of the I/O-ef?cient distribution sweeping framework was introduced recently, and a number of algorithms for problems on axis-aligned objects were obtained using this framework. The obtained algorithms were ef?cient but not optimal. In this paper, we improve the framework to obtain algorithms with the optimal I/O complexity of O(sortP(N) + K=PB) for a number of problems on axis-aligned objects; P denotes the number of cores/processors, B denotes the number of elements that ?t in a cache line, N and K denote the sizes of the input and output, respectively, and sortP(N) denotes the I/O complexity of sorting N items using P processors in the PEM model. To obtain the above improvement, we present a new one-dimensional batched range counting algorithm on a sorted list of ranges and points that achieves an I/O complexity of O((N + K)=PB), where K is the sum of the counts of all the ranges. The key to achieving ef?cient load balancing among the processors in this algorithm is a new method to count the output without enumerating it, which might be of independent interest.

Questions and Answers

You need to be logged in to be able to post here.