WIREDに掲載されているすべての製品は、編集者が独自に選定したものです。ただし、小売店やリンクを経由した製品購入から報酬を受け取る場合があります。詳細はこちらをご覧ください。
この物語 のオリジナル版はQuanta Magazineに掲載されました。
コンピュータ科学者は理解しにくい抽象的な問題に取り組むことが多いですが、本と少なくとも一つの棚を持つ人にとって、画期的な新しいアルゴリズムは重要です。このアルゴリズムは、図書館のソート問題（より正式には「リストのラベル付け」問題）と呼ばれる問題に取り組んでいます。課題は、本を何らかの順序（例えばアルファベット順）で整理し、新しい本を棚に置くまでの時間を最小化する戦略を考案することです。
例えば、本を寄せ集めて棚に置いていて、棚の右端に空きスペースが残っているとします。イサベル・アジェンデの本をコレクションに加える場合、棚にある本をすべて移動させてスペースを空けなければならないかもしれません。これは時間のかかる作業です。さらにダグラス・アダムスの本を買ったら、また同じ作業を繰り返さなければなりません。より良い配置は、棚全体に空きスペースを残すことですが、具体的にはどのように配置すればよいのでしょうか？
この問題は1981年の論文で提起され、単に図書館員に整理の指針を提供するという枠にとらわれません。なぜなら、この問題はハードドライブやデータベース上のファイルの整理にも当てはまるからです。整理すべきアイテムは数十億個に及ぶこともあります。非効率的なシステムは、長い待ち時間と膨大な計算コストを意味します。研究者たちはアイテムを保管するための効率的な方法をいくつか発明してきましたが、最善の方法を模索し続けています。
昨年、シカゴで開催されたコンピュータサイエンスの基礎会議で発表された研究において、7人の研究者チームが、理論上の理想に非常に近い、アイテムを整理する方法を解説しました。この新しいアプローチは、本棚の過去の内容に関するわずかな知識と、ランダム性の驚くべき力を組み合わせたものです。
「これは非常に重要な問題です」と、ミシガン大学のコンピュータ科学者セス・ペティ氏は述べた。なぜなら、今日私たちが頼りにしているデータ構造の多くは、情報を順次格納しているからだ。彼はこの新しい研究を「非常に刺激的で、間違いなく今年の私のお気に入りの論文トップ3の1つだ」と評した。
境界を狭める
では、整理整頓された本棚の良し悪しを測るにはどうすればよいでしょうか。一般的な方法は、個々の本を入れるのにかかる時間を測ることです。当然、その時間はそもそも何冊の本があるのかによって異なり、その値は通常nで表されます。イサベル・アジェンデの例では、新しい本を入れるためにすべての本を移動させる必要がある場合、かかる時間はnに比例します。nが大きいほど、時間がかかります。つまり、これが問題の「上限」となります。つまり、本棚に1冊の本を入れるのにかかる時間は、 nに比例する時間よりも長くかかることはありません。
この問題を提起した 1981 年の論文の著者らは、平均挿入時間がnよりはるかに短いアルゴリズムを設計できるかどうかを知りたかった。そして実際、もっと良い方法があることを証明した。彼らは、平均挿入時間が (log n ) 2に比例することが保証されたアルゴリズムを作成した。このアルゴリズムには 2 つの特性があった。それは「決定論的」である、つまり決定がランダム性に左右されないこと、そして「滑らか」である、つまり挿入 (または削除) が行われる棚のサブセクション内に本が均等に広がっていなければならないことである。著者らは、上限をさらに改善できるかどうかという問題を未解決のまま残した。40 年以上もの間、誰もそれを成し遂げることができなかった。
しかし、その後数年間で下限値は改善されました。上限値は本を挿入するのにかかる最大時間を指定するのに対し、下限値は挿入にかかる最速時間を指定します。問題の決定的な解決策を見つけるために、研究者は上限値と下限値の差を縮めようと努力し、理想的には両者が一致するまで近づけます。一致した時点で、アルゴリズムは最適とみなされます。つまり、上下から容赦なく制限され、それ以上の改良の余地はなくなります。
2004年、ある研究チームは、図書館整理問題に対するアルゴリズムの最高の解、つまり究極の下限値はlog nであることを発見しました。この結果は、問題の最も一般的なバージョンに関するもので、あらゆるタイプのアルゴリズムに当てはまります。同じ著者2人は、1990年に、この問題のより具体的なバージョンについて既に結果を得ており、あらゆる滑らかなアルゴリズムの場合、下限値は(log n ) 2 と、それよりもはるかに高いことを示していました。そして2012年には、別のチームが、ランダム性を全く用いないあらゆる決定論的アルゴリズムについて、同じ下限値(log n ) 2 を証明しました。
これらの結果は、滑らかなアルゴリズムや決定論的なアルゴリズムでは、平均挿入時間を(log n ) 2より短くすることは不可能であることを示しており、これは1981年の論文で設定された上限と同じでした。言い換えれば、この上限を改善するには、研究者は異なる種類のアルゴリズムを考案する必要があるということです。「より優れた結果を出すには、ランダム性があり、滑らかではないアルゴリズムが必要です」と、ストーニーブルック大学のコンピューター科学者であるマイケル・ベンダー氏は述べています。
Michael Bender 氏は、必ずしも直感的に理解できるわけではないアプローチを使用して、ライブラリのソート問題に取り組みました。
写真提供：マイケル・ベンダーしかし、アイテムをほぼ均等に並べる必要がある滑らかさを捨て去るのは、間違いのように思えた。（最初の例で生じた問題を思い出してほしい。棚の左側にすべての本が密集し、滑らかでない配置になっていたのだ。）また、物事を偶然に任せること、つまりコイントスのように、それがどのように状況を改善するのかは明らかではなかった。「直感的に、それが理にかなった方向性だとは思えませんでした」とベンダー氏は言う。
それにもかかわらず、2022年にベンダー氏と5人の同僚は、ランダム化された非滑らかなアルゴリズムをとにかく試してみて、それが何か利点をもたらすかどうかを調べることにしました。
秘密の歴史
皮肉なことに、進歩は別の制約から生まれた。プライバシーやセキュリティ上の正当な理由から、本棚の履歴を考慮に入れないアルゴリズムを使う必要がある場合もある。「もし私の本棚に『フィフティ・シェイズ・オブ・グレイ』があって、それを取り出したとしても、誰にも気づかれないだろう」とカーネギーメロン大学のウィリアム・クズマウル氏は述べた。
ウィリアム・クズマウル、ベンダーらは、図書館ソート問題の上限を実質的に理想まで引き下げました。
写真：ローズ・シルバー2022年の論文で、ベンダー、クズマウル、および4人の共著者は、まさにそのようなアルゴリズム（「履歴に依存しない」、非滑らかでランダムなアルゴリズム）を作成し、最終的に1981年の上限を引き下げ、平均挿入時間を（log n）1.5まで短縮しました。
クズマウル氏は、通常はプライバシー確保のために使われるツールが、他の利点ももたらすことに驚いたことを覚えている。「まるで暗号技術を使ってアルゴリズムを高速化したかのようです」と彼は言った。「ちょっと奇妙に思えます」
この研究チームには参加していないジョージア工科大学のヘレン・シュー氏も感銘を受けており、セキュリティ以外の理由で履歴独立性を利用するという考えは、他の多くの種類の問題にも影響を与える可能性があると述べた。
ギャップを埋める
ベンダー、クズマウルらは昨年の論文でさらに大きな進歩を遂げました。彼らは再び記録を破り、上限を(log n )×(log log n ) 3まで引き下げました。これは(log n ) 1.000…1に相当します。言い換えれば、彼らは理論限界、つまりlog nの究極の下限に非常に近づいたのです。
今回も彼らのアプローチは滑らかではなくランダムなものだったが、今回はアルゴリズムが歴史への依存度を限定的にした。過去の傾向を参考にして将来の出来事を予測していたが、それも限界があった。例えば、ナボコフ、ネルーダ、ンなど、姓がNで始まる作家の本をたくさん手に入れているとしよう。アルゴリズムはそこから推測し、今後もさらに出版されるだろうと想定して、Nのセクションに少し余裕を持たせる。しかし、スペースをあまりに多く確保しておくと、Aの名を持つ作家が大量に出版され始めた場合に問題が生じる可能性がある。「これをうまく機能させたのは、判断を下す際にどの程度の歴史を参照するかを戦略的にランダムにすることでした」とベンダー氏は述べた。
この結果は、彼らの以前の研究を基盤とし、それを変革した。「2022年の論文とは全く異なる方法でランダム性を利用している」とペティ氏は述べた。
シカゴ大学のコンピューター科学者、ブライアン・ウィートマン氏は、これらの論文は理論面で「大きな進歩」を示していると述べ、「そして応用面でも、大きな進歩の可能性を秘めていると思います」と続けた。
Xu氏も同意見だ。「ここ数年、動的なグラフの保存と処理にリストラベリングに基づくデータ構造の利用が注目されています」と彼女は述べた。こうした進歩は、ほぼ確実に処理速度を向上させるだろう。
一方、理論家たちが検討すべき点はまだある。「log n はほぼ実現可能であることは分かっています」とベンダー氏は述べた。「しかし、まだ小さなギャップが残っています」。log log nという小さな項が、完全な解への道を阻んでいるのです。「上限を下げるのが正しいのか、下限を上げるのが正しいのか、まだ分かりません。」
ペティー氏は、下限が変わるとは考えていない。「通常、このような状況では、これほど近い差があり、一方の境界は極めて自然に見え、もう一方の境界は不自然に見える場合、自然な境界が正解です」と彼は述べた。しかし、将来の改善によって上限が影響を受け、log nまで下がる可能性の方がはるかに高い。「しかし、世の中には奇妙な驚きが満ち溢れているのです。」
オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。
