デビッド・マウント

デビッド・マウント
国籍	アメリカ人
母校	パーデュー大学
知られている	計算幾何学
科学者としてのキャリア
フィールド	コンピュータサイエンス
機関	メリーランド大学カレッジパーク校
博士課程の指導教員	クリストフ・ホフマン
Webサイト	マウント

デビッド・マウントはメリーランド大学カレッジパーク校のコンピュータサイエンス学部の教授であり、計算幾何学を研究しています。

マウントは 1977 年にパデュー大学でコンピュータ サイエンスの学士号を取得し、1983 年にクリストフ ホフマンの指導の下、パデュー大学でコンピュータ サイエンスの博士号を取得しました。

彼は1984年にメリーランド大学で教鞭をとり始め、現在は同大学のコンピュータサイエンス学部の教授を務めている。 ^[1]

教師として、彼は2005年と1997年にメリーランド大学コンピュータ数学・物理科学学部の優秀教育学部長賞を受賞したほか、2001年に香港科学技術大学工学部優秀教育賞など、その他の教育賞も受賞しています。

マウントの主な研究分野は計算幾何学であり、これは幾何学的性質の問題を解決するアルゴリズムの分野です。この分野には、最近点問題などの古典的な幾何学の問題だけでなく、曲線や面のコンピュータ表現やモデリングなどの最近の応用問題も含まれます。特に、マウントはk平均法クラスタリング問題、最近傍探索、点の位置問題に取り組んできました。

マウントは、 NP困難問題として知られるk平均法クラスタリングの実用的なアルゴリズムの開発に取り組んできました。最も一般的に使用されているアルゴリズムはロイドのアルゴリズムで、これは本質的にはヒューリスティックですが、実際には優れたパフォーマンスを発揮します。マウントと他の人たちは後に、 kd木を使用してロイドのアルゴリズムを高速化する方法を示しました^[2]。彼らはこのアルゴリズムを、いくつかの追加の改良とともにソフトウェアライブラリKmeansに実装しました。

マウントは、最近傍探索問題と近似最近傍探索問題に取り組んできました。アルゴリズムが最近傍クエリに対して近似解を返すようにすることで、空間計算量と時間計算量の大幅な高速化を実現できます。近似アルゴリズムの 1 つのクラスは、誤差距離 を入力として受け取り、効率的に格納でき (空間計算量が低い)、近似最近傍をすばやく返す (時間計算量が低い) データ構造を形成します。マウントは、Arya、 Netanyahu、R. Silverman、A. Wuとの共著論文^[3]で、近似最近傍問題が低次元の空間で効率的に解けることを示しました。その論文で説明されているデータ構造は、近似最近傍探索用の ANN オープンソース ライブラリの基礎となりました。^[4]その後の研究では、近似最近傍探索の計算量について調査しました。共著者の Arya と Malamatos とともに、 AVD (または近似ボロノイ図) と呼ばれるデータ構造に基づいて、近似最近傍探索の効率的な空間と時間のトレードオフを提供しました^[5${\displaystyle \epsilon }$${\displaystyle (1+\epsilon )}$

マウントは、ポイントの位置についても研究しており、これには、サイズの平面多角形サブディビジョンSを前処理して、クエリポイントが含まれるサブディビジョンのセルを決定することが含まれます。^[6]この論文では、クエリポイントがどのセルにあるかを尋ねられたときに、クエリポイントがどのセルにあるかの確率分布のエントロピーである予想時間で空間のデータ構造を構築する時間が示されています。 ${\displaystyle n}$${\displaystyle O(nlogn)}$${\displaystyle O(n)}$${\displaystyle H+O({\sqrt {H}}+1)}$${\displaystyle H}$

計算幾何学におけるアルゴリズムの設計と分析に加えて、マウントは次のようなソフトウェア ライブラリにおける効率的なアルゴリズムの実装にも取り組んできました。

• ANN - 近似最近傍探索
• ISODATA - 一般的なクラスタリングアルゴリズムの効率的な実装
• KMeans - k-means クラスタリング

2009 年 12 月 8 日現在、彼の最も引用されている作品 ( Google Scholarによる) とその主な貢献のリストが、引用数の降順で記載されています。

1. 固定次元での近似最近傍探索の最適アルゴリズム^[3] - この論文では、最近傍から最大で係数距離にある近傍を見つけるアルゴリズム（次元数と近似誤差の両方に依存）が示されています。${\displaystyle O(c_{d,\epsilon }\log(n))}$${\displaystyle c_{d,\epsilon }}$${\displaystyle d}$${\displaystyle \epsilon }$${\displaystyle (1+\epsilon )}$
2. 効率的なk-meansクラスタリングアルゴリズム：分析と実装^{[2] - この論文では、} k-meansクラスタリングで使用されるロイドのアルゴリズムのよりシンプルで効率的な実装が提供されています。このアルゴリズムはフィルタリングアルゴリズムと呼ばれます。
3. 離散測地線問題^{[7] - この論文では、与えられた（おそらく}非凸）多面体の表面上を移動する必要があるという制約の下で、ソースから目的地までの最短経路を計算します。彼らのアルゴリズムは、最初の目的地への最初の最短経路を見つけるのに時間がかかり、追加の目的地（同じソースから）への最短経路は時間内に計算できます。ここで、頂点の数は です。${\displaystyle O(n^{2}\log(n))}$${\displaystyle O(\log n)}$${\displaystyle n}$

マウントは「幾何学的データの解析と検索のためのアルゴリズムとデータ構造への貢献」により、2022年度のACMフェローに選出された。^[8]

• 公式サイト
• C++ のデータ構造とアルゴリズム
• Google 学術