  High-quality machine learning models are dependent on access to high-quality
training data. When the data are not already available, it is tedious and
costly to obtain them. Data markets help with identifying valuable training
data: model consumers pay to train a model, the market uses that budget to
identify data and train the model (the budget allocation problem), and finally
the market compensates data providers according to their data contribution
(revenue allocation problem). For example, a bank could pay the data market to
access data from other financial institutions to train a fraud detection model.
Compensating data contributors requires understanding data's contribution to
the model; recent efforts to solve this revenue allocation problem based on the
Shapley value are inefficient to lead to practical data markets.
  In this paper, we introduce a new algorithm to solve budget allocation and
revenue allocation problems simultaneously in linear time. The new algorithm
employs an adaptive sampling process that selects data from those providers who
are contributing the most to the model. Better data means that the algorithm
accesses those providers more often, and more frequent accesses corresponds to
higher compensation. Furthermore, the algorithm can be deployed in both
centralized and federated scenarios, boosting its applicability. We provide
theoretical guarantees for the algorithm that show the budget is used
efficiently and the properties of revenue allocation are similar to Shapley's.
Finally, we conduct an empirical evaluation to show the performance of the
algorithm in practical scenarios and when compared to other baselines. Overall,
we believe that the new algorithm paves the way for the implementation of
practical data markets.
