Retaining Data from Streams of Social Platforms with Minimal Regret

1 Introduction

Current social platforms such as Twitter, Facebook, and Yelp, produce data streams with an unprecedented rate. For example, about half a billion tweets are generated every day [Mathioudakis and Koudas, 2010]. To make sense of these streams, one can typically only retain a small fraction of the data for analysis, due to storage limits and the cognitive load induced by the sheer data volume.

Against this background, traditional methods for the analysis of social platforms perform data summarization, e.g., based on relevance detection or measures of information diversity [Chang et al., 2016]. However, these approaches are inherently limited to a static setting: The data is crawled and stored, before the top-k most important data items are selected as a data summary. Even if feasible, such an approach incurs high storage cost and does not avoid the problem of retaining only a fraction of the data once its volume exceeds a storage limit.

In this paper, we consider the natural setting of social platforms, where data is dynamic and available as a stream. Then, retaining of data becomes more challenging compared to oneoff summarization, as data selection has to be repeated every time new data arrives. Instead of considering the whole historical data, summarization now works on the retained data

∗Corresponding author

(i.e., a previous summary) and the new data. This further degrades the informativeness of the original data since the summary of the retained data already induces some loss of information. Specifically, the lack of historical data leads to a biased assessment of data importance: Data that was considered unimportant and thus discarded in the past may retrospectively turn out to be important.

To minimize the regret of discarding important data, two requirements have to be met. First, a compact data sketch needs to be maintained, in addition to the actual data summary, to capture the long-term history of data and enable a precise assessment of data utility over time. Yet, for data stemming from social platforms, this sketch needs to be adaptive to changes in the data stream. Second, a protocol needs to be specified to decide which data items to retain and to discard, such that the total regret in data utility is minimal. To cope with the data stream volume and velocity of social platforms, this protocol needs to be very efficient.

In this paper, we tackle these requirements and propose a novel statistical model, which does not only capture the traditional context of social data (importance of topics, user influence, information diffusion), but also embeds the dynamics of this context over time. For example, topics are not considered to be static. They may emerge or disappear over time and relate to recurring events. Striving for online processing of streaming data, we develop a scalable learning mechanism to quickly update the model with new data. We further show how the statistical model is used to define a utility function to assess the representativeness of a data summary. Minimizing the regret of discarding data then becomes the problem of minimizing the difference between the utility of the retained data and the utility of whole historical data. Finally, we present a progressive algorithm to select which data to retain, with guarantees on the induced regret factor. This algorithm scales linearly in time and space, solely in the size of the data summary (not the whole data stream).

Our contributions and the paper structure are summarized as follows. After outlining the retaining problem with minimal regret (§2), we present (i) a statistical model to sketch data properties; (ii) a utility function to assess data representativeness (§3); and (iii) a progressive algorithm to solve the retaining problem (§4). Using diverse datasets derived from Twitter, we demonstrate improvements of five orders of magnitude in efficiency and up to 42% in information quality of our approach over state-of-the-art baselines (§5). We then review related work (§6) and conclude the paper (§7).

2 Problem Statement

We model the stream of data stemming from a social platform by an infinite set of textual data items E = {e1, e2, . . .}. The items are totally ordered based on their occurrence time, denoted by the subscript. By Et = {e1, . . . , et}, we denote the set of items until time t. Acknowledging that not all items from E can be stored permanently, a representative subset of E of size k shall be retained. Here, the parameter k depends on the application context and typically reflects the storage limit. We further postulate a non-negative function f : 2E → R≥0 to quantify the utility of a set of items S ⊆ E, capturing how well S represents E according to some objective. Given that E is continuously extended with new data items, the retaining problem with minimal regret is to select k items, such that the regret ratio-the normalized difference between the utility of the retained items and the utility of the whole data stream-is minimal.

Problem 1 (Retaining Problem with Minimal Regret). Given a data stream Et until time t, a current set of retained items St ⊆ Et, a window of new data items W = {et+1, . . . , et+|W|}, the problem is to construct a new set of retained items St+w, such that:

The problem setting is illustrated in Figure 1. Upon the arrival of a window of new items, the set of retained items is updated. This is done by selecting items from the old set of retained items and from the window.

