Lower-Bound Distance Queries under Partial Information

Abstract

Given a metric space graph G ( V, E ) in which only a subset of edge distances is known, we study a query-based model for answering lower bound distance queries on unknown edges, without access to any black-box distance oracle. For a queried pair of objects ( u, υ ) with unknown distance, the lower bound corresponds to the minimum feasible value of d ( u, υ ) that satisfies all known distances and the triangle inequality constraints. We develop algorithmic techniques that operate directly on the partially observed graph to answer such queries efficiently. Our framework carefully balances preprocessing overhead, query processing time, and tightness of the produced bounds, while providing provable guarantees under metric assumptions. The proposed methods significantly improve both theoretical understanding and practical performance for lower bound inference, as validated through extensive experiments on multiple large-scale real-world datasets.