ストリーミングアルゴリズム

コンピュータサイエンスにおいて、ストリーミングアルゴリズムは入力データストリームをアイテムのシーケンスとして処理し、通常はデータに対して1回（または数回）のパスのみを実行します。これらのアルゴリズムは、限られたメモリで動作するように設計されており、一般的にストリームのサイズやストリーム内の最大値に対して対数的であり、アイテムあたりの処理時間も制限される場合があります。

これらの制約の結果として、ストリーミング アルゴリズムは、データ ストリームの概要または「スケッチ」に基づいて近似的な回答を生成することがよくあります。

歴史

ストリーミングアルゴリズムは、1978年にはマンローとパターソン^[1]によって、また1982年から83年にはフィリップ・フラジョレとG・ナイジェル・マーティン^[2]によって既に研究されていましたが、ストリーミングアルゴリズムの分野が初めて形式化され、普及したのは、1996年にノーガ・アロン、ヨッシ・マティアス、マリオ・セゲディによって発表された論文でした。^[3]この論文により、著者らは後に2005年に「ストリーミングアルゴリズムへの基礎的貢献」によりゲーデル賞を受賞しました。それ以来、データストリーミングアルゴリズムを中心に、理論、データベース、ネットワーク、自然言語処理など、コンピュータサイエンスの多様な分野にわたる膨大な研究が行われてきました。

セミストリーミングアルゴリズムは、グラフのストリーミングアルゴリズムの緩和策として2005年に導入されました。^[4]セミストリーミングアルゴリズムでは、許容される空間は頂点数nに対して線形ですが、辺数mに対しては対数的です。この緩和策は稠密グラフにおいても依然として有効であり、空間的に解決できない興味深い問題（例えば接続性など）を解くことができます。 ${\displaystyle o(n)}$

モデル

データストリームモデル

データストリームモデルでは、入力の一部または全部が有限の整数列（ある有限領域から）として表現されます。この整数列は通常ランダムアクセスできず、代わりに「ストリーム」として1つずつ到着します。^[5]ストリームの長さがnで、領域のサイズがmの場合、アルゴリズムは一般的にmとnの対数空間を使用するように制約されます。アルゴリズムは通常、ストリームに対して小さな定数回しかパスできず、場合によっては1回しかパスできないこともあります。^[6]

回転式改札口とレジのモデル

ストリーミングに関する文献の多くは、保存するには大きすぎる頻度分布の統計計算に関するものです。この種の問題では、ストリーム内で更新が提示されるベクトル （ゼロベクトル に初期化される）が存在します。これらのアルゴリズムの目的は、 の関数を、正確に表現するのに必要なスペースよりもはるかに少ないスペースで計算することです。このようなストリームを更新するための一般的なモデルとして、「キャッシュレジスタ」モデルと「ターンスタイル」モデルと呼ばれる2つがあります。^[7]${\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {a} }$

キャッシュレジスタモデルでは、各更新は の形式をとるため、 は正の整数 だけ増加します。注目すべき特別なケースは、 のときです （単位の挿入のみが許可されます）。 ${\displaystyle \langle i,c\rangle }$ ${\displaystyle a_{i}}$ ${\displaystyle c}$ ${\displaystyle c=1}$

回転式改札口モデルでは、各更新は の形式をとり、 は何らかの（負の可能性のある）整数 だけ増加します。「厳密な回転式改札口」モデルでは、 どの時点においても はゼロ未満になることはありません。 ${\displaystyle \langle i,c\rangle }$ ${\displaystyle a_{i}}$ ${\displaystyle c}$ ${\displaystyle a_{i}}$

スライディングウィンドウモデル

いくつかの論文では「スライディングウィンドウ」モデルも検討されている。^[要出典]このモデルでは、対象となる関数はストリーム内の固定サイズのウィンドウ上での計算である。ストリームが進むにつれて、ウィンドウの末尾にあるアイテムは考慮対象から外され、ストリームからの新しいアイテムがその場所を占める。

上記の頻度ベースの問題以外にも、様々な種類の問題が研究されてきました。多くのグラフ問題は、グラフの隣接行列または隣接リストが未知の順序でストリームされるという設定で解かれています。ストリーム内の反転の数を数える問題や、最長増加部分列を求める問題など、ストリームの順序に大きく依存する問題（すなわち非対称関数）も存在します。^[要出典]

評価

