@article{oai:ipsj.ixsq.nii.ac.jp:00157631,
 author = {Shigeyuki, Sato and Kenjiro, Taura and Shigeyuki, Sato and Kenjiro, Taura},
 issue = {1},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Feb},
 note = {Space-partitioning trees, each of which holds particles in some space, are extensively used in various applications. Parallel programming with space-partitioning trees is an important issue because they are often used for spatial computation on large-scale data that motivates parallel computing. High-level computational patterns that abstract spatial computation on space-partitioning trees will make parallel programming easy, simple, and productive. Although they have tree structures, spatial computation on them is inherently interaction/correlation computation on two sets rather than tree computation. Existing patterns based only on tree structures are therefore insufficient to abstract it. In this study, we present a pattern based on cross edges between two space-partitioning trees. It abstracts computations between subspaces/particles as cross edges. We have implemented our pattern as a C++ template library at the proof-of-concept level. We present our library API, describe its affinity with parallel implementation, and also report the experimental overhead of sequential execution., Space-partitioning trees, each of which holds particles in some space, are extensively used in various applications. Parallel programming with space-partitioning trees is an important issue because they are often used for spatial computation on large-scale data that motivates parallel computing. High-level computational patterns that abstract spatial computation on space-partitioning trees will make parallel programming easy, simple, and productive. Although they have tree structures, spatial computation on them is inherently interaction/correlation computation on two sets rather than tree computation. Existing patterns based only on tree structures are therefore insufficient to abstract it. In this study, we present a pattern based on cross edges between two space-partitioning trees. It abstracts computations between subspaces/particles as cross edges. We have implemented our pattern as a C++ template library at the proof-of-concept level. We present our library API, describe its affinity with parallel implementation, and also report the experimental overhead of sequential execution.},
 pages = {16--16},
 title = {Abstraction of Space Partitioning for Spatial Computation},
 volume = {9},
 year = {2016}
}