  Distance queries are a basic tool in data analysis. They are used for
detection and localization of change for the purpose of anomaly detection,
monitoring, or planning. Distance queries are particularly useful when data
sets such as measurements, snapshots of a system, content, traffic matrices,
and activity logs are collected repeatedly.
  Random sampling, which can be efficiently performed over streamed or
distributed data, is an important tool for scalable data analysis. The sample
constitutes an extremely flexible summary, which naturally supports domain
queries and scalable estimation of statistics, which can be specified after the
sample is generated. The effectiveness of a sample as a summary, however,
hinges on the estimators we have.
  We derive novel estimators for estimating $L_p$ distance from sampled data.
Our estimators apply with the most common weighted sampling schemes: Poisson
Probability Proportional to Size (PPS) and its fixed sample size variants. They
also apply when the samples of different data sets are independent or
coordinated. Our estimators are admissible (Pareto optimal in terms of
variance) and have compelling properties.
  We study the performance of our Manhattan and Euclidean distance ($p=1,2$)
estimators on diverse datasets, demonstrating scalability and accuracy even
when a small fraction of the data is sampled. Our work, for the first time,
facilitates effective distance estimation over sampled data.