データ ストリームで動作するアルゴリズムのパフォーマンスは、次の 3 つの基本的な要素によって測定されます。

• アルゴリズムがストリーム上で実行する必要があるパスの数。
• 使用可能なメモリ。
• アルゴリズムの実行時間。

これらのアルゴリズムは、オンラインアルゴリズムと多くの類似点があります。どちらもすべてのデータが利用可能になる前に決定を下す必要があるためですが、同一ではありません。データストリームアルゴリズムは利用可能なメモリが限られていますが、ポイントのグループが到着するまでアクションを延期できる場合があります。一方、オンラインアルゴリズムは、各ポイントが到着するとすぐにアクションを実行する必要があります。

アルゴリズムが近似アルゴリズムである場合、答えの精度も重要な要素となります。精度は多くの場合近似値と表現され、これはアルゴリズムが確率 で未満の誤差を達成することを意味します。 ${\displaystyle (\epsilon ,\delta )}$ ${\displaystyle \epsilon }$ ${\displaystyle 1-\delta }$

アプリケーション

ストリーミングアルゴリズムは、ネットワークリンクのエレファントフローの監視、個別のフローの数のカウント、フローサイズの分布の推定など、ネットワークにおいていくつかの用途があります。 ^[8]また、結合のサイズを推定するなど、データベースにおいても用途があります^[要出典]。

ストリーミングの問題

周波数モーメント

周波数セットの k 番目の周波数モーメントは次のように定義されます。 ${\displaystyle \mathbf {a} }$ ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}$

第一モーメントは、頻度（つまり、総数）の合計です。第二モーメントは、ジニ係数などのデータの統計的特性を計算するのに役立ちます 。は、最も頻繁に出現する項目の頻度として定義されます。 ${\displaystyle F_{1}}$ ${\displaystyle F_{2}}$ ${\displaystyle F_{\infty }}$

Alon、Matias、Szegedyによる独創的な論文は、周波数モーメントの推定の問題を扱っていました。^[要引用]

周波数モーメントの計算

周波数モーメントを直接求めるアプローチでは、すべての異なる要素a _i ∈ (1,2,3,4,..., N )に対してレジスタm _iを維持する必要があり、これには少なくとも オーダーのメモリが必要です。^[3]しかし、メモリ容量の制限があるため、はるかに少ないメモリで計算するアルゴリズムが必要です。これは、正確な値ではなく近似値を使用することで実現できます。F _kの( ε, δ )近似値を計算するアルゴリズムです。ここで、F' _kはF _kの( ε, δ )近似値です。^[9]ここで、 εは近似パラメータ、δは信頼度パラメータです。^[10]${\displaystyle \Omega (N)}$

計算中 F₀（データストリーム内の個別の要素）

FMスケッチアルゴリズム

Flajoletらは^[2]で、 Robert Morrisの論文からヒントを得た確率的な計数法を紹介した。^[11] Morrisは論文の中で、精度の要件がなくなると、カウンタnをlog log nビットで格納できるカウンタlog nに置き換えることができると述べている。^[12] Flajoletらは^{[2]で、ハッシュ空間（長さ}Lのバイナリ文字列）内の要素を均一に分散すると想定されるハッシュ関数hを使用してこの方法を改良した。

${\displaystyle h:[m]\rightarrow [0,2^{L}-1]}$

bit( y,k )をyの2進数表現におけるk番目のビットを表すものとする。

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}}$

は、の適切な規則を使用して、y _iのバイナリ表現における最下位 1 ビットの位置を表します。 ${\displaystyle \rho (y)}$ ${\displaystyle \rho (0)}$

${\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}$

Aを長さMのデータストリームのシーケンスとし、その基数を決定する必要がある。BITMAP [0... L − 1] を

ρ（ハッシュ値）が記録される ハッシュ空間。以下のアルゴリズムは、Aのおおよその基数を決定する。

手順 FM-Sketch:

    i が 0 から L − 1 までの場合、
        ビットマップ[i] := 0
    終わりのために
    Aのxに対して:
        インデックス := ρ(ハッシュ(x))
        BITMAP[インデックス] = 0の場合
            ビットマップ[インデックス] := 1
        終了の場合
    終わりのために
    B := BITMAP[]の左端の0ビットの位置
    2^Bを返す

データ ストリームに N 個の異なる要素がある場合。

