Beyond Pairwise: Provably Fast Algorithms for Approximate K-Way Similarity Search