Reconstructing approximate tree metrics

We introduce a novel measure called ε-four-pointscondition (ε-4PC), which assigns a value ε ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of ε-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the ε-4PC can be embedded into a tree with distortion (1+ε)c1log|X|, and (2) for every ε ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the ε-4PC that does not embed into a tree with distortion less than (1+ε)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of ε-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees.