Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the “diminishing returns” property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general @math d-knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes the KnapStream algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is @math 1-ɛ1+d-approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework (KW @math +) to improve upon KW. KW @math + builds an index SubKnapChk to manage the checkpoints and KS instances. SubKnapChk deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW @math + achieves higher efficiency than KW while still guaranteeing a @math 1-ɛ'2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW @math + in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW @math + further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities.
Recently, we have witnessed the growth of studies in the data stream model. in append-only streams where new elements arrive continuously but old ones never expire is studied in @cite_38 @cite_24 @cite_3 @cite_16 . @cite_13 further propose a method for deletion-robust where a limited number of old elements can be deleted from the stream. However, these techniques neither support general constraints beyond cardinality nor consider the recency of selected subsets. In many scenarios, data streams are highly dynamic and evolve over time. Therefore, recent elements are more important and interesting than earlier ones. The @cite_8 model is widely adopted in many data-driven applications @cite_18 @cite_10 to capture the recency constraint. over sliding windows is still largely unexplored yet and, to the best of our knowledge, there is only one existing method @cite_40 for dynamic over sliding windows. But it is specific for the cardinality constraint. In this paper, we propose more general frameworks for than any existing ones, which work with various submodular utility functions, support @math -knapsack constraints, and maintain the representatives over sliding windows.
@cite_38 @cite_18 @cite_8 @cite_10 @cite_3 @cite_24 @cite_40 @cite_16 @cite_13
2842078607 2547615739 2128846062 2119163494
Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the “diminishing returns” property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general @math d-knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes the KnapStream algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is @math 1-ɛ1+d-approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework (KW @math +) to improve upon KW. KW @math + builds an index SubKnapChk to manage the checkpoints and KS instances. SubKnapChk deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW @math + achieves higher efficiency than KW while still guaranteeing a @math 1-ɛ'2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW @math + in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW @math + further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities. In this paper we study the extraction of representative elements in the data stream model in the form of submodular maximization. Different from the previous work on streaming submodular maximization, we are interested only in the recent data, and study the maximization problem over sliding windows. We provide a general reduction from the sliding window model to the standard streaming model, and thus our approach works for general constraints as long as there is a corresponding streaming algorithm in the standard streaming model. As a consequence, we obtain the first algorithms in the sliding window model for maximizing a monotone non-monotone submodular function under cardinality and matroid constraints. We also propose several heuristics and show their efficiency in real-world datasets. In the streaming model elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and non-trivial task in the model. This becomes even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar, Gionis, Indyk and Motwani [15] presented exponential histograms, an effective method for estimating statistics on sliding windows. In this paper we present a new smooth histograms method that improves the approximation error rate obtained via exponential histograms. Furthermore, our smooth histograms method not only captures and improves multiple previous results on sliding windows bur also extends the class functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: Lp norms for p notin [1,2], frequency moments, length of increasing subsequence and geometric mean. We study the problem of maintaining a sketch of recent elements of a data stream. Motivated by applications involving network data, we consider streams that are asynchronous, in which the observed order of data is not the same as the time order in which the data was generated. The notion of recent elements of a stream is modeled by the sliding timestamp window, which is the set of elements with timestamps that are close to the current time. We design algorithms for maintaining sketches of all elements within the sliding timestamp window that can give provably accurate estimates of two basic aggregates, the sum and the median, of a stream of numbers. The space taken by the sketches, the time needed for querying the sketch, and the time for inserting new elements into the sketch are all polylogarithmic with respect to the maximum window size. Our sketches can be easily combined in a lossless and compact way, making them useful for distributed computations over data streams. Previous works on sketching recent elements of a data stream have all considered the more restrictive scenario of synchronous streams, where the observed order of data is the same as the time order in which the data was generated. Our notion of recency of elements is more general than that studied in previous work, and thus our sketches are more robust to network delays and asynchrony.