2024年7月6日～12日の7日間、国際会議 15th International Congress on Advanced Applied Informatics(IIAI-AAI 2024)が香川県高松市で開催され、大学院情報工学府 博士前期課程 情報創成工学専攻 2年の阿部大祐さんCompetitive Paper Award を受賞しました。

この論文は、根があり各頂点にラベルが付与されている根付きラベル付き木(以後、単に木という)に対する新たなヒストグラム距離として、各頂点vに対して、根からvへのパスのラベル列、vのラベル、vのすべての子孫の頂点のラベルの重集合からなる3つ組とその頻度からなる先祖パス子孫ラベルヒストグラム(以後、APDLヒストグラムという)を新たに導入し、2つの木に対するAPDLヒストグラムのL1距離を先祖パス子孫ラベルヒストグラム距離(以後,APDFヒストグラム距離という)として定式化しました。そして、APDLヒストグラムは木の頂点を2回走査するだけで計算でき、したがってAPDLヒストグラム距離は2つの木の頂点数に関する線形時間で計算できることを示しました。さらに、一般にヒストグラム距離はメトリックにならないが、APDLヒストグラム距離はメトリックになるこを示しました。したがって、APDLヒストグラム距離は、メトリックになるが計算に頂点数に関する3乗時間かかる編集距離の変種である孤立部分木距離に代わる木の距離となります。さらに、実データに対してAPDLヒストグラム距離と孤立部分木距離を計算してそれらの分布を比較しました。

【受賞対象】

受賞者の阿部大祐さん