research-article

Range Thresholding on Streams

Authors:

Yufei TaoAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Pages 571 - 582

https://doi.org/10.1145/2882903.2915965

Published: 14 June 2016 Publication History

Abstract

This paper studies a type of continuous queries called range thresholding on streams (RTS). Imagine the stream as an unbounded sequence of elements each of which is a real value. A query registers an interval, and must be notified as soon as a certain number of incoming elements fall into the interval. The system needs to support multiple queries simultaneously, and aims to minimize the space consumption and computation time. Currently, all the solutions to this problem entail quadratic time O(nm) to process n stream elements and m queries, which severely limits their applicability to only a small number of queries. We propose the first algorithm that breaks the quadratic barrier, by reducing the computation cost dramatically to O(n + m), subject only to a polylogarithmic factor. The algorithm is general enough to guarantee the same on weighted versions of the queries even in d-dimensional space of any constant d. Its vast advantage over the previous methods in practical environments has been confirmed through extensive experimentation.

References

[1]

D. J. Abadi, D. Carney, U. Çetintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Aurora: a new model and architecture for data stream management. VLDB J., 12(2):120--139, 2003.

Digital Library

[2]

A. Arasu and J. Widom. A denotational semantics for continuous queries over streams and relations. SIGMOD Record, 33(3):6--12, 2004.

Digital Library

[3]

L. Arge and J. Vahrenhold. I/O-efficient dynamic planar point location. Computational Geometry, 29(2):147--162, 2004.

Digital Library

[4]

L. Arge and J. S. Vitter. Optimal external memory interval management. SIAM J. of Comp., 32(6):1488--1508, 2003.

Digital Library

[5]

N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In SIGMOD, pages 322--331, 1990.

Digital Library

[6]

J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. Journal of Algorithms, 1(4):301--358, 1980.

[7]

D. Carney, U. Çetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Monitoring streams - A new class of data management applications. In VLDB, pages 215--226, 2002.

Digital Library

[8]

J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. Niagaracq: A scalable continuous query system for internet databases. In SIGMOD, pages 379--390, 2000.

Digital Library

[9]

G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms, 7(2):21, 2011.

Digital Library

[10]

G. Cugola and A. Margara. Processing flows of information: From data stream to complex event processing. ACM Comp. Surv., 44(3):15, 2012.

Digital Library

[11]

U. Dayal, E. N. Hanson, and J. Widom. Active database systems. In Modern Database Systems, pages 434--456. 1995.

Digital Library

[12]

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008.

Digital Library

[13]

A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White. Cayuga: A general purpose event monitoring system. In CIDR, pages 412--422, 2007.

[14]

Y. Diao, S. Rizvi, and M. J. Franklin. Towards an internet-scale XML dissemination service. In VLDB, pages 612--623, 2004.

Digital Library

[15]

F. Fabret, H. Jacobsen, F. Llirbat, J. L. M. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe. In SIGMOD, pages 115--126, 2001.

Digital Library

[16]

A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984.

Digital Library

[17]

S. Madden, M. A. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In SIGMOD, pages 49--60, 2002.

Digital Library

[18]

B. Nguyen, S. Abiteboul, G. Cobena, and M. Preda. Monitoring XML data on the web. In SIGMOD, pages 437--448, 2001.

Digital Library

[19]

N. W. Paton and O. Dıaz. Active database systems. ACM Comp. Surv., 31(1):63--103, 1999.

Digital Library

[20]

S. Rahul. Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in R3. In SODA, pages 200--211, 2015.

Digital Library

[21]

D. B. Terry, D. Goldberg, D. A. Nichols, and B. M. Oki. Continuous queries over append-only databases. In SIGMOD, pages 321--330, 1992.

Digital Library

[22]

E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD, pages 407--418, 2006.

Digital Library

[23]

A. Yu, P. K. Agarwal, and J. Yang. Processing a large number of continuous preference top-phk queries. In SIGMOD, pages 397--408, 2012.

Digital Library

Cited By

Amagata DHara T(2023)Efficient Density-peaks Clustering Algorithms on Static and Dynamic Data in Euclidean SpaceACM Transactions on Knowledge Discovery from Data10.1145/360787318:1(1-27)Online publication date: 10-Aug-2023
https://dl.acm.org/doi/10.1145/3607873
Zhang ZGan JBao ZKazemi SChen GZhu FIves ZBonifati AEl Abbadi A(2022)Approximate Range ThresholdingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526123(1108-1121)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526123
Tsuruoka SAmagata DNishio SHara T(2020)Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/SubProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422199(111-114)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422199
Show More Cited By

Index Terms

Range Thresholding on Streams
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Stream management

Recommendations

Approximate Range Thresholding
SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data

In this paper, we study the (approximate) Range Thresholding (RT) problem over streams. Each stream element is a d-dimensional point and with a positive integer weight. An RT query q specifies a d-dimensional axis-parallel rectangular range R(q) and a ...
Characterizing memory requirements for queries over continuous data streams

This article deals with continuous conjunctive queries with arithmetic comparisons and optional aggregation over multiple data streams. An algorithm is presented for determining whether or not any given query can be evaluated using a bounded amount of ...
Data Streams with Bounded Deletions
PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Two prevalent models in the data stream literature are the insertion-only and turnstile models. Unfortunately, many important streaming problems require a Θ(log(n)) multiplicative factor more space for turnstile streams than for insertion-only streams. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
449
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amagata DHara T(2023)Efficient Density-peaks Clustering Algorithms on Static and Dynamic Data in Euclidean SpaceACM Transactions on Knowledge Discovery from Data10.1145/360787318:1(1-27)Online publication date: 10-Aug-2023
https://dl.acm.org/doi/10.1145/3607873
Zhang ZGan JBao ZKazemi SChen GZhu FIves ZBonifati AEl Abbadi A(2022)Approximate Range ThresholdingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526123(1108-1121)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526123
Tsuruoka SAmagata DNishio SHara T(2020)Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/SubProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422199(111-114)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422199
WU HGan JZhang RGupta RLiu YShah MRajan STang JPrakash B(2020)Learning Based Distributed TrackingProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403255(2040-2050)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403255

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents