Streaming Classical Multidimensional Scaling

Multidimensional scaling (MDS) is a widely used embedding method that preserves the similarity among data items in the embedded low dimensional space. While MDS has shown great versatility, it is computationally expensive and non-scalable as it requires operation on the whole data distance matrix. This can be problematic when the dataset is not fixed but is constantly growing over time, such as in streaming applications. To address this problem, we introduce a streaming, one-pass, limited memory version of the classical MDS algorithm, named scMDS, specifically designed for streaming high-dimensional data. In scMDS, m-dimensional samples are arriving sequentially and are embedded in a k-dimensional subspace (k ≪ m) with high approximation quality to batch classical MDS (cMDS). It also reduces the time complexity from O(mn ² ) to O(mn _t ² ), where n is the size of the data stream and n _t is the size of a data batch at time-streaming data processing we pair our algorithm with a t (n _t ≪ n). To overcome the concept-drift during novel realignment method.