The figure further illustrates why the retaining problem with minimal regret cannot be addressed by applying traditional data summarization each time a window of new data items arrives. Traditional summarization would consider solely the current set of retained items and the items of the new window. Yet, the data stream history in terms of items discarded in the past would be neglected. Consequently, when constructing a new set of retained items, the utility of possible candidate sets cannot be assessed accurately.

As illustrated in Figure 1, therefore, a concise sketch of

historical data needs to be maintained. It captures essential

properties of data items that have been discarded in the past,

thereby enabling an accurate assessment of the regret ratio

of a potential set of retained items. To realise such a sketch,

§3 presents a statistical model and also shows how to assess the representativeness of an item set using an utility function. In §4, we then present a progressive algorithm to solve the retaining problem with minimal regret under this model.

3 Model and Approach

Below, we first propose a statistical model to sketch the historical data of a stream, before turning to the question of how to assess the utility of a set of retained data items. Finally, we discuss a simple strategy to solve the retaining problem.

3.1 A Statistical Model for Social Data

For textual data items that originate from social platforms, topics are a fundamental concept to understand the cooccurrence relations of words [Cha et al., 2013]. We thus capture information on topics as a statistical means to select representative data items from important clusters of words. However, the dynamic nature of streaming data from social platforms prevents us from knowing a specific distribution of topics in some future state. Rather, we face the following phenomena:

• Emergent topics: In a streaming setting, new topics may emerge over time. Hence, topic modelling techniques such as LDA [Blei et al., 2003] or pLSI [Hofmann, 1999] that fix a pre-defined number of topics are not applicable. A small number of topics may lead to information loss, as different words might end up in the same cluster, whereas a large number of topics may imply sparse clusters, destroying data regularities.
• Emergent vocabulary: An evolving collection of topics implies that the vocabulary of words changes over time. Words may only be invented at a specific time [Zhai and Boyd-Graber, 2013] (e.g., 'brexit' during the events in the UK in June 2016). A fixed vocabulary as in traditional topic models does not capture these dynamics and tends to be inefficient due to unused and redundant words.
• Recurring topics: Traditional data summarization typically spans a short period of time [Chakrabarti and Punera, 2011], due to data storage limits. In contrast, when processing data streams of social platforms, a long history of data items is considered, so that topics will recur over time [Herrera-Damas, 2014] (e.g., the topic of 'football' shows seasonal patterns). Such effects influence the decision of which data items to retain.

Against this background, we propose a non-parametric [Hollander et al., 2013] probabilistic model to sketch the properties of past data items. It features a potentially unbounded number of topics and words that are learned from textual data items over time. It also considers recurrent topics by means of temporal cluster variables, for which the time granularity can be customised.

Formally, a textual data item e is modelled as a multiset of words {v1, . . . , v|e|}, where vi is a word from a dynamic vocabulary V . A multiset of words further defines a semantic topic z. We model the dynamics of words per topic by means of a Dirichlet process to generate the word distribution φz and the vocabulary ρz of a topic z. Further, at time t, a topic distribution θ is used to generate the topics of a new data item et. To ensure that the temporal aspect of evolving topics is reflected in the generation, we use a hierarchical Dirichlet process to establish the link between data items in terms of topics. This yields a a concise and consistent set of topics rather than a sparse and unnecessarily large one. Finally, we model the recurring topics by means of temporal clusters, whose number is unbounded in general. To this end, a Chinese restaurant process [Blei et al., 2010] τ is used to non-parametrically generate a temporal cluster label ct for each data item et. The model is summarised in Figure 2.

Generative process. The generative process for our model is defined as follows. For each item et ∈ E at time t:

1. Generate the lengths (number of words) of et from a Poisson distribution:
2. Ne ∼ Poiss(ϵ)
3. Generate the temporal cluster label of et from a multinomial distribution:
4. Generate the topic of et from a categorical distribution: ct ∼ Cat(τ)

ht|ct, π ∼ Mult(πct )

where the value of ht depends on the granularity according to which the topic distribution is captured for the data stream (e.g., ht has a value of 31 to model topics per day of a month).

1. For each of the i = 1 . . .Ne word indices of et:
2. Generate a topic from a multinomial distribution: zi|ct, θ ∼ p(z|t) ≜ Mult(θct )
3. Generate a word vi from zi via a multinomial distribution:

vi|zi, φ, ρ ∼ p(v|z) ≜ Multρzi (φzi ) where ρz is a vocabulary generated from an n-gram model and φz is the probability of selecting ρz for word vi [Zhai and Boyd-Graber, 2013].

