OSTOR: Online Scheduling Framework for Trading Continuous Queries
Jin Cheng, Ningning Ding, John C. S. Lui, Jianwei Huang · 2025
Data trading significantly enhances data utility by enabling data sharing across diverse applications. Despite being crucial for real-time analytics and online machine learning, trading continuous queries with streaming data output remains largely unexplored. The inherent characteristics of trading continuous queries pose distinctive technical challenges in scheduling query execution. First, the streaming nature demands online scheduling under information uncertainty, where data utilities and execution costs vary unpredictably during query execution. Second, the intrinsic NP-hardness of the optimization problem, coupled with repeated invocation requirements, necessitates efficient algorithmic solutions to address computational complexity. We present OSTOR, the first online scheduling framework for trading continuous queries. OSTOR aims to maximize social welfare, defined as the difference between buyers' obtained utilities and sellers' execution costs, while achieving both theoretical guarantees and practical efficiency. To handle the information uncertainty, we present a primary-dual decomposition method that transforms the online scheduling problem into multiple one-round integer programming problems, enabling adaptive decision-making that only needs current system information. To address the computational complexity, we design an adaptive dual descent (ADD) algorithm that iteratively optimizes dual variables, achieving a bounded constant approximation ratio in polynomial time. We further enhance OSTOR through structureaware greedy optimization strategies with provable performance guarantees. Extensive experiments demonstrate that OSTOR substantially improves social welfare and reduces query execution costs on both real-world and synthetic datasets, compared to existing data trading methods.