Non-rigid whole-brain fiber streamline matching is a highly challenging technical problem in brain white matter analysis, largely due to the lack of reasonable vector-space representation and efficacious streamline distance measurement in the original curve space is computationally intractable. To address the issue of fast and accurate streamline distance measurement, we propose a fast fiber k-NN algorithm based on a strong relationship between point-wise K-NN and fiber-wise k-NN. Additionally , we propose a distance-preserving vector-space representation of the fiber streamlines based on a novel group-wise multi-dimensional scaling (MDS) technique. Based on the fast fiber k-NN and group-wise MDS, we propose a novel computationally tractable framework for non-rigid whole-brain white matter fiber matching. In this framework , our fast fiber k-NN algorithm is used to initialize the point-cloud matching in the vector space of the streamlines computed by the group-wise MDS. In our experiments, we show that our fast fiber k-NN algorithm reasonably approximates the exhaustive fiber k-NN search at a significantly reduced computational cost, the group-wise MDS effectively computes the vector representation in the aligned vector space, and our fast fiber matching method achieves higher accuracy for large displacement non-rigid whole-brain streamline matching compared to conventional image registration based streamline matching.