Model parameters. The sketch of historical data is designed by parametrising the model as follows. The sketch is denoted by Θ = (α, G0, λ, γ, ζ, η, ϵ), a vector of parameters for:

• The Dirichlet process to generate ρ and φ: ρzk, φzk ∼ DP(α,G0), for t = 1, 2, . . . and k = 1, 2, . . ..
• The hierarchical Dirichlet process to generate θ: β ∼ GEM(γ), θc ∼ DP(λ, β), for c = 1, 2 . . .
• The Chinese restaurant process to generate τ:
• τ ∼ CRP(ζ)

• The Dirichlet distribution to generate π:

This parametrisation of the model yields a compact, lightweight sketch of historical data. Since it contains solely single-variable parameters, it has constant-space requirements. In §4, we will show how to update the model parameters based on a data stream by means of an incremental inference mechanism.

3.2 Utility of Retained Data

To judge how well a set of retained data items stemming from social platforms represents a whole data stream, we argue that the following aspects shall be considered: First, semantic information such as topics and word frequencies has to be incorporated, see [Morstatter et al., 2013]. Second, the importance of data from social platforms is influenced by the social context (e.g., the authors of a textual statement) and its freshness, as the interestingness of social data degrades over time. Given the above sketch of historical data Θ(t) at time t, these incorporate these aspects in the assessment of data utility as follows.

On semantic information. We first consider the probability p(v, e) for observing a word w in a data item e at time t. It is defined based on the evolution of topics over time as

where p(v|z) represents the probability distribution of words given a topic, and p(z|Θ(t) ) represents the probability distribution of topics at time t. The latter is derived from sketch Θ by the aforementioned generative distributions.

Based thereon, the probability of an item e being semantically important is defined as

where V (t) is the vocabulary at time t (maintained based on Θ(t) in constant space [Zhai and Boyd-Graber, 2013]) and n(v, e) denotes the frequency of a word v ∈ V (t) in item e.

On freshness and social context. To model that the interestingness of data degrades over time, we define a monotonic decreasing function g(t). Specifically, the decay in interestingness of past data is described by an exponential form:

where λ is the decay rate and is set to 0.5 (maximal entropy principle), t is the current time and t(e) is the time of e. Following [Mukherjee et al., 2014; Zhuang et al., 2016], we further associate each item e with a vector of social features (h1(e), . . . , hm(e)). Then, the aggregation of these features, denoted by h(e), describes the social context of a data item.

A utility measure. In social data, topics with highly frequent words may dominate other topics. To avoid such vocabulary bias, we define the utility of a set of items S as the loglikelihood over its items based on the information entropy. This measure of utility incorporates the above notions of semantic information, freshness, and social context:

Using this formulation, an algorithm to select data items will prefer sets with high entropy, i.e., sets with items that cover diverse topics and preserve the evolving topic distribution. As proven in our technical report [Nguyen et al., 2017], the above measure is monotonic (selecting more items increases utility) and submodular (marginal gains by selecting more items start to diminish due to saturation of the utility objective).

Proposition 1. f(.) is a monotonic function.

Proposition 2. f(.) is a submodular function.

3.3 A Simple Retaining Algorithm

A straight-forward approach to solve Problem 1 under the above model applies traditional data summarization [Zhuang et al., 2016] on the retained items and the content of a new window. Then, the new set of retained items is selected as:

which is equivalent to Eq. 1 since the value of f(Et+w) is constant in terms of selecting any S. However, this problem is known to be NP-complete [Hung et al., 2015]

Due to the computational complexity, greedy approximation algorithms (inspired by the knapsack problem) are commonly employed. They start with the empty set S(0) = ∅, and at each iteration i over the current data, choose an item e ∈ St ∪W maximizing the utility, i.e.,

For a monotonic and submodular function (as our utility function defined above), this greedy algorithm yields a (1 - 1/e) ≈ 0.63 approximation [Nemhauser and Wolsey, 1981]. However, this algorithm has an update time complexity of O(k(k + |W|)), which is undesirable for streaming applications. Also, the update process needs to be repeated every time new data arrives.

4 A Progressive Retaining Algorithm

Given the above results on hardness of the retaining problem and the time complexity of a simple greedy algorithm, we now present a progressive algorithm. It is tailored to the stream processing setting and shows linear time and space complexity. The algorithm comprises of (i) an incremental inference mechanism to update the sketch of historical data; and (ii) a mechanism to select a new set of retained items.

