ログイン
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

{"_buckets": {"deposit": "9805dff8-fb1a-466b-85bb-e242b1017b98"}, "_deposit": {"created_by": 2, "id": "295", "owners": [2], "pid": {"revision_id": 0, "type": "depid", "value": "295"}, "status": "published"}, "_oai": {"id": "oai:kutarr.kochi-tech.ac.jp:00000295", "sets": ["5"]}, "author_link": ["1322", "1323"], "item_2_biblio_info_7": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2014-12", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "5", "bibliographicPageEnd": "9", "bibliographicPageStart": "1", "bibliographicVolumeNumber": "7", "bibliographic_titles": [{"bibliographic_title": "IPSJ Transaction on Programming"}]}]}, "item_2_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "Parallel tree contraction is a well established method of parallel tree processing. There are efficient and useful algorithms for binary trees, including the Shunt contraction algorithm and one based on the m-bridge decomposition method. However, for trees of unbounded degree, there are few practical tree contraction algorithms. The standard approach is “binarization,” namely to translate the input tree to a full binary tree beforehand. To prevent the overhead introduced by binarization, we previously proposed the Rake-Shunt contraction algorithm (ICCS 2011), which is a generalization of the Shunt contraction algorithm to trees of unbounded degree. This paper further extends this result. The major contribution is to show that the Rake-Shunt contraction algorithm is a tree contraction algorithm that uses fewer types of primitive contraction operations if we assume the input tree has been binarized. This observation clarifies the connection between the Rake-Shunt contraction algorithm and those based on binarization. In particular, it enables us to translate a parallel program developed based on the Rake-Shunt contraction algorithm to one based on the m-bridge decomposition method. Thus, we can choose whether to use binarization according to the situation.", "subitem_description_type": "Abstract"}]}, "item_2_publisher_35": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Information Processing Society of Japan (情報処理学会)"}]}, "item_2_rights_14": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "Copyright © 2014 by the Information Processing Society of Japan"}]}, "item_2_source_id_9": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1882-7802", "subitem_source_identifier_type": "ISSN"}]}, "item_2_version_type_18": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Morihata, Akimasa"}], "nameIdentifiers": [{"nameIdentifier": "1322", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Matsuzaki, Kiminori"}], "nameIdentifiers": [{"nameIdentifier": "1323", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2019-02-13"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "28-57.pdf", "filesize": [{"value": "372.4 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 372400.0, "url": {"label": "28-57.pdf", "url": "https://kutarr.kochi-tech.ac.jp/record/295/files/28-57.pdf"}, "version_id": "8f18821e-b295-44ae-93e5-33c30efab51d"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "parallel tree contraction", "subitem_subject_scheme": "Other"}, {"subitem_subject": "rose tree", "subitem_subject_scheme": "Other"}, {"subitem_subject": "m-bridge decomposition", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree"}]}, "item_type_id": "2", "owner": "2", "path": ["5"], "permalink_uri": "http://hdl.handle.net/10173/1479", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-03-24"}, "publish_date": "2017-03-24", "publish_status": "0", "recid": "295", "relation": {}, "relation_version_is_last": true, "title": ["Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree"], "weko_shared_id": -1}
  1. 学術雑誌論文

Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree

http://hdl.handle.net/10173/1479
http://hdl.handle.net/10173/1479
0475f7c1-e132-44a2-91f7-f98a91a1c5e3
名前 / ファイル ライセンス アクション
28-57.pdf 28-57.pdf (372.4 kB)
Item type 学術雑誌論文 / Journal Article(1)
公開日 2017-03-24
タイトル
タイトル Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree
言語
言語 eng
キーワード
主題Scheme Other
主題 parallel tree contraction
キーワード
主題Scheme Other
主題 rose tree
キーワード
主題Scheme Other
主題 m-bridge decomposition
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_6501
資源タイプ journal article
著者 Morihata, Akimasa

× Morihata, Akimasa

WEKO 1322

Morihata, Akimasa

Search repository
Matsuzaki, Kiminori

× Matsuzaki, Kiminori

WEKO 1323

Matsuzaki, Kiminori

Search repository
抄録
内容記述タイプ Abstract
内容記述 Parallel tree contraction is a well established method of parallel tree processing. There are efficient and useful algorithms for binary trees, including the Shunt contraction algorithm and one based on the m-bridge decomposition method. However, for trees of unbounded degree, there are few practical tree contraction algorithms. The standard approach is “binarization,” namely to translate the input tree to a full binary tree beforehand. To prevent the overhead introduced by binarization, we previously proposed the Rake-Shunt contraction algorithm (ICCS 2011), which is a generalization of the Shunt contraction algorithm to trees of unbounded degree. This paper further extends this result. The major contribution is to show that the Rake-Shunt contraction algorithm is a tree contraction algorithm that uses fewer types of primitive contraction operations if we assume the input tree has been binarized. This observation clarifies the connection between the Rake-Shunt contraction algorithm and those based on binarization. In particular, it enables us to translate a parallel program developed based on the Rake-Shunt contraction algorithm to one based on the m-bridge decomposition method. Thus, we can choose whether to use binarization according to the situation.
書誌情報 IPSJ Transaction on Programming

巻 7, 号 5, p. 1-9, 発行日 2014-12
ISSN
収録物識別子タイプ ISSN
収録物識別子 1882-7802
権利
権利情報 Copyright © 2014 by the Information Processing Society of Japan
著者版フラグ
出版タイプ VoR
出版タイプResource http://purl.org/coar/version/c_970fb48d4fbd8a85
出版者
出版者 Information Processing Society of Japan (情報処理学会)
戻る
0
views
See details
Views

Versions

Ver.1 2023-05-15 13:39:03.408986
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3