遡及的データ構造

コンピュータサイエンスにおいて、遡及的データ構造とは、構造に対して実行された一連の操作に対する効率的な変更をサポートするデータ構造のことである。これらの変更は、過去のある時点で実行された操作の遡及的な挿入、削除、または更新の形をとることができる。^{[ 1 ]}

遡及的データ構造のいくつかの応用例

現実世界では、一連の操作の中から過去の操作を修正したいケースが数多くあります。以下に、考えられる応用例をいくつか示します。

エラー訂正：データの入力ミス。データを修正し、誤ったデータによる二次的な影響をすべて除去する必要があります。
不良データ：大規模なシステム、特に大量の自動データ転送を伴うシステムでは、不良データが発生することは珍しくありません。例えば、気象観測ネットワークのセンサーの1つが故障し、ゴミデータや誤ったデータを報告し始めたとします。理想的な解決策は、センサーの故障以降に生成されたすべてのデータと、不良データがシステム全体に及ぼしたすべての影響を削除することです。
復旧：ハードウェアセンサーが損傷したが、修理されてセンサーからデータを読み取れるようになったとします。センサーが最初から損傷していなかったかのように、データをシステムに再挿入できるようにしたいと考えます。
過去の操作：過去を変えることは、損害制御の場合に役立つことがあり、遡及的なデータ構造は、過去を意図的に操作するために設計されています。

空間次元としての時間

時間を追加の空間次元として考えることはできません。これを説明するために、時間の次元を空間軸にマッピングすると仮定します。空間的な時間次元を追加するために使用するデータ構造は、最小ヒープです。y軸はヒープ内の項目のキー値を表し、x軸は空間的な時間次元を表します。いくつかの挿入と最小削除操作（すべて遡及的に行われません）の後、最小ヒープは図1のようになります。次に、操作リストの先頭にゼロを遡及的に挿入すると仮定します。最小ヒープは図2のようになります。単一の操作がデータ構造全体に影響を与える連鎖的な効果を生み出すことに注目してください。このように、時間を空間次元として描くことはできますが、時間に関わる操作は、時間に関して変更を加えると波及効果をもたらす依存関係を生み出すことがわかります。

持続性との比較

一見すると、遡及的データ構造の概念は、どちらも時間の次元を考慮に入れるため、永続的データ構造と非常によく似ているように思えます。永続的データ構造と遡及的データ構造の主な違いは、時間の要素をどのように扱うかです。永続的データ構造は、データ構造の複数のバージョンを保持し、あるバージョンに対して操作を実行して、データ構造の別のバージョンを生成できます。各操作によって新しいバージョンが生成されるため、各バージョンは変更できないアーカイブになります（そこから新しいバージョンのみを生成できます）。各バージョンは変更されないため、各バージョン間の依存関係も変更されません。遡及的データ構造では、以前のバージョンに直接変更を加えることができます。各バージョンは相互依存しているため、1つの変更が後続のすべてのバージョンに波及効果を引き起こす可能性があります。図1と図2は、この波及効果の例を示しています。

意味

どのようなデータ構造も、遡及的な設定で再定式化できます。一般に、データ構造は、一定期間にわたって行われる一連の更新とクエリを含みます。t ₁からt _{mまでの更新操作のシーケンスを U = [u}_{t ₁} , u _{t ₂} , u _{t ₃} , ..., u _{t _m} ] とします。ただし、t ₁ < t ₂ < ... < t _mとします。ここでの仮定は、与えられた時間 t に対して実行できる操作は最大で 1 つであるということです。

一部遡及適用

データ構造が部分的に遡及的であるとは、現在時点で更新操作とクエリ操作を実行でき、かつ過去における挿入操作と削除操作をサポートできる場合を指します。したがって、部分的に遡及的であるデータ構造については、以下の操作に関心があります。

Insert(t, u): 時刻 t にリスト U に新しい操作 u を挿入します。
Delete(t): 時刻 t の操作をリスト U から削除します。

上記の遡及的な操作を考慮すると、標準的な挿入操作は Insert(t, "insert(x)") の形式になります。データ構造の操作履歴に対するすべての遡及的な変更は、操作が行われた時点から現在までのすべての操作に影響を与える可能性があります。たとえば、t _i-1 < t < t _i+1の場合、Insert(t, insert(x)) は、操作op _i-1とop _i+1の間に新しい操作op を挿入します。データ構造の現在の状態 (つまり、現在の時点のデータ構造) は、操作op _i-1、op、op _i+1がすべて連続して発生した状態となり、操作op が常に存在していたかのようになります。図 1 と図 2 を参照してください。

完全に遡及適用

部分的な遡及操作に加えて、過去に関するクエリも実行できる場合、データ構造は完全に遡及的であると定義します。部分的な遡及モデルでは標準操作 insert(x) が Insert(t, "insert(x)") となるのと同様に、完全遡及モデルでは操作 query(x) は Query(t, "query(x)") の形式になります。

遡及的な実行時間

遡及的データ構造の実行時間は、構造に対して実行される操作の数m、遡及的操作が実行される前に実行された操作の数r 、および任意の時点で構造内に存在する要素の最大数nに基づいて決定されます。

自動的な遡及活動

データ構造に関する自動的な遡及処理に関する主な疑問は、任意のデータ構造を効率的な遡及処理可能なデータ構造に変換できる一般的な手法が存在するかどうかです。単純なアプローチとしては、適用する遡及処理の前に構造に対して行われたすべての変更をロールバックする方法があります。データ構造を適切な状態にロールバックしたら、遡及処理を適用して目的の変更を行うことができます。変更が行われたら、データ構造を新しい状態にするために、以前にロールバックしたすべての変更を再適用する必要があります。この方法は任意のデータ構造に適用できますが、ロールバックする必要のある変更の数が多い場合は特に非効率的で無駄が多いことがよくあります。効率的な遡及処理可能なデータ構造を作成するには、構造自体の特性を調べて、どこで高速化を実現できるかを判断する必要があります。したがって、任意のデータ構造を効率的な遡及処理可能なデータ構造に変換する一般的な方法はありません。Erik D. Demaine、John Iacono 、およびStefan Langerman がこれを証明しています。^{[ 1 ]}

参考文献

1 2 Demaine, Erik D. ; Iacono, John ; Langerman, Stefan (2007). "Retroactive data structures" . ACM Transactions on Algorithms . 3 (2): 13. doi : 10.1145/1240233.1240236 . S2CID 5555302. 2012年4月21日取得。