4.1 Updating the Data Sketch

To update the parameters Θ of our model, we realise an online learning mechanism. When data arrives, we compute the observed variables and propagate back the information to the model parameters. Once the parameters have been updated, the conditional and marginal probabilities for the utility function are computed following the generative process.

Many online learning techniques have been developed based on Markov chain Monte Carlo sampling (e.g., incremental Gibbs sampling [Canini et al., 2009]). However, these techniques either reduce model complexity (loosing the guarantee to converge for the complete model) or have a space complexity that is linear in the number of items to analyse [Hoffman et al., 2010]. To overcome these issues, we rely on stochastic variational inference [Hoffman et al., 2013]. Here, the idea is to minimize the evidence lower bound (ELBO) of the expected difference between the observed distribution and the latent distribution, defined as:

where Z is the set of all latent variables in the model (except model parameters and observed variables); and q(Z) is an approximate distribution of p(Z|E), which can be factorised over the distributions of model parameters in the generative process. Then, we apply stochastic optimisation to the ELBO function over a data stream, which basically updates the new parameter values from the previous ones following the direction of the ELBO gradient of new data with a fixed step size. The more data is received, the more the model parameters will converge to minimize the ELBO function.

Instead of single-item update, our approach considers multiple observations per update to reduce noise, which also aligns with window-based processing to avoid order distortion in data streaming settings. Receiving data as a series of windows Wb, b = 1, 2, . . ., of items, we proceed as follows:

1. We update the local parameters of the variational distribution of the word-topic variable z and the topic-cluster variable c. This requires us to maintain additional Mz local parameters for possible values of z, and Mc local parameters for possible values of c. Here, Mc,Mz are 'prior beliefs' on the maximum number of topics and recurring topic clusters. Yet, their effects are marginal, as the updates are dominated by the observed information, so that they can be safely set to large constant values (e.g., 1000).
2. We compute the natural gradients using previous parameter values Θ(t-1) and the above local parameters of the ELBO function decomposed over each item e ∈ Eb [Hoffman et al., 2010]. Formally, we obtain ∇Θ(t-1)Le as a vector of gradients for each parameter in Θ(t-1) .
3. The new values for model parameters are computed from their previous value:

where wb is the learning rate to control the learning quality and convergence of the inference. wb is often modelled as a power function of b with a forgetting rate r [Hoffman et al., 2013]. Setting r ∈ (0.5, 1] guarantees convergence, while larger values often lead to higher learning quality and faster convergence (but not monotonically).

Note that windows of large size reduce the number of updates, but may lead to a poor estimation of model parameters. To further improve scalability, updating of model parameters can be parallelised by exploiting the conditional independence property. When the global variables (i.e., the most outer parameters in the model) are given, the updates to local variables (i.e., inner parameters) become independent and can thus be computed concurrently. Also, the computation of semantic information, decay in interestingness, and social features per data item, see §3.2, is independent once the model parameters are updated and thus can be parallelised.

4.2 Retaining Data Items

We now turn to the selection of data items to retain. In essence, at each step, a new set of items is selected as the one with the highest utility among all candidate sets. The candidate sets are created by swapping at most one new item with a retained item, if the utility increases. However, the arrival of a new item may change the model parameters, influences the decay in interestingness of old items, and may introduce new social features. Hence, the utility of the retained set of items has to be updated, before the swapping procedure is started.

Retaining algorithm. Our progressive retaining algorithm is formalised in Alg. 1. We illustrate the algorithm with a window size of |W| = 10 (line 6). The algorithm starts with the empty set S0 = ∅. As long as no more than k elements e1, . . . , et have arrived, all of them are kept, i.e., St = St-1 ∪ {et}, for t ≤ k. For each new item et, where t > k, we update the utility value of f(St-1) and compute the semantic importance p(et), the decay in interestingness g(et) and the social features h(et). Then, we check whether swapping this item and an item in St-1 will increase the utility value. If so, the one that maximizes the utility is selected for swapping.

Theorem 1. Alg. 1 does a single pass over data stream, uses O(k) memory, and has O(k) update time per item.

