Math @ Duke

Publications [#235549] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Efrat, A; Sankararaman, S; Zhang, W, Nearestneighbor searching under uncertainty,
Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems
(2012),
pp. 225236 [doi]
(last updated on 2018/10/14)
Abstract: Nearestneighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an εapproximate ENN, for a given error parameter 0 < ε < 1, under dierent distance functions. These methods build an index of nearlinear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or εapproximate ENN queries with provable performance guarantees. © 2012 ACM.


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

