Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.336
URN: urn:nbn:de:0030-drops-56488
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5648/
Bishnu, Arijit ; Chakrabarti, Amit ; Nandy, Subhas C. ; Sen, Sandeep
On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model
| pdf-format: |
|
Abstract
In this paper, we study the maximum density, threshold and emptinessqueries 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.
BibTeX - Entry
@InProceedings{bishnu_et_al:LIPIcs:2015:5648,
author = {Arijit Bishnu and Amit Chakrabarti and Subhas C. Nandy and Sandeep Sen},
title = {{On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {336--349},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-97-2},
ISSN = {1868-8969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5648},
URN = {urn:nbn:de:0030-drops-56488},
doi = {10.4230/LIPIcs.FSTTCS.2015.336},
annote = {Keywords: Density, threshold, emptiness queries, interval queries, streaming model, heavy hitter, frequency estimation}
}
| Keywords: | Density, threshold, emptiness queries, interval queries, streaming model, heavy hitter, frequency estimation | |
| Seminar: | 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 14.12.2015 |
