TL;DR
This paper introduces Non-negative Snowflake Factorization of Tensors (NSFT), a novel method for predicting missing Quality of Service (QoS) data in dynamic Web service environments. By utilizing a specialized "snowflake" core tensor and a non-negative multiplicative update rule, the model captures complex temporal patterns in user-service interactions more accurately than traditional matrix or tensor factorization methods.
What Problem Does This Paper Address?
In the world of cloud computing, users must choose between thousands of functionally similar Web services. To make the best choice, they rely on Quality of Service (QoS) metrics like response time and throughput. However, the data is "High-Dimension and Incomplete" (HDI): most users only interact with a tiny fraction of available services, and these interactions change over time.
Existing solutions often use Matrix Factorization, which collapses the time dimension, losing crucial temporal dynamics. While standard Tensor Factorization (like Tucker decomposition) can handle time, it often struggles with the extreme sparsity of real-world data or fails to enforce non-negativity (e.g., predicting a physically impossible negative response time). The authors aim to bridge this gap with a model that is both temporally aware and robust to sparse data.
Methods
The authors propose the NSFT model, which builds upon the foundations of Tucker decomposition but introduces three key innovations:
- Snowflake Core Tensor: Instead of a dense core tensor that models every possible interaction between latent features, the authors design a "snowflake" structure. This specifically models the relationships between latent features of users, services, and time slices in a way that enhances the model's learning capability for dynamic patterns.
- Linear Bias (LB) Terms: Recognizing that individual users, services, or time periods have inherent "baselines" (e.g., a specific user always has a slow connection), the model incorporates linear bias vectors ($a, b, c$) to stabilize predictions.
- SLF-NMUT Learning Rule: To ensure all predicted values remain non-negative, the authors employ a Single Latent Factor-based Non-negative Multiplicative Update on Tensor. This algorithm tunes learning rates to eliminate negative components during the gradient descent process, ensuring the model parameters remain physically meaningful.
Datasets
The model was evaluated using two large-scale, authentic QoS datasets from the WS-DREAM repository:
- QoS-RT (Response Time): Values ranging from 0–20 seconds.
- QoS-TP (Throughput): Values ranging from 0–1000 kbps.
Both datasets track 142 users invoking 4,500 services over 64 time slices, totaling over 30 million service invocation logs with a density of approximately 74.06%.
Key Insights and Ideas
- Structured Sparsity: By using a "snowflake" core tensor rather than a fully dense one, the model focuses on the most relevant feature interactions, which prevents overfitting in highly sparse environments.
- The Importance of Non-negativity: QoS metrics are inherently non-negative. By enforcing this constraint directly in the learning rule (SLF-NMUT) rather than as a post-processing step, the model achieves more stable and realistic convergence.
- Temporal Fluctuations are Unique: The paper highlights that every user-service pair has its own "distinctive pattern of change." The inclusion of linear biases allows the model to separate these individual "baselines" from the complex three-way interactions.
Key Results
The NSFT model (labeled M4 in the paper) was compared against state-of-the-art baselines including CP-SGD, NNCP, and CTF. Across various training/testing splits (D1 through D4):
- Accuracy: NSFT consistently achieved the lowest Mean Absolute Error (MAE) and Root Mean Square Error (RMSE).
- Significant Gains: On the throughput dataset (D4), NSFT showed an MAE improvement of up to 3.9% over the standard CP-SGD model.
- Robustness: The model maintained high predictive accuracy even as the proportion of missing entries increased, suggesting it is well-suited for real-world, large-scale deployments where data is often missing.
Limitations and Future Work
While the NSFT model performs well on structured tensor data, the authors note several areas for expansion:
- Deep Learning Integration: The current model is a "shallow" factorization method. The authors suggest that integrating deep learning techniques could further capture non-linear temporal dynamics.
- External Variables: The model currently relies solely on historical QoS logs. It does not yet incorporate "side information" such as user geographic location, network topology, or environmental variables that might influence service performance.
- Scalability: While the update rules are efficient, the authors plan to explore more advanced optimization strategies to handle even larger, more complex datasets in future iterations.
Summary updated