B+ 木へのシノプシス埋め込みによる近似問合せとその予備的な実験

• Item type: SIG Technical Reports(1)
• 公開日: 2021-09-09
• タイトル: B+ 木へのシノプシス埋め込みによる近似問合せとその予備的な実験
• タイトル / 言語: en
• タイトル: Approximate query processing using synopses embedded b+trees and preliminary experiments
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学情報理工学系研究科
• 著者所属: 東京大学生産技術研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, Toyo University
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, Toyo University
• 著者名: 湯浅, 拓樹; 合田, 和生; 喜連川, 優
• 著者名(英): Hiroki, Yuasa; Kazuo, Goda; Masaru, Kitsuregawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，データベース上の索引構造である B+ 木の内部ノードに要約情報であるシノプシスを付随することによって，クエリ実行時にシノプシスを利用し，探索する必要のあるノード数を削減するという手法を提案する．B+ 木の内部ノードのみにシノプシスを付随することで，容量オーバーヘッドを少なく抑えることが可能であり， それによって最大で約 25 倍クエリの実行時間を短縮することができた．またB+ 木上で探索するノード数の最大値をあらかじめ規定しておくことで，探索するノード数をより削減した上で一定の精度を担保したまま近似解をより短時 間で返すことできるということも実験により示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a new data structure made by incorporating synopses into b+trees, and make use of the incorporated synopsis when processing queries in order to reduce the number of nodes in the b+tree that must be read for exact results. By planting synopses only in the internal nodes, we showed that it is possible to have very small storage overheads, and accelerating processing time by 25x at most. By restricting the number of nodes being read while processing b+trees, it is possible to reduce processing time even more allowing approximate answers with high accuracies.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 研究報告データベースシステム（DBS）; 巻 2021-DBS-173, 号 6, p. 1-6, 発行日 2021-09-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-871X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会