eprintid: 10152071
rev_number: 6
eprint_status: archive
userid: 699
dir: disk0/10/15/20/71
datestamp: 2022-07-15 07:53:55
lastmod: 2022-07-15 07:53:55
status_changed: 2022-07-15 07:53:55
type: article
metadata_visibility: show
sword_depositor: 699
creators_name: Basat, Ran Ben
creators_name: Jo, Seungbum
creators_name: Satti, Srinivasa Rao
creators_name: Ugare, Shubham
title: Approximate query processing over static sets and sliding windows☆
ispublished: pub
divisions: C05
divisions: F48
divisions: B04
divisions: UCL
keywords: Streaming, Algorithms, Sliding window, Lower bounds
note: © 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the
CC BY license (http://creativecommons.org/licenses/by/4.0/).
abstract: 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  (i.e., computing ) and  (i.e., finding ) 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  factor more space than the fixed-window summation algorithms.
date: 2021-09-11
date_type: published
publisher: Elsevier
official_url: https://doi.org/10.1016/j.tcs.2021.06.015
oa_status: green
full_text_type: pub
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1965494
doi: 10.1016/j.tcs.2021.06.015
lyricists_name: Ben Basat, Shlomi Ran
lyricists_id: SRBEN76
actors_name: Flynn, Bernadette
actors_id: BFFLY94
actors_role: owner
full_text_status: public
publication: Theoretical Computer Science
volume: 885
pagerange: 1-14
citation:        Basat, Ran Ben;    Jo, Seungbum;    Satti, Srinivasa Rao;    Ugare, Shubham;      (2021)    Approximate query processing over static sets and sliding windows☆.                   Theoretical Computer Science , 885    pp. 1-14.    10.1016/j.tcs.2021.06.015 <https://doi.org/10.1016/j.tcs.2021.06.015>.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10152071/1/1-s2.0-S0304397521003571-main.pdf