File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Clustering uncertain data using voronoi diagrams and R-tree index

TitleClustering uncertain data using voronoi diagrams and R-tree index
Authors
Keywordsclustering
indexing methods
object hierarchies
Uncertainty
Issue Date2010
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
Citation
Ieee Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 9, p. 1219-1233 How to Cite?
AbstractWe study the problem of clustering uncertain objects whose locations are described by probability density functions (pdfs). We show that the UK-means algorithm, which generalizes the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (EDs) between objects and cluster representatives. For arbitrary pdfs, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculations. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organize the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods. © 2006 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/129978
ISSN
2023 Impact Factor: 8.9
2023 SCImago Journal Rankings: 2.867
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong Research Grants CouncilHKU 7134/06E
Funding Information:

This research is supported by Hong Kong Research Grants Council Grant HKU 7134/06E.

References
Grants

 

DC FieldValueLanguage
dc.contributor.authorKao, Ben_HK
dc.contributor.authorLee, SDen_HK
dc.contributor.authorLee, FKFen_HK
dc.contributor.authorCheung, DWen_HK
dc.contributor.authorHo, WSen_HK
dc.date.accessioned2010-12-23T08:45:06Z-
dc.date.available2010-12-23T08:45:06Z-
dc.date.issued2010en_HK
dc.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 9, p. 1219-1233en_HK
dc.identifier.issn1041-4347en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129978-
dc.description.abstractWe study the problem of clustering uncertain objects whose locations are described by probability density functions (pdfs). We show that the UK-means algorithm, which generalizes the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (EDs) between objects and cluster representatives. For arbitrary pdfs, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculations. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organize the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods. © 2006 IEEE.en_HK
dc.languageengen_US
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tkdeen_HK
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineeringen_HK
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.subjectclusteringen_HK
dc.subjectindexing methodsen_HK
dc.subjectobject hierarchiesen_HK
dc.subjectUncertaintyen_HK
dc.titleClustering uncertain data using voronoi diagrams and R-tree indexen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1041-4347&volume=22&issue=9&spage=1219&epage=1233&date=2010&atitle=Clustering+uncertain+data+using+voronoi+diagrams+and+R-tree+index-
dc.identifier.emailKao, B: kao@cs.hku.hken_HK
dc.identifier.emailCheung, DW: dcheung@cs.hku.hken_HK
dc.identifier.emailHo, WS: wsho@cs.hku.hken_HK
dc.identifier.authorityKao, B=rp00123en_HK
dc.identifier.authorityCheung, DW=rp00101en_HK
dc.identifier.authorityHo, WS=rp01730en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/TKDE.2010.82en_HK
dc.identifier.scopuseid_2-s2.0-77955150205en_HK
dc.identifier.hkuros176926en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955150205&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume22en_HK
dc.identifier.issue9en_HK
dc.identifier.spage1219en_HK
dc.identifier.epage1233en_HK
dc.identifier.isiWOS:000280134800003-
dc.publisher.placeUnited Statesen_HK
dc.relation.projectComputational issues in mining uncertain data-
dc.identifier.scopusauthoridKao, B=35221592600en_HK
dc.identifier.scopusauthoridLee, SD=7601400741en_HK
dc.identifier.scopusauthoridLee, FKF=36195751200en_HK
dc.identifier.scopusauthoridCheung, DW=34567902600en_HK
dc.identifier.scopusauthoridHo, WS=7402968940en_HK
dc.identifier.issnl1041-4347-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats