Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235474] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Xie, J; Yang, J; Yu, H, Monitoring continuous band-join 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. 349-359, ISSN 0302-9743 [doi]
    (last updated on 2018/12/16)

    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 band-join queries over two data sets R and S, where each band-join 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 band-joins being indexed. We believe that this structure is of independent interest and should have broad impact in practice. We present the details in [1]. © Springer-Verlag Berlin Heidelberg 2005.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320