Online Sample Selection for Resource Constrained Networked Systems

Abstract: As more devices with different service requirements become connected to networked systems, such as Internet of Things (IoT) devices, maintaining quality of service becomes increasingly difficult. Large data sets can be obtained ahead of time in networks to train prediction models offline, however, resulting in high computational costs. Online learning is an alternative approach where a smaller cache of fixed size is maintained for training using sample selection algorithms, allowing for lower computational costs and real-time model re-computation. This project has resulted in two newly designed sample selection algorithms, Binned Relevance and Redundancy Sample Selection (BRR-SS) and Autoregressive First, In First Out-buffer (AR-FIFO). The algorithms are evaluated on data traces retrieved from a Key Value store and a Video on Demand service. Prediction accuracy of the resulting model while using the sample selection algorithms and the time to process a received sample is evaluated and compared to the pre-existing Reservoir Sampling (RS) and Relevance and Redundancy Sample Selection (RR-SS) with and without model re-computation. The results show that, while RS maintains the lowest computational overhead, BRR-SS outperforms both RS and RR-SS in prediction accuracy on the investigated traces. AR-FIFO, with its low computational cost, outperforms offline learning for larger cache sizes on the Key Value data set but shows inconsistencies on the Video on Demand trace. Model re-computation results in reduced error rates and significantly lowered variance on the investigated data traces, where periodic model re-computation overall outperforms change detection in practicality, prediction accuracy, and computational overhead.