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.
Preview |
PDF
1-s2.0-S0304397521003571-main.pdf - Published Version Download (725kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Approximate query processing over static sets and sliding windows☆ |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.tcs.2021.06.015 |
| Publisher version: | https://doi.org/10.1016/j.tcs.2021.06.015 |
| Language: | English |
| Additional information: | © 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/). |
| Keywords: | Streaming, Algorithms, Sliding window, Lower bounds |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152071 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