• そのときBITMAP [ i ]は確実に0である。${\displaystyle i\gg \log(N)}$
• そのときBITMAP [ i ]は確実に1である。${\displaystyle i\ll \log(N)}$
• ビットマップ[ i ]は0と1の縞模様である。${\displaystyle i\approx \log(N)}$

K-最小値アルゴリズム

前述のアルゴリズムは、FlajoletとMartinによるデータストリーム内のF _{0 を}近似する最初の試みを記述しています。彼らのアルゴリズムは、ハッシュ値がハッシュ空間に均一に分布すると仮定したランダムハッシュ関数を選択します。

Bar-Yossef らは、^[10]でデータ ストリーム内の異なる要素の数を決定する k 最小値アルゴリズムを導入しました。彼らは、として [0,1] に正規化できる同様のハッシュ関数hを使用しました。しかし、ハッシュ空間内の値の数にtという制限を固定しました。 tの値は次数であると想定されます(つまり、近似値ε が小さいほど、より多くのtが必要です)。 KMV アルゴリズムは、ハッシュ空間にt個の最小ハッシュ値のみを保持します。ストリームのm個の値がすべて到着した後、を使用して を計算します。つまり、ほぼ均一なハッシュ空間では、少なくともt個の要素が 未満になると 予想されます。${\displaystyle h:[m]\rightarrow [0,1]}$ ${\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}$ ${\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}$ ${\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}$ ${\displaystyle O\left({\dfrac {t}{F_{0}}}\right)}$

手順2 K最小値

KMVの最初のt値を初期化する
a1のaをanにdoする
    h(a) < Max(KMV)の場合
        KMVセットからMax(KMV)を削除する
        KMVにh(a)を挿入する
    終了の場合
終わりのために
t/Max(KMV)を返す

KMVの複雑性分析

KMVアルゴリズムはメモリビット空間で実装できます。各ハッシュ値はメモリビット単位の空間を必要とします。ハッシュ値は のオーダーで存在します。t個のハッシュ値を二分木に格納すればアクセス時間を短縮できます。これにより、時間計算量は に削減されます。 ${\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}$ ${\displaystyle O(\log(m))}$ ${\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}$ ${\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}$

計算中F _k

アロンらは、与えられた空間と時間内で計算できるランダム変数を定義することでF _kを^{推定した。 [3]}ランダム変数の期待値はF _kのおおよその値を与える。

シーケンスの長さmが事前にわかっていると仮定します。そして、確率変数Xを以下のように構築します。

• シーケンスAのランダムな要素pを_pのインデックスで選択し、${\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}$
• は、 p_に続くシーケンスAのメンバー内でのlの出現回数を表します。${\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}$
• ランダム変数。${\displaystyle X=m(r^{k}-(r-1)^{k})}$

S _{1 が}次、S ₂が 次であると仮定します。アルゴリズムはS ₂を乱数として受け取り、中央値を出力します。ここで、Y _{i は}1 ≤ j ≤ S _1となるX _ijの平均です。 ${\displaystyle O(n^{1-1/k}/\lambda ^{2})}$ ${\displaystyle O(\log(1/\varepsilon ))}$ ${\displaystyle Y_{1},Y_{2},...,Y_{S2}}$ ${\displaystyle Y}$

ここで、確率変数E ( X )の期待値を計算してみましょう。

${\displaystyle {\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}}$

複雑さF _k

上で説明したF _kを計算するアルゴリズムから、各確率変数X はa _pとrの値を格納することがわかります。したがって、X を計算するには、 a _pを格納するためのlog( n )ビットとrを格納するためのlog( n )ビットのみが必要です。確率変数Xの総数は⁠ ⁠となります。 ${\displaystyle S_{1}*S_{2}}$

したがって、アルゴリズムが要する空間計算量は次のオーダーとなる。${\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}$

よりシンプルな計算方法F2_​

従来のアルゴリズムはメモリビットの順序で計算を行っていました。 ^[3]のAlonらは、このアルゴリズムを、4つの独立したランダム変数を用いて簡略化し、その値を にマッピングしました。 ${\displaystyle F_{2}}$ ${\displaystyle O({\sqrt {n}}(\log m+\log n))}$ ${\displaystyle \{-1,1\}}$

これにより計算の複雑さがさらに軽減され 、${\displaystyle F_{2}}$ ${\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}$

頻繁な要素

