The transmission and storage of global navigation satellite system (GNSS) data places very high demands on mobile networks and centralised data processing systems. GNSS applications including community based navigation and fleet management require GNSS data to be transmitted from a vehicle to a centralised system and then processed by a map-matching algorithm to determine the location of a vehicle within a road segment. Various data compression techniques have been developed to reduce the volume of data transmitted. There is also an independent literature relating to map-matching algorithms. However, no previous research has integrated data compression with a map-matching algorithm that accepts compressed data as an input without the need for decompression. This paper develops a novel GNSS data reduction algorithm with deterministic error bounds, which was seamless integrated with a specifically designed map-matching algorithm. The approach significantly reduces the volume of GNSS data communicated and improves the performance of the map-matching algorithm. The data compression extracts critical points in the trajectory and velocity–time curve of a vehicle. During the process of selecting critical points, the error of restoring vehicle trajectories and velocity–time curves are used as parameters to control the number of critical points selected. By setting different error bound values prior to the execution of the algorithm, the accuracy and volume of reduced data is controlled precisely. The compressed GNSS data, particularly the critical points selected from the vehicle’s trajectory is directly input to the map-matching algorithm without the need for decompression. An experiment indicated that the data reduction algorithm is very effective in reducing data volume. This research will be useful in many fields including community driven navigation and fleet management.