1 Search Results for "Ugare, Shubham"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.54
Approximate Query Processing over Static Sets and Sliding Windows

Authors: Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

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 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.
Cite as

Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare. Approximate Query Processing over Static Sets and Sliding Windows. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ISAAC.2018.54,
  author =	{Ben Basat, Ran and Jo, Seungbum and Satti, Srinivasa Rao and Ugare, Shubham},
  title =	{{Approximate Query Processing over Static Sets and Sliding Windows}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{54:1--54:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.54},
  URN =		{urn:nbn:de:0030-drops-100027},
  doi =		{10.4230/LIPIcs.ISAAC.2018.54},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
  • Refine by Author
  • 1 Ben Basat, Ran
  • 1 Jo, Seungbum
  • 1 Satti, Srinivasa Rao
  • 1 Ugare, Shubham

  • Refine by Classification
  • 1 Theory of computation → Data compression

  • Refine by Keyword
  • 1 Algorithms
  • 1 Lower bounds
  • 1 Sliding window
  • 1 Streaming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact