圧縮ダイナミックレンジ多数決と少数データ構造【JST・京大機械翻訳】

Gagie Travis; Gagie Travis; He Meng; Navarro Gonzalo; Navarro Gonzalo; Navarro Gonzalo

文献

J-GLOBAL ID：202002289306186899 整理番号：20A1122728

圧縮ダイナミックレンジ多数決と少数データ構造【JST・京大機械翻訳】

Compressed Dynamic Range Majority and Minority Data Structures

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A1122728&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A1122728&from=J-GLOBAL&jstjournalNo=T0530A") }}

著者 (6件)： , , , , ,
資料名：
巻： 82 号： 7 ページ： 2063-2086 発行年： 2020年
JST資料番号： T0530A ISSN： 0178-4617 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：ドイツ (DEU) 言語：英語 (EN)

[数式:原文を参照]-大多数質問問題において,シーケンス[数式:原文を参照]と固定閾値[数式:原文を参照]を与えて,質問範囲[数式:原文を参照]を与えられるようにSを前処理するように求め,[数式:原文を参照]における[数式:原文を参照]時間よりも多く発生するシンボルを効率的に報告することができる。本論文では,範囲[数式:原文を参照]-大多数質問のための最初の圧縮動的データ構造について述べた。それは,任意の[数式:原文を参照]に対して圧縮された空間-[数式:原文を参照]ビットにおけるSを表し,そこでは,[数式:原文を参照]はアルファベットサイズであり,[数式:原文を参照]は[数式:原文を参照]時間におけるS-および応答質問のk次経験エントロピーであり,一方,[数式:原文を参照]におけるSにおける挿入および削除を支援する。次に,質問時間でいくつかの[数式:原文を参照]を受信するために,著者らのデータ構造を修正する方法を示し,漸近的空間または更新時間限界を増加させることなく,[数式:原文を参照]時間における範囲[数式:原文を参照]-主要性を報告した。最良の以前の動的解法には,同じ質問と更新時間がある。しかし,それはO(n)単語を占めて,質問時間においてより大きな閾値[数式:原文を参照]を与えるという利点を利用することができない。また,距離[数式:原文を参照]に対する最初の動的データ構造を設計した。すなわち,距離において生じる非[数式:原文を参照]-大多数を見出し,空間および時間限界を[数式:原文を参照]-majorに対するものと類似させた。構造を拡張して,同じ空間と時間コストで[数式:原文を参照][数式:原文を参照]を見つけた。更新を与えることによって,著者らは,著者らの空間限界を増加することなく,単語サイズ[数式:原文を参照]ビットを有するRAMに関して,両方の問題のために質問時間[数式:原文を参照]を有する静的データ構造を得た。静的代替案は時間[数式:原文を参照]に達するが,それらはSのみをゼロ次エントロピー([数式:原文を参照])に圧縮するか,またはそれらは[数式:原文を参照]の小さな値,すなわち[数式:原文を参照]を扱うだけである。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , , ,

著者キーワード (3件)： , ,

データベースシステム

, ,

前のページに戻る