Efficient Computation of Pairwise Minimax Distance Measures

저자
Morteza Haghir Chehreghani
인용
ICDM, New Orleans, USA, 18 - 21 November 2017
초록

We study efficient computation of Minimax distances measures, which enable to capture the correct structures via taking the transitive relations into account. We analyze in detail two settings, the dense graphs and the sparse graphs. In particular, we show that an adapted variant of the Kruskal’s algorithm is the most efficient approach for computing pairwise Minimax distances. However, for dense graphs we require a preprocessing step based on the Prim’s algorithm, in order to reduce the set of candidate edges to be investigated. For each case, we study the correctness, efficiency and computational optimality of our approach. We perform numerical experiments on several datasets to validate the superior performance of our methods.

발행년도
2017
파일 다운로드
Efficient Computation of Pairwise Minimax Distance Measures.pdf (0.27MB)