Document Open Access Logo

On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model

Authors Arijit Bishnu, Amit Chakrabarti, Subhas C. Nandy, Sandeep Sen

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.336.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Arijit Bishnu
Amit Chakrabarti
Subhas C. Nandy
Sandeep Sen

Cite As Get BibTex

Arijit Bishnu, Amit Chakrabarti, Subhas C. Nandy, and Sandeep Sen. On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 336-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.336

Abstract

In this paper, we study the maximum density, threshold and emptiness 
queries for intervals in the streaming model. The input is a stream S 
of n points in the real line R and a floating closed interval W of width alpha. The specific problems we consider in this paper are as follows.
- Maximum density: find a placement of W in R containing the
maximum number of points of S.
- Threshold query: find a placement of W in R, if it exists,
that contains at least Delta elements of S. 
- Emptiness query: find, if possible, a placement of W within the extent of S so that the interior of W does not contain any element of S.

The stream S, being huge, does not fit into main memory and can be read sequentially at most a constant number of times, usually once. 
The problems studied here in the geometric setting have relations to frequency estimation and heavy hitter identification in a stream of data. We provide lower bounds and results on trade-off between extra space and quality of solution. We also discuss generalizations for the higher dimensional variants for a few cases.

Subject Classification

Keywords
  • Density
  • threshold
  • emptiness queries
  • interval queries
  • streaming model
  • heavy hitter
  • frequency estimation

Metrics

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

References

  1. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606-635, July 2004. Google Scholar
  2. A. Aggarwal and S. Suri. Fast algorithms for computing the largest empty rectangle. In Proceedings of the Third Annual Symposium on Computational Geometry, SCG'87, pages 278-290, 1987. Google Scholar
  3. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. Google Scholar
  4. T. Asano, M. Sato, and T. Ohtsuki. Computational geometric algorithms. In Layout Design and Verification, Advances in CAD for VLSL (Edited by T. Ohtsuki), pages 295-347. North Holland, 1986. Google Scholar
  5. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 3rd ed. edition, 2008. Google Scholar
  6. Sergio Cabello and Pablo Pérez-Lantero. Interval selection in the streaming model. In WADS'15, pages 127-139, 2015. Google Scholar
  7. Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In PROC18 #CCC, pages 107-117, 2003. Google Scholar
  8. Timothy M. Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom., 35(1-2):20-35, 2006. Google Scholar
  9. Timothy M. Chan and Vinayak Pathak. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. In Proceedings of the 12th International Conference on Algorithms and Data Structures, WADS'11, pages 195-206, 2011. Google Scholar
  10. Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theor. Comput. Sci., 312(1):3-15, 2004. Google Scholar
  11. Graham Cormode and Marios Hadjieleftheriou. Methods for finding frequent items in data streams. VLDB J., 19(1):3-20, 2010. Google Scholar
  12. Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Frequency estimation of internet packet streams with limited space. In Algorithms - ESA 2002, 10th Annual European Symposium, pages 348-360, 2002. Google Scholar
  13. Yuval Emek, Magnús M. Halldórsson, and Adi Rosén. Space-constrained interval selection. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 302-313, 2012. Google Scholar
  14. Sariel Har-Peled and Soham Mazumdar. Fast algorithms for computing the smallest k-enclosing circle. Algorithmica, 41(3):147-157, 2005. Google Scholar
  15. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar Rajagopalan. Computing on data streams, 1998. Google Scholar
  16. John Hershberger and Subhash Suri. Adaptive sampling for geometric problems over data streams. Comput. Geom. Theory Appl., 39(3):191-208, April 2008. Google Scholar
  17. Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In STOC, pages 202-208, 2005. Google Scholar
  18. Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou. A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst., 28:51-55, 2003. Google Scholar
  19. Subhashis Majumder and Bhargab B. Bhattacharya. On the density and discrepancy of a 2d point set with applications to thermal analysis of vlsi chips. Inf. Process. Lett., 107(5):177-182, 2008. Google Scholar
  20. Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In VLDB, pages 346-357, 2002. Google Scholar
  21. Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program., 2(2):143-152, 1982. Google Scholar
  22. S. Muthukrishnan. Data streams: Algorithms and applications. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'03, pages 413-413, 2003. Google Scholar
  23. Subhas C. Nandy and Bhargab B. Bhattacharya. A unified algorithm for finding maximum and minimum point enclosing rectangles and cuboids. Int. J. on Computers and Mathematics with applications, 29(8):45-61, 1995. Google Scholar
  24. Alexander Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. Google Scholar
  25. Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Parallel streaming frequency-based aggregates. In 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'14, pages 236-245, 2014. Google Scholar
  26. David P. Woodruff. Frequency moments. In Encyclopedia of Database Systems, pages 1169-1170. Springer, US, 2009. Google Scholar
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