2025-11-17T04:01:13.190278

Retroactive Monotonic Priority Queues via Range Searching

Castro, de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) and partially retroactive priority queues can cost $O(\log m)$ time per operation. So far, it is unknown whether this $O(\log m)$ bound can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue with a cost of $O(\log m + T(m))$ time per operation, where $T(m)$ is the maximum between the query and the update time of a specific range-searching data structure with $m$ elements. Finally, we design a fully retroactive monotonic priority queue that costs $O(\log m \log \log m)$ time per operation.

academic

範囲探索を用いた遡及的単調優先度キュー

基本情報

論文ID: 2508.09892
タイトル: Retroactive Monotonic Priority Queues via Range Searching
著者: Lucas Castro、Rosiane de Freitas（ブラジル UFAM コンピューティング研究所）
分類: cs.DS（データ構造とアルゴリズム）、cs.CG（計算幾何学）
発表日時: arXiv プレプリント、2025年10月14日更新
論文リンク: https://arxiv.org/abs/2508.09892

概要

現在知られている最適な完全遡及優先度キューは、1操作あたり $O(\log^2 m \log \log m)$ の時間を要します。ここで $m$ はデータ構造上で実行された操作の総数です。これに対して、標準的な（非遡及）および部分的に遡及可能な優先度キューは、1操作あたり $O(\log m)$ の時間しか必要としません。完全遡及優先度キューが $O(\log m)$ の境界に到達できるかどうかは現在のところ不明です。本論文は単調優先度キューという制限された変種を研究し、まず遡及的単調優先度キューにおける最小値の探索が範囲探索問題の特例であることを証明し、次に1操作あたり $O(\log m + T(m))$ の時間を要する完全遡及的単調優先度キューを設計し、最後に1操作あたり $O(\log m \log \log m)$ の時間を要する完全遡及的単調優先度キューを実装しました。

研究背景と動機

問題定義

従来のデータ構造は「現在」の状態のみを操作でき、過去の状態を照会または修正することはできません。遡及的データ構造は Demaine らによって導入され、過去の状態を修正し、その修正の結果を現在の状態に伝播させることができます。機能に応じて、以下のように分類されます：

部分的に遡及可能：過去を修正できますが、現在の状態のみを照会できます
完全に遡及可能：過去を修正でき、任意の時点の状態を照会できます

研究動機

効率の格差：完全遡及優先度キューと標準/部分的に遡及可能なバージョン間に顕著な時間計算量の格差が存在します
理論的課題：完全遡及優先度キューが $O(\log m)$ の理論的下限に到達できるかどうかは不明です
実用的応用：単調優先度キューは Dijkstra アルゴリズムなどのシナリオで重要な応用価値を持ちます

既存手法の限界

最適な完全遡及優先度キューの時間計算量は $O(\log^2 m \log \log m)$ です
標準優先度キューの $O(\log m)$ 計算量との間に大きな格差があります
制限された変種（単調優先度キューなど）に特化した研究が不足しています

核心的貢献

理論的発見：遡及的単調優先度キューにおける最小値の探索が範囲探索問題と等価であることを証明しました
汎用フレームワーク：時間計算量 $O(\log m + T(m))$ の完全遡及的単調優先度キューを設計しました。ここで $T(m)$ は範囲探索データ構造の照会/更新時間です
具体的実装：2次元範囲木に基づいて、時間計算量 $O(\log m \log \log m)$ の完全遡及的単調優先度キューを実装しました
幾何学的視点：遡及的優先度キューを理解するための新しい幾何学的視点を提供しました

方法の詳細説明

タスク定義

以下の操作をサポートする完全遡及的単調優先度キューを設計します：

Insert(insert(x), t)：時刻 $t$ に要素 $x$ を挿入します
Delete(insert(x), t)：時刻 $t$ の挿入操作を削除します
Insert(extract-min, t)：時刻 $t$ に最小値抽出操作を挿入します
Delete(extract-min, t)：時刻 $t$ の抽出操作を削除します
GetMin(t)：時刻 $t$ の最小要素を返します

単調性制約：抽出された要素は非減少数列を形成する必要があります。

核心的理論基礎

存在条件（補題14）

単調優先度キューにおいて、要素 $x$ が時刻 $t$ に存在するための必要十分条件は：

insertionTime(x) ≤ t
x > lastExtracted(t)

これにより、各要素の抽出時刻を維持する必要がなくなり、遡及操作の複雑性が簡素化されます。

最後に抽出された要素の効率的な探索（補題16-17）

重要な洞察：単調優先度キューにおいて、 $k$ 番目に小さい要素 val[k] は $k$ 番目の抽出操作 em[k] によってのみ抽出されます。

アルゴリズム：

抽出時刻木で時刻 $t$ の先行操作を見つけます
その操作の序号 $k$ を決定します
$k$ 番目に小さい要素を返します

時間計算量： $O(\log m)$

幾何学的表現（補題18）

単調優先度キューを2次元平面上の点として表現します：

各要素 $e$ は点 (insertionTime(e), e) として表現されます
GetMin(t) クエリは矩形 $R(t) = (-\infty, t] \times (\text{lastExtracted}(t), \infty)$ 内で $y$ 座標が最小の点を見つけることに変換されます

この表現により、優先度キューのクエリ問題が完全に幾何学的範囲探索問題に変換されます。

データ構造設計

3つの補助データ構造：

$T_{el}$ ：すべての挿入要素の順序統計木
$T_{em}$ ：すべての抽出時刻の順序統計木
$T_{ins}$ ：すべての (挿入時刻、要素値) ペアの最小-y 範囲探索データ構造

操作の実装：

GetMin(t)：まず lastExtracted(t) を見つけ、次に $T_{ins}$ で矩形範囲をクエリします
Insert/Delete(insert(x), t)： $T_{el}$ と $T_{ins}$ を更新します
Insert/Delete(extract-min, t)： $T_{em}$ を更新します

実験設定

理論分析フレームワーク

本論文は主に理論分析を実施し、以下の方法で方法の正確性を検証します：

数学的証明：すべての重要な補題と定理を厳密に証明します
計算量分析：各操作の時間および空間計算量を詳細に分析します
正確性検証：幾何学的直観とアルゴリズムロジックを通じて方法の正確性を検証します

範囲探索データ構造の選択

Mehlhorn と Näher の2次元範囲木を底層データ構造として選択します：

更新時間： $O(\log n \log \log n)$ （償却、最悪ケースに変換可能）
クエリ時間： $O(\log n \log \log n)$
空間計算量： $O(n \log n)$

実験結果

主要な理論的結果

定理20（汎用フレームワーク）：以下の計算量を持つ完全遡及的単調優先度キューが存在します：

抽出操作： $O(\log m)$
挿入操作： $O(\log m + U(m))$
クエリ操作： $O(\log m + Q(m))$
空間計算量： $O(m + S(m))$

ここで $U(m)$ 、 $Q(m)$ 、 $S(m)$ はそれぞれ範囲探索データ構造の更新、クエリ、空間計算量です。

定理21（具体的実装）： 2次元範囲木に基づく実装は以下の計算量を持ちます：

抽出操作： $O(\log m)$
挿入操作： $O(\log m \log \log m)$
クエリ操作： $O(\log m \log \log m)$
空間計算量： $O(m \log m)$

計算量の比較

データ構造の種類	時間計算量
標準優先度キュー	$O(\log m)$
部分的に遡及可能な優先度キュー	$O(\log m)$
完全遡及優先度キュー（既知の最適）	$O(\log^2 m \log \log m)$
本論文：完全遡及的単調優先度キュー	$O(\log m \log \log m)$