File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: UV-diagram: A Voronoi diagram for uncertain data

TitleUV-diagram: A Voronoi diagram for uncertain data
Authors
KeywordsBusiness applications
Data space
Nearest neighbors
Nearest-neighbor query
Non-zero probability
Issue Date2010
PublisherIEEE, Computer Society.
Citation
The 26th IEEE International Conference on Data Engineering (ICDE 2010), Long Beach, CA., 1-6 March 2010. In Proceedings of the 26th ICDE, 2010, p. 796-807 How to Cite?
AbstractThe Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. In this paper, we study how the Voronoi diagram can be used on uncertain data, which are inherent in scientific and business applications. In particular, we propose the Uncertain-Voronoi Diagram (or UV-diagram in short). Conceptually, the data space is divided into distinct "UV-partitions", where each UV-partition P is associated with a set S of objects; any point q located in P has the set S as its nearest neighbor with non-zero probabilities. The UV-diagram facilitates queries that inquire objects for having non-zero chances of being the nearest neighbor of a given query point. It also allows analysis of nearest neighbor information, e.g., finding out how many objects are the nearest neighbors in a given area. However, a UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation for UV-partitions, and develop an adaptive index for the UV-diagram. This index can be constructed in polynomial time. We examine how it can be extended to support other related queries. We also perform extensive experiments to validate the effectiveness of our approach. © 2010 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/129588
ISSN
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorCheng, Ren_HK
dc.contributor.authorXie, Xen_HK
dc.contributor.authorYiu, MLen_HK
dc.contributor.authorChen, Jen_HK
dc.contributor.authorSun, Len_HK
dc.date.accessioned2010-12-23T08:39:31Z-
dc.date.available2010-12-23T08:39:31Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 26th IEEE International Conference on Data Engineering (ICDE 2010), Long Beach, CA., 1-6 March 2010. In Proceedings of the 26th ICDE, 2010, p. 796-807en_HK
dc.identifier.issn1084-4627en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129588-
dc.description.abstractThe Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. In this paper, we study how the Voronoi diagram can be used on uncertain data, which are inherent in scientific and business applications. In particular, we propose the Uncertain-Voronoi Diagram (or UV-diagram in short). Conceptually, the data space is divided into distinct "UV-partitions", where each UV-partition P is associated with a set S of objects; any point q located in P has the set S as its nearest neighbor with non-zero probabilities. The UV-diagram facilitates queries that inquire objects for having non-zero chances of being the nearest neighbor of a given query point. It also allows analysis of nearest neighbor information, e.g., finding out how many objects are the nearest neighbors in a given area. However, a UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation for UV-partitions, and develop an adaptive index for the UV-diagram. This index can be constructed in polynomial time. We examine how it can be extended to support other related queries. We also perform extensive experiments to validate the effectiveness of our approach. © 2010 IEEE.en_HK
dc.languageengen_US
dc.publisherIEEE, Computer Society.-
dc.relation.ispartofProceedings of the 26th IEEE International Conference on Data Engineering, ICDE 2010en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsInternational Conference on Data Engineering. Proceedings. Copyright © IEEE, Computer Society.-
dc.rights©2010 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.subjectBusiness applications-
dc.subjectData space-
dc.subjectNearest neighbors-
dc.subjectNearest-neighbor query-
dc.subjectNon-zero probability-
dc.titleUV-diagram: A Voronoi diagram for uncertain dataen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1084-4627&volume=&spage=796&epage=807&date=2010&atitle=UV-diagram:+A+voronoi+diagram+for+uncertain+data-
dc.identifier.emailCheng, R:ckcheng@cs.hku.hken_HK
dc.identifier.authorityCheng, R=rp00074en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/ICDE.2010.5447917en_HK
dc.identifier.scopuseid_2-s2.0-77952758928en_HK
dc.identifier.hkuros176461en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77952758928&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage796en_HK
dc.identifier.epage807en_HK
dc.identifier.isiWOS:000286933100086-
dc.publisher.placeUnited Statesen_HK
dc.description.otherThe 26th IEEE International Conference on Data Engineering (ICDE 2010), Long Beach, CA., 1-6 March 2010. In Proceedings of the 26th ICDE, 2010, p. 796-807-
dc.identifier.scopusauthoridCheng, R=7201955416en_HK
dc.identifier.scopusauthoridXie, X=34881209700en_HK
dc.identifier.scopusauthoridYiu, ML=8589889600en_HK
dc.identifier.scopusauthoridChen, J=23501401700en_HK
dc.identifier.scopusauthoridSun, L=36083786800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats