Characterizing memory requirements for queries over continuous data streams

被引：32

作者：

Arasu, A ^{[1
]}

Babcock, B ^{[1
]}

Babu, S ^{[1
]}

McAlister, J ^{[1
]}

Widom, J ^{[1
]}

机构：

[1] Stanford Univ, Stanford, CA 94305 USA

来源：

ACM TRANSACTIONS ON DATABASE SYSTEMS | 2004年 / 29卷 / 01期

关键词：

algorithms; performance; theory; continuous queries; memory requirement; streams;

D O I：

10.1145/974750.974756

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 memory for all possible instances of the data streams. For queries that can be evaluated using bounded memory, an execution strategy based on constant-sized synopses of the data streams is proposed. For queries that cannot be evaluated using bounded memory, data stream scenarios are identified in which evaluating the queries requires memory linear in the size of the unbounded streams.

引用

页码：162 / 194

页数：33

共 31 条

[1] The space complexity of approximating the frequency moments [J].

Alon, N ;

Matias, Y ;

Szegedy, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (01) :137-147

[2]

[Anonymous], P 21 ACM SIGMOD SIGA

[3]

Arasu A., 2002, ABSTRACT SEMANTICS C

[4]

Babcock B, 2002, SIAM PROC S, P633

[5]

Babcock B., 2002, Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), P1, DOI DOI 10.1145/543613.543615

[6]

BABU S, 2002, EXPLOITING K KONSTRA

[7]

Carney D., 2002, Proceedings of the Twenty-eighth International Conference on Very Large Data Bases, P215

[8]

Chandrasekaran S., 2002, Proceedings of the Twenty-eighth International Conference on Very Large Data Bases, P203

[9]

CHANDRASEKARAN S, 2003, P 1 BIENN C INN DAT, P269

[10]

Chen J., 2000, SIGMOD 00, P379, DOI DOI 10.1145/342009.335432

← 1 2 3 4 →