The proof of Theorem 1 can be found in our technical report [Nguyen et al., 2017]. Correctness of Alg. 1 is established as follows: First, the decay in interestingness is a monotonic decreasing function. Thus, an optimal selection remains optimal after the utility has been updated. Also, even if a new item does not increase utility in terms of entropy and social features, the algorithm still swaps it with an old item to preserve the freshness of the retained set of items. Second, adding a new item increases the entropy of the topic distribution. Thus, while the algorithm favours new items, it still preserves topics by ensuring an even distribution of the selected items across all topics (old and new). Moreover, an optimal selection remains optimal as the entropy increases for all old items.

Incremental utility computation. The above complexity result assumes that the computation of utility (line 14), when swapping data items, is done in constant time. This indeed holds true, since utility can be computed incrementally, i.e., f(Si) is derived from f(Si-1) in constant time as follows:

Here, values p(., .), n(., .), g(.), h(.) have been computed already in the previous steps of the algorithm (lines 9 to 13).

5 Empirical Evaluation

Below, we first elaborate on the experimental setup, before we analyse our method's efficiency and effectiveness.

input : An infinite sequence E of data items output: A selected set St of size k of data items at any time t 1 S0 = ∅; 2 for t = 1 to k do St = St-1 ∪ {et} ; 3 W = ∅; ▷ Window 4 for t = k + 1 to |E| do 5 W =W ∪ {et}; 6 if |W| < 10 and t < n then 7 St = St-1; 8 continue; // Incremental learning of model parameters 9 Compute Θ(t) fromΘ(t-1) andW; 10 Update p(v, e) and n(v, e) by new parameter Θ(t) , ∀v ∈ V, e ∈ St-1; 11 Update g(e) ∀e ∈ St-1; 12 Update f(St-1); // Prepare computation of utility of new items 13 Compute p(v, e′ ), n(v, e′ ), g(e′ ), h(e′ ) for all e′ ∈ W and v ∈ V ; // Find swapping pair 14 e∗ , eb = arg maxe∈St-1,e′∈W f(St-1 \ {e} ∪ {e′ }); 15 if f(St-1 \ {e∗ } ∪ {eb}) ≥ f(St-1) then 16 St = St-1 \ {e∗ } ∪ {eb}; 17 else St = St-1 ; 18 W = ∅; ▷ Reset for new window

5.1 Experimental Setup

Datasets. We extracted datasets using the Twitter Streaming API. Over a year, we considered five different domains (climate change, vaccination, processed food, genetically modified organism, general public) and randomly selected 1 million English tweets per domain. Furthermore, a total of five important social features (e.g., user influence, retweet score, and affective language) had been extracted for each data item using existing frameworks [Zhuang et al., 2016].

Baselines. We compare our approach with several baselines:

• Traditional summarization: a state-of-the-art summarization technique [Zhuang et al., 2016] for social data.
• Greedy: the simple greedy algorithm (see §3.3) to select the items to retain.
• Offline learning: an iterative algorithm to compute model parameters using deterministic variational inference [Jordan et al., 1999; Blei et al., 2006], which requires a full pass of the data in each iteration.
• Static: our retaining algorithm tailored to the traditional, static setting of data summarization: offline learning to compute the sketch of historical data and the greedy algorithm to select the items to retain.

Environment. All results have been obtained on an Intel i7 3.8GHz system (4 cores, 16GB RAM). Following [Hoffman et al., 2013], we vary the forget rate in (0.5, 1], choose a stable window size = 10 and report average values.

5.2 Efficiency

We evaluate the update time of our approach, when new data arrives. To assess the average time per window needed to update the model parameters, we compare our online learning algorithm with its offline version. The latter considers the whole data received so far when computing the parameters upon the arrival of a new window. Figure 3 illustrates the results averaged over all datasets, reporting the average update time until 100K, 500K, and 1M data items are received. Here, the update time of our progressive approach remains constant and small (< 0.01s), whereas the baseline yields a high and increasing runtime (up to 103 s).

Focusing on how to select the items to retain, we compare the efficiency of our progressive algorithm (fast) with the greedy algorithm. We realise the online setting as above and vary the size of the set of retained items (k = 0.2% to 1%). Figure 4 depicts the update time of the algorithms, averaged over all datasets. Our progressive algorithm outperforms the greedy one. It also scales better to large data summaries.

Figure 4: Retaining data

5.3 Effectiveness

