Document Open Access Logo

Approximate Query Processing over Static Sets and Sliding Windows

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.54.pdf
  • Filesize: 0.57 MB
  • 12 pages

Document Identifiers

Author Details

Ran Ben Basat
  • Harvard University, Cambridge, USA
Seungbum Jo
  • University of Siegen, Germany
Srinivasa Rao Satti
  • Seoul National University, South Korea
Shubham Ugare
  • IIT Guwahati, Guwahati, India

Funding

  • Ben Basat, Ran: Supported by the Zuckerman Foundation, the Technion Hiroshi Fujiwara cyber security research center, and the Israel Cyber Directorate.
  • Jo, Seungbum: The author of this paper is supported by the DFG research project LO748/11-1.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2018.54

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data compression
Keywords
  • Streaming
  • Algorithms
  • Sliding window
  • Lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. R. Ben Basat, S. Jo, S. Rao Satti, and S. Ugare. Approximate Query Processing over Static Sets and Sliding Windows. ArXiv e-prints, September 2018. URL: http://arxiv.org/abs/1809.05419.
  2. Ran Ben-Basat, Gil Einziger, and Roy Friedman. Give Me Some Slack: Efficient Network Measurements. In MFCS, pages 34:1-34:16, 2018. Google Scholar
  3. Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient Summing over Sliding Windows. In SWAT, pages 11:1-11:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.11.
  4. Ran Ben-Basat, Roy Friedman, and Rana Shahout. Heavy Hitters over Interval Queries. CoRR, abs/1804.10740, 2018. URL: http://arxiv.org/abs/1804.10740.
  5. David R. Clark and J. Ian Munro. Efficient Suffix Trees on Secondary Storage. In SODA, pages 383-391, 1996. Google Scholar
  6. Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining Stream Statistics over Sliding Windows. SIAM J. Comput., 31(6):1794-1813, 2002. URL: http://dx.doi.org/10.1137/S0097539701398363.
  7. Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct Color Searching in One Dimension. In ISAAC, pages 30:1-30:11, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.30.
  8. Phillip B. Gibbons and Srikanta Tirthapura. Distributed streams algorithms for sliding windows. In SPAA, pages 63-72, 2002. URL: http://dx.doi.org/10.1145/564870.564880.
  9. Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. Rank/Select Operations on Large Alphabets: A Tool for Text Indexing. In SODA, pages 368-373, 2006. Google Scholar
  10. Alexander Golynski, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. Optimal Indexes for Sparse Bit Vectors. Algorithmica, 69(4):906-924, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9767-2.
  11. Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung. Succinct data structures for Searchable Partial Sums with optimal worst-case performance. Theor. Comput. Sci., 412(39):5176-5186, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.05.023.
  12. Guy Joseph Jacobson. Succinct Static Data Structures. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 1988. AAI8918056. Google Scholar
  13. Seungbum Jo, Stelios Joannou, Daisuke Okanohara, Rajeev Raman, and Srinivasa Rao Satti. Compressed Bit vectors Based on Variable-to-Fixed Encodings. Comput. J., 60(5):761-775, 2017. Google Scholar
  14. P. B. Miltersen. Cell probe complexity - a survey. FSTTCS, 1999. Google Scholar
  15. J.Ian Munro, Venkatesh Raman, and S.Srinivasa Rao. Space Efficient Suffix Trees. J. Algorithms, 39(2):205-222, 2001. Google Scholar
  16. Gonzalo Navarro and Eliana Providel. Fast, Small, Simple Rank/Select on Bitmaps. In SEA, pages 295-306, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30850-5_26.
  17. Daisuke Okanohara and Kunihiko Sadakane. Practical Entropy-Compressed Rank/Select Dictionary. In ALENEX, pages 60-70, 2007. URL: http://dx.doi.org/10.1137/1.9781611972870.6.
  18. Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct Dynamic Data Structures. In WADS, pages 426-437, 2001. URL: http://dx.doi.org/10.1007/3-540-44634-6_39.
  19. Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3(4):43, 2007. URL: http://dx.doi.org/10.1145/1290672.1290680.
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 About DROPS Imprint Privacy Contact