File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Voronoi-based nearest neighbor search for multi-dimensional uncertain databases

TitleVoronoi-based nearest neighbor search for multi-dimensional uncertain databases
Authors
KeywordsAttribute values
Nearest neighbor queries
Nearest Neighbor search
Nearest neighbors
Query points
Real data sets
Uncertain database
Uncertain datas
Issue Date2013
PublisherIEEE, Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178
Citation
The 29th International Conference on Data Engineering (ICDE 2013), Brisbane, Australia, 8-11 April 2013. In International Conference on Data Engineering Proceedings, 2013, p. 158-169 How to Cite?
AbstractIn Voronoi-based nearest neighbor search, the Voronoi cell of every point p in a database can be used to check whether p is the closest to some query point q. We extend the notion of Voronoi cells to support uncertain objects, whose attribute values are inexact. Particularly, we propose the Possible Voronoi cell (or PV-cell). A PV-cell of a multi-dimensional uncertain object o is a region R, such that for any point p ∈ R, o may be the nearest neighbor of p. If the PV-cells of all objects in a database S are known, they can be used to identify objects that have a chance to be the nearest neighbor of q. However, there is no efficient algorithm for computing an exact PV-cell. We hence study how to derive an axis-parallel hyper-rectangle (called the Uncertain Bounding Rectangle, or UBR) that tightly contains a PV-cell. We further develop the PV-index, a structure that stores UBRs, to evaluate probabilistic nearest neighbor queries over uncertain data. An advantage of the PV-index is that upon updates on S, it can be incrementally updated. Extensive experiments on both synthetic and real datasets are carried out to validate the performance of the PV-index. © 2013 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/189614
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorZhang, Pen_US
dc.contributor.authorCheng, Ren_US
dc.contributor.authorMamoulis, Nen_US
dc.contributor.authorRenz, Men_US
dc.contributor.authorZüfle, Aen_US
dc.contributor.authorTang, Yen_US
dc.contributor.authorEmrich, Ten_US
dc.date.accessioned2013-09-17T14:50:20Z-
dc.date.available2013-09-17T14:50:20Z-
dc.date.issued2013en_US
dc.identifier.citationThe 29th International Conference on Data Engineering (ICDE 2013), Brisbane, Australia, 8-11 April 2013. In International Conference on Data Engineering Proceedings, 2013, p. 158-169en_US
dc.identifier.isbn978-1-4673-4910-9-
dc.identifier.issn1084-4627-
dc.identifier.urihttp://hdl.handle.net/10722/189614-
dc.description.abstractIn Voronoi-based nearest neighbor search, the Voronoi cell of every point p in a database can be used to check whether p is the closest to some query point q. We extend the notion of Voronoi cells to support uncertain objects, whose attribute values are inexact. Particularly, we propose the Possible Voronoi cell (or PV-cell). A PV-cell of a multi-dimensional uncertain object o is a region R, such that for any point p ∈ R, o may be the nearest neighbor of p. If the PV-cells of all objects in a database S are known, they can be used to identify objects that have a chance to be the nearest neighbor of q. However, there is no efficient algorithm for computing an exact PV-cell. We hence study how to derive an axis-parallel hyper-rectangle (called the Uncertain Bounding Rectangle, or UBR) that tightly contains a PV-cell. We further develop the PV-index, a structure that stores UBRs, to evaluate probabilistic nearest neighbor queries over uncertain data. An advantage of the PV-index is that upon updates on S, it can be incrementally updated. Extensive experiments on both synthetic and real datasets are carried out to validate the performance of the PV-index. © 2013 IEEE.-
dc.languageengen_US
dc.publisherIEEE, Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178-
dc.relation.ispartofInternational Conference on Data Engineering Proceedingsen_US
dc.rightsInternational Conference on Data Engineering. Proceedings. Copyright © IEEE, Computer Society.-
dc.rights©2013 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectAttribute values-
dc.subjectNearest neighbor queries-
dc.subjectNearest Neighbor search-
dc.subjectNearest neighbors-
dc.subjectQuery points-
dc.subjectReal data sets-
dc.subjectUncertain database-
dc.subjectUncertain datas-
dc.titleVoronoi-based nearest neighbor search for multi-dimensional uncertain databasesen_US
dc.typeConference_Paperen_US
dc.identifier.emailZhang, P: pwzhang@cs.hku.hken_US
dc.identifier.emailCheng, R: ckcheng@cs.hku.hken_US
dc.identifier.emailMamoulis, N: nikos@cs.hku.hk-
dc.identifier.emailRenz, M: renz@dbs.ifi.lmu.de-
dc.identifier.emailZ¨ufle, A: zuefle@dbs.ifi.lmu.de-
dc.identifier.emailTang, Y: ytang@cs.hku.hk-
dc.identifier.emailEmrich, T: emrich@dbs.ifi.lmu.de-
dc.identifier.authorityCheng, R=rp00074en_US
dc.identifier.authorityMamoulis, N=rp00155en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/ICDE.2013.6544822-
dc.identifier.scopuseid_2-s2.0-84881360282-
dc.identifier.hkuros220971en_US
dc.identifier.spage158en_US
dc.identifier.epage169en_US
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 131016-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats