File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Voronoi-based nearest neighbor search for multi-dimensional uncertain databases

TitleVoronoi-based nearest neighbor search for multi-dimensional uncertain databases
Authors
Advisors
Issue Date2012
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Zhang, P. [张培武]. (2012). Voronoi-based nearest neighbor search for multi-dimensional uncertain databases. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961817
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.
DegreeMaster of Philosophy
SubjectVoronoi polygons.
Nearest neighbor analysis (Statistics)
Uncertainty (Information theory)
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/181489

 

DC FieldValueLanguage
dc.contributor.advisorMamoulis, N-
dc.contributor.advisorCheng, CK-
dc.contributor.authorZhang, Peiwu.-
dc.contributor.author张培武.-
dc.date.accessioned2013-03-03T03:20:05Z-
dc.date.available2013-03-03T03:20:05Z-
dc.date.issued2012-
dc.identifier.citationZhang, P. [张培武]. (2012). Voronoi-based nearest neighbor search for multi-dimensional uncertain databases. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961817-
dc.identifier.urihttp://hdl.handle.net/10722/181489-
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.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.source.urihttp://hub.hku.hk/bib/B49618179-
dc.subject.lcshVoronoi polygons.-
dc.subject.lcshNearest neighbor analysis (Statistics)-
dc.subject.lcshUncertainty (Information theory)-
dc.titleVoronoi-based nearest neighbor search for multi-dimensional uncertain databases-
dc.typePG_Thesis-
dc.identifier.hkulb4961817-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b4961817-
dc.date.hkucongregation2013-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats