Tele-Rehabilitation as a Service (TRaaS) has recently emerged as a technique allowing remote patients with motor impairments to be monitored and treated directly in their homes. The objective of this paper is twofold: i) studying how Machine Learning (ML) can improve the TRaaS, and ii) demonstrating how a NoSQL graph database approach can enhance the performance because it works directly at the database layer instead of at the application one. In particular, the K-Nearest Neighbors (K-NN) algorithm is studied in order to improve a robotic rehabilitation therapy using the Lokomat device as case of study. Experiments compare two system prototypes, that are respectively based on Python and Neo4j, showing that the latter presents better performance in terms of processing time guaranteeing the same accuracy.