We thank the reviewer for taking the time to review our submission and for their helpful

We will elaborate on works relevant to the noiseless triplet setting in the related work section. Thank you also for pointing out the typos. That is an interesting way of looking at the problem. If the dataset consists of hierarchical clusters as in the condition for Theorem 4.6, This is made more explicit in the discussion following Theorem 4.4. Houle, Michael E., and Michael Nett (2013), Rank cover trees for nearest neighbor search, International Conference on