.png){kind=icon}
返回
Efficient Representative Subset Selection over Sliding Windows
.png){kind=icon}
OA
AI
DOI：10.1109/TKDE.2018.2854182.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 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 1-epsilon/1+dapproximate for SMDK. Furthermore, we propose a KNAPWINDOWPLUS framework (KW+) to improve upon KW. KW+ 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+ achieves higher efficiency than KW while still guaranteeing a 1-epsilon'/2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW+ 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+ further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities.
Keyword:
Data summarization
sliding window
data stream
submodular maximization
approximation algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏
Processing Long Queries Against Short Text: Top-k Advertisement Matching in News Stream Applications针对短文本处理长查询: 新闻流应用程序中的top-k广告匹配OAAI
OAAI分享收藏
查看更多内容