首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Approximate Query Processing over Static Sets and Sliding Windows
  • 本地全文:下载
  • 作者:Ran Ben Basat ; Seungbum Jo ; Srinivasa Rao Satti
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:123
  • 页码:1-12
  • DOI:10.4230/LIPIcs.ISAAC.2018.54
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and multisets to support approximate versions of the operations rank(i) (i.e., computing sum_{j <= i} B[j]) and select(i) (i.e., finding min{p|rank(p) >= i}) queries. We study multiple types of approximations (allowing an error in the query or the result) and present lower bounds and succinct data structures for several variants of the problem. We also extend our model to sliding windows, in which we process a stream of elements and compute suffix sums. This is a generalization of the window summation problem that allows the user to specify the window size at query time. Here, we provide an algorithm that supports updates and queries in constant time while requiring just (1+o(1)) factor more space than the fixed-window summation algorithms.
  • 关键词:Streaming; Algorithms; Sliding window; Lower bounds
国家哲学社会科学文献中心版权所有