Using light, Fiber Optic RealShape (FORS) technology enables real-time, 3D visualization of compatible guidewires and catheters inside the body. FORS generates 3D position data and other related features, such as twist and strain, in high temporal resolution. Storing data during procedures is crucial to obtaining technical insights to improve devices enabled by FORS technology and deploy it for new types of clinical procedures. Continuous shape sensing leads to substantial data streams (amounting to 1 GB of data for less than 4.5 min of a procedure) that may restrict storage during interventions and impede post-operative analysis, thus requiring data compression. In this paper, we present a novel method for the problem of compressing data streams recorded while tracking devices during minimally invasive surgeries using FORS technology. The proposed approach represents the 3D FORS shapes via natural cubic splines (NCS) as a small set of subsampling points (knots), making it efficient for compression. In addition, we propose an adaptive heuristic algorithm to optimize the NCS fit, resulting in effective and low-loss compression of the shapes. The presented method outperforms previous shape compression methods by a factor of 3 in compression ratio. This improvement is achieved, for example, compared to the PCA dimensionality reduction method at the same level of distortion. Moreover, it achieves a better compression rate while preserving the spatial and curvature signals in real-time.