ソート集合のある分割に対する並列アルゴリズムについて

• Item type: SIG Technical Reports(1)
• 公開日: 1996-05-29
• タイトル: ソート集合のある分割に対する並列アルゴリズムについて
• タイトル / 言語: en
• タイトル: Parallel Algorithm for Partitioning Sorted Sets and Related Problems
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: ノートルダム大学計算機科学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering University of Notre Dame
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者名: Danny, Z.Chen; 陳, 慰; 和田, 幸一; 川口, 喜三男
• 著者名(英): Danny, Z.Chen; Wei, Chen; Koichi, Wada; Kimio, Kawaguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では次のような分割問題を考える。要素数nの集合Sがk個の列からなりそれぞれソートされたn/k個の集合として与えられているとき、パラメタh(/k〓h〓n/)に対してSを|D_i|=Θ()であり、1〓i<j〓gなる任意の添字iとjに対してD_iのどの要素もD_jのどの要素より大きくないようにg=O(/()）個の部分集合D_1，D_2，…，D_gに分割する。この分割問題はkとhをうまく設定することにより、マージ、ソートや近似の中間値などを求める問題を含んでおり、また計算幾何学の問題へも応用できる。本稿では、この分割問題を解く並列アルゴリズムを示す。この並列アルゴリズムはEREW PRAMモデルにおいてO（(in{(/)*max{log h，1}，n*max{log(/)，1}}）/(og )）個のプロセッサを用いてO(og )時間で分割問題を解く。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k〓h〓n/k, partition S into g = O(n/(hk)) subsets D_1, D_2, …, D_g of size Θ(hk) each, such that for any two indices i and j with 1〓i<j〓g, no element in D_i is bigger than any element in D_j. In this paper, we present efficient parallel algorithms for solving the partition problem and its applications. Our parallel partition algorithm runs in O(log n) time using O((min{(n/h)*max{log h,1},n*max{log(1/h),1}})/(log n)) processors in the EREW PRAM model.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 57(1996-AL-051), p. 33-40, 発行日 1996-05-29
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会