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

Math @ Duke



Publications [#235552] of Pankaj K. Agarwal

Papers Published

  1. Yu, A; Agarwal, PK; Yang, J, Processing and notifying range top-k subscriptions, Proceedings International Conference on Data Engineering (2012), pp. 810-821, ISSN 1084-4627 [doi]
    (last updated on 2018/08/20)

    We consider how to support a large number of users over a wide-area network whose interests are characterised by range top-k continuous queries. Given an object update, we need to notify users whose top-k results are affected. Simple solutions include using a content-driven network to notify all users whose interest ranges contain the update (ignoring top-k), or using a server to compute only the affected queries and notifying them individually. The former solution generates too much network traffic, while the latter overwhelms the server. We present a geometric framework for the problem that allows us to describe the set of affected queries succinctly with messages that can be efficiently disseminated using content-driven networks. We give fast algorithms to reformulate each update into a set of messages whose number is provably optimal, with or without knowing all user interests. We also present extensions to our solution, including an approximate algorithm that trades off between the cost of server-side reformulation and that of user-side post-processing, as well as efficient techniques for batch updates. © 2012 IEEE.
ph: 919.660.2800
fax: 919.660.2821

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