データストリームモデルにおける頻出要素問題とは、ストリームの一定の割合を超える要素の集合を出力することです。特殊なケースとして、過半数問題があります。これは、ある値がストリームの過半数を構成するかどうかを判定する問題です。

より正式には、正の定数c > 1 を固定し、ストリームの長さをmとし、ストリームにおける値iの頻度をf _iとします。頻出要素問題は、集合{ i | f _i > m/c } を出力することです。^[13]

注目すべきアルゴリズムは次のとおりです。

• ボイヤー・ムーア多数決アルゴリズム
• カウント・ミニットスケッチ
• 損失のあるカウント
• 多段ブルームフィルタ
• ミスラ・グリース重打者アルゴリズム
• ミスラ・グリース要約

イベント検出

データストリーム内のイベント検出は、上記のようなヘビーヒッターアルゴリズムを用いて行われることが多い。これらのアルゴリズムのいずれかを用いて、最も頻繁に出現する項目とその頻度を決定し、前回の時点からの最大の増加をトレンドとして報告する。このアプローチは、指数加重移動平均と分散を用いて正規化することで、より精度を高めることができる。^[14]

異なる要素を数える

ストリーム内の異なる要素の数を数える問題（ F ₀モーメントと呼ばれることもある）もよく研究されている。この問題に対する最初のアルゴリズムは、FlajoletとMartinによって提案された。2010年に、Daniel Kane、Jelani Nelson、David Woodruffはこの問題に対する漸近的に最適なアルゴリズムを発見した。^[15]このアルゴリズムは、 O ( ε ² + log d )の空間と、最悪のケースでO (1)の更新および報告時間、およびユニバーサルハッシュ関数とr単位の独立ハッシュ族（ r = Ω(log(1/ ε ) / log log(1/ ε )) ）を使用する。

エントロピ

周波数セットの（経験的）エントロピーは （）として定義されます。 ${\displaystyle \mathbf {a} }$ ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}$ ${\displaystyle m=\sum _{i=1}^{n}a_{i}}$

オンライン学習

トレーニング セットを 1 回通過して モデル (分類器など) を学習します。

• 特徴ハッシュ
• 確率的勾配降下法

下限

これまで研究されてきた多くのデータストリーミング問題において、下限値が計算されてきました。これまでのところ、これらの下限値を計算する最も一般的な手法は、通信複雑度を用いることです。^[要出典]

参照

• データストリームマイニング
• データストリームのクラスタリング
• オンラインアルゴリズム
• ストリーム処理
• シーケンシャルアルゴリズム

注記

1. Munro, J. Ian; Paterson, Mike (1978). 「限られた記憶域での選択とソート」.第19回コンピュータサイエンス基礎シンポジウム, 米国ミシガン州アナーバー, 1978年10月16～18日. IEEEコンピュータ協会. pp.  253– 258. doi :10.1109/SFCS.1978.32.
2. フラジョレ＆マーティン（1985）
3. アロン、マティアス、セゲディ (1996)
4. フェイゲンバウム, ジョアン; サムパス, カンナン (2005). 「セミストリーミングモデルにおけるグラフ問題について」.理論計算機科学. 348 (2): 207– 216. doi : 10.1016/j.tcs.2005.09.013 .
5. Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). 「データストリームシステムにおけるモデルと課題」.第21回ACM SIGMOD-SIGACT-SIGARTシンポジウム「データベースシステムの原理」議事録. PODS '02. ニューヨーク、ニューヨーク州、米国: ACM. pp.  1– 16. CiteSeerX 10.1.1.138.190 . doi :10.1145/543613.543615. ISBN  978-1-58113-507-7. S2CID  2071130。
6. Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). 「データストリーム内の個別要素のカウント」.コンピュータサイエンスにおけるランダム化と近似手法. コンピュータサイエンス講義ノート. 第2483巻. Springer, Berlin, Heidelberg. pp.  1– 10. CiteSeerX 10.1.1.12.6276 . doi :10.1007/3-540-45726-7_1. ISBN  978-3-540-45726-8. S2CID  4684185。
7. ギルバート他（2001）
8. 徐（2007）
9. Indyk, Piotr; Woodruff, David (2005-01-01). 「データストリームの周波数モーメントの最適近似」.第37回ACMコンピューティング理論シンポジウム議事録. STOC '05. ニューヨーク、ニューヨーク州、米国: ACM. pp.  202– 208. doi :10.1145/1060590.1060621. ISBN 978-1-58113-960-0. S2CID  7911758。
10. Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José DP; Vadhan, Salil (eds.).データストリーム内の個別要素のカウント. コンピュータサイエンスの講義ノート. Springer Berlin Heidelberg. pp.  1– 10. CiteSeerX 10.1.1.12.6276 . doi :10.1007/3-540-45726-7_1. ISBN  978-3-540-44147-2. S2CID  4684185。
11. モリス（1978）
12. Flajolet, Philippe (1985-03-01). 「近似計数：詳細な分析」. BIT Numerical Mathematics . 25 (1): 113– 134. CiteSeerX 10.1.1.64.5320 . doi :10.1007/BF01934993. ISSN  0006-3835. S2CID  2809103. 
13. Cormode, Graham (2014). 「Misra-Gries Summaries」. Kao, Ming-Yang (編). Encyclopedia of Algorithms . Springer US. pp.  1– 5. doi :10.1007/978-3-642-27848-8_572-1. ISBN 978-3-642-27848-8。
14. Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: ハッシュ化された重要度閾値によるテキストストリーム内の新興トピックのスケーラブルな検出. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. pp.  871– 880. doi :10.1145/2623330.2623740. ISBN 978-1-4503-2956-9。
15. ケイン、ネルソン、ウッドラフ（2010）

