New Algorithmic Tools for Distributed Similarity Search and Edge Estimation