We compare the quality of model parameters, in terms of utility, obtained with our online learning algorithm and its offline version. To mitigate the randomness of the Twitter streaming API, we select 100K items ˜E from the original datasets and construct a set of retained items S as the k = 1% oldest items in ˜E. We stream ˜E and learn model parameters online (Θ˜E ). Offline learning considers all data received so far, the result being Θ′˜E . We then assess the relative difference in utility of S, computed with either method, i.e., |fΘ(S)-fΘ′ (S)| .

0.20

0.15

0.10

0.05

0.00

0 10 20 30 40 50 60 70 80 90 100

Data Arrival (%)

• (a) Updating model parameters

fΘ′ (S)

Figure 5: Effectiveness relative to amount of processed data

The difference in utility relative to the amount of processed data is shown in Figure 5a (averaged over 100 runs of different ˜E and the five datasets). Due to the stochastic property of online learning (data is needed to converge in the model parameters), the utility increases initially. Also, the difference between the online and offline learning results is less than 15% in general, underlining the usefulness of our approach.

We further compare the utility of retained items selected by the greedy and our progressive algorithm. Similar to the above setting, we stream all data and use online learning to update the model parameters. Both algorithms start from the set of k = 1% old items and update it upon the arrival of a new window. We then measure the relative difference of the obtained sets of retained items at each step. The results in Figure 5b (averaged over 100 runs and the five datasets) show that the utility difference increases with the arrival of

Utility Difference data. This is because the progressive algorithm accumulates some loss of information. However, the difference is small (≤ 15%) and converges with more data. As such, data quality is not compromised too much.

Finally, we compare the overall utility ratio (utility of output over utility of whole data) of our retaining algorithm (dynamic) and two baselines: the static version of our algorithm and traditional summarization (sum). The utility ratios obtained after processing all data of the five datasets are shown in Table 1, for different sizes of the set of retained items (k = 0.1% and k = 1%). While the static approach outperforms traditional summarization (sum), we need to acknowledge that both, static and sum, are inapplicable for streaming data. However, the results of the dynamic technique are relatively close to those of the static approach, highlighting its usefulness for online processing. Also, its decrease in utility for a smaller number of retained items (k) is less drastic compared to traditional summarization.

6 RelatedWork

Social data analysis is often based on topic modelling, feature extraction [Nguyen et al., 2017], and temporal-aware information processing [Chang et al., 2016]. Methods for topic modelling, e.g., Latent Dirichlet Allocation, hierarchical Dirichlet processes [Griffiths and Tenenbaum, 2004], or word modelling [Zhai and Boyd-Graber, 2013], are not applicable for a streaming setting, since they require multiple passes over the data. Streaming versions of these techniques [Canini et al., 2009], in turn, ignore the dynamics of social data. Our model follows a non-parametric approach, where the number of topics and vocabulary words is learned from the data rather than specified in advance. Moreover, our model incorporates social features [Ernst et al., 2014] when assessing data utility. Also, methods to query a streams of social data [Kedzie et al., 2016] are not applicable for data summarization, since the query is not known in advance.

Traditional data summarization works on offline data [Nguyen et al., 2015; Hung et al., 2013] and, even if temporal aspects are considered [Alsaedi et al., 2016], on the whole data. Existing streaming algorithms for data summarization [Badanidiyuru et al., 2014] also rely on access to the complete data, as they sample the data for an estimation of the utility. A relaxed version of the retaining problem has been addressed in [Epasto et al., 2016], which finds subsets of items with maximal utility using a sliding window. Yet, different from our problem formulation, this method targets solely the recent data bounded by a fixed window size, discarding all old items. Whereas, our approach retains old items as long as they are valuable. Also, unlike [Epasto et al., 2016], our approach summarizes the entire history of a data stream. Finally, their algorithm assumes apriori knowledge of an upper bound of utility. While this assumption may be reasonable for some types of data streams, it it unrealistic for dynamic data produced by social platforms.

7 Conclusions

This paper proposed a technique to retain a representative set of items from a stream of social data. That is, we acknowledge the online nature of data produced by social platforms, which prevents us from storing the complete data stream. This led the retaining problem with minimal regret, where a protocol decides which data to retain, such that the loss of utility is minimized. To address this problem, we proposed a light-weight, adaptive sketch of historical data and a progressive algorithms for the selection of data items. Experiments on large-scale real-world data showed that our approach is efficient (five orders of magnitude faster than the baseline) and effective (less than 15% reduction in the utility ratio).