دانلود مقاله ISI انگلیسی شماره 150365
ترجمه فارسی عنوان مقاله

الگوریتم سریع برای شناسایی دوستان هالو دوستان

عنوان انگلیسی
A fast algorithm for identifying friends-of-friends halos
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
150365 2017 8 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Astronomy and Computing, Volume 20, July 2017, Pages 44-51

ترجمه کلمات کلیدی
کیهان شناسی، هاله، شبیه سازی، الگوریتم، شناسایی ویژگی،
کلمات کلیدی انگلیسی
Cosmology; Halo; Simulation; Algorithm; Feature identification;
پیش نمایش مقاله
پیش نمایش مقاله  الگوریتم سریع برای شناسایی دوستان هالو دوستان

چکیده انگلیسی

We describe a simple and fast algorithm for identifying friends-of-friends features and prove its correctness. The algorithm avoids unnecessary expensive neighbor queries, uses minimal memory overhead, and rejects slowdown in high over-density regions. We define our algorithm formally based on pair enumeration, a problem that has been heavily studied in fast 2-point correlation codes and our reference implementation employs a dual KD-tree correlation function code. We construct features in a hierarchical tree structure, and use a splay operation to reduce the average cost of identifying the root of a feature from O[logL] to O[1] (L is the size of a feature) without additional memory costs. This reduces the overall time complexity of merging trees from O[LlogL] to O[L], reducing the number of operations per splay by orders of magnitude. We next introduce a pruning operation that skips merge operations between two fully self-connected KD-tree nodes. This improves the robustness of the algorithm, reducing the number of merge operations in high density peaks from O[δ2] to O[δ]. We show that for cosmological data set the algorithm eliminates more than half of merge operations for typically used linking lengths b∼0.2 (relative to mean separation). Furthermore, our algorithm is extremely simple and easy to implement on top of an existing pair enumeration code, reusing the optimization effort that has been invested in fast correlation function codes.