File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A novel probabilistic pruning approach to speed up similarity queries in uncertain databases

TitleA novel probabilistic pruning approach to speed up similarity queries in uncertain databases
Authors
KeywordsExperimental evaluation
Multi-dimensional space
Possible world semantics
Probabilistic density function
Probability bound
Issue Date2011
PublisherIEEE, Computer Society.
Citation
The 27th International Conference on Data Engineering (ICDE 2011), Hannover, Germany, 11-16 April 2011. In Proceedings of the International Conference on Data Engineering, 2011, p. 339-350 How to Cite?
AbstractIn this paper, we propose a novel, effective and efficient probabilistic pruning criterion for probabilistic similarity queries on uncertain data. Our approach supports a general uncertainty model using continuous probabilistic density functions to describe the (possibly correlated) uncertain attributes of objects. In a nutshell, the problem to be solved is to compute the PDF of the random variable denoted by the probabilistic domination count: Given an uncertain database object B, an uncertain reference object R and a set D of uncertain database objects in a multi-dimensional space, the probabilistic domination count denotes the number of uncertain objects in D that are closer to R than B. This domination count can be used to answer a wide range of probabilistic similarity queries. Specifically, we propose a novel geometric pruning filter and introduce an iterative filter-refinement strategy for conservatively and progressively estimating the probabilistic domination count in an efficient way while keeping correctness according to the possible world semantics. In an experimental evaluation, we show that our proposed technique allows to acquire tight probability bounds for the probabilistic domination count quickly, even for large uncertain databases. © 2011 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/137648
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorBernecker, Ten_HK
dc.contributor.authorEmrich, Ten_HK
dc.contributor.authorKriegel, HPen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorRenz, Men_HK
dc.contributor.authorZüfle, Aen_HK
dc.date.accessioned2011-08-26T14:30:31Z-
dc.date.available2011-08-26T14:30:31Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 27th International Conference on Data Engineering (ICDE 2011), Hannover, Germany, 11-16 April 2011. In Proceedings of the International Conference on Data Engineering, 2011, p. 339-350en_HK
dc.identifier.issn1084-4627en_HK
dc.identifier.urihttp://hdl.handle.net/10722/137648-
dc.description.abstractIn this paper, we propose a novel, effective and efficient probabilistic pruning criterion for probabilistic similarity queries on uncertain data. Our approach supports a general uncertainty model using continuous probabilistic density functions to describe the (possibly correlated) uncertain attributes of objects. In a nutshell, the problem to be solved is to compute the PDF of the random variable denoted by the probabilistic domination count: Given an uncertain database object B, an uncertain reference object R and a set D of uncertain database objects in a multi-dimensional space, the probabilistic domination count denotes the number of uncertain objects in D that are closer to R than B. This domination count can be used to answer a wide range of probabilistic similarity queries. Specifically, we propose a novel geometric pruning filter and introduce an iterative filter-refinement strategy for conservatively and progressively estimating the probabilistic domination count in an efficient way while keeping correctness according to the possible world semantics. In an experimental evaluation, we show that our proposed technique allows to acquire tight probability bounds for the probabilistic domination count quickly, even for large uncertain databases. © 2011 IEEE.en_HK
dc.languageengen_US
dc.publisherIEEE, Computer Society.-
dc.relation.ispartofProceedings of the International Conference on Data Engineeringen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsInternational Conference on Data Engineering. Proceedings. Copyright © IEEE, Computer Society.-
dc.rights©20xx 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.subjectExperimental evaluation-
dc.subjectMulti-dimensional space-
dc.subjectPossible world semantics-
dc.subjectProbabilistic density function-
dc.subjectProbability bound-
dc.titleA novel probabilistic pruning approach to speed up similarity queries in uncertain databasesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1084-4627&volume=&spage=339&epage=350&date=2011&atitle=A+novel+probabilistic+pruning+approach+to+speed+up+similarity+queries+in+uncertain+databases-
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/ICDE.2011.5767908en_HK
dc.identifier.scopuseid_2-s2.0-79957835085en_HK
dc.identifier.hkuros190938en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79957835085&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage339en_HK
dc.identifier.epage350en_HK
dc.publisher.placeUnited Statesen_HK
dc.description.otherThe 27th International Conference on Data Engineering (ICDE 2011), Hannover, Germany, 11-16 April 2011. In Proceedings of the International Conference on Data Engineering, 2011, p. 339-350-
dc.identifier.scopusauthoridBernecker, T=24512341500en_HK
dc.identifier.scopusauthoridEmrich, T=35104699500en_HK
dc.identifier.scopusauthoridKriegel, HP=7005718994en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridRenz, M=22433777600en_HK
dc.identifier.scopusauthoridZüfle, A=26666444500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats