Math @ Duke

Publications [#235474] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Xie, J; Yang, J; Yu, H, Monitoring continuous bandjoin queries over dynamic data,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS
(2005),
pp. 349359, ISSN 03029743 [doi]
(last updated on 2018/12/16)
Abstract: A continuous query is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure on a set of continuous bandjoin queries over two data sets R and S, where each bandjoin query asks for reporting the set {(r, s) ∈R × S  a ≤r  s ≤ b} for some parameters a and b, so that given a data update in R or S, one can quickly identify the subset of continuous queries whose results are affected by the update, and compute changes to these results. We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem into two independent subproblems, and then carefully designing data structures suitable for each case, by exploiting the particular structure in each subproblem. A key step in the above construction is a data structure whose performance increases with the degree of clusteredness of the bandjoins being indexed. We believe that this structure is of independent interest and should have broad impact in practice. We present the details in [1]. © SpringerVerlag Berlin Heidelberg 2005.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