参考文献

• アロン、ノガ；マティアス、ヨッシ；セゲディ、マリオ（1999）「周波数モーメントの近似の空間計算量」、コンピュータとシステム科学ジャーナル、58（1）：137– 147、doi：10.1006/jcss.1997.1545、ISSN  0022-0000初版はAlon, Noga; Matias, Yossi; Szegedy, Mario (1996)「周波数モーメントの近似の空間計算量」、Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)、pp.  20– 29、CiteSeerX 10.1.1.131.4984、doi :10.1145/237814.237823、ISBN  978-0-89791-785-8、S2CID  1627911。
• バブコック, ブライアン; バブ, シヴナス; ダタール, マユール;モトワニ, ラジーヴ;ウィドム, ジェニファー(2002)「データストリームシステムにおけるモデルと問題点」第21回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム (PODS 2002) 議事録(PDF)、pp.  1– 16、CiteSeerX  10.1.1.138.190、doi :10.1145/543613.543615、ISBN 978-1-58113-507-7, S2CID 2071130, 2017年7月9日に オリジナル（PDF）からアーカイブ、 2013年7月15日取得。
• フラジョレ, フィリップ; マーティン, G. ナイジェル (1985). 「データベースアプリケーションのための確率的計数アルゴリズム」(PDF) . Journal of Computer and System Sciences . 31 (2): 182– 209. doi :10.1016/0022-0000(85)90041-8 . 2016年12月11日閲覧.
• Gilbert, AC ; Kotidis, Y.; Muthukrishnan, S .; Strauss, MJ (2001)、「ストリーム上のウェーブレットサーフィン：近似集約クエリのワンパスサマリー」（PDF）、大規模データベースに関する国際会議の議事録：79– 88。
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). 「個別要素問題に対する最適アルゴリズム」.第29回ACM SIGMOD-SIGACT-SIGARTデータベースシステム原理シンポジウム議事録. PODS '10. ニューヨーク、ニューヨーク州、米国: ACM. pp.  41– 52. CiteSeerX  10.1.1.164.142 . doi :10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. S2CID  10006932。。
• Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003)「ストリームとバッグ内の頻出要素を見つけるためのシンプルなアルゴリズム」、ACM Transactions on Database Systems、28 (1): 51– 55、CiteSeerX  10.1.1.116.8530、doi :10.1145/762471.762473、S2CID  952840。
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006). 「ネットワークトラフィックのエントロピー推定のためのデータストリーミングアルゴリズム」.コンピュータシステムの測定とモデリングに関する合同国際会議 (ACM SIGMETRICS 2006) の議事録. p. 145. doi :10.1145/1140277.1140295. hdl : 1802/2537 . ISBN 978-1-59593-319-5. S2CID  240982。。
• Xu, Jun (Jim) (2007)、「ネットワークデータストリーミングのチュートリアル」(PDF)。
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., 「限られた記憶域でのネストされた概念の学習」、Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777–782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991
• モリス、ロバート（1978）、「小さなレジスタ内の多数のイベントのカウント」、Communications of the ACM、21（10）：840–842、doi：10.1145/359619.359627、S2CID  36226357。