File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Scalable probabilistic similarity ranking in uncertain databases

TitleScalable probabilistic similarity ranking in uncertain databases
Authors
Keywordsprobabilistic ranking
similarity search
Uncertain databases
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. 1234-1246 How to Cite?
AbstractThis paper introduces a scalable approach for probabilistic top-k similarity ranking on uncertain vector data. Each uncertain object is represented by a set of vector instances that is assumed to be mutually exclusive. The objective is to rank the uncertain data according to their distance to a reference object. We propose a framework that incrementally computes for each object instance and ranking position, the probability of the object falling at that ranking position. The resulting rank probability distribution can serve as input for several state-of-the-art probabilistic ranking models. Existing approaches compute this probability distribution by applying the Poisson binomial recurrence technique of quadratic complexity. In this paper, we theoretically as well as experimentally show that our framework reduces this to a linear-time complexity while having the same memory requirements, facilitated by incremental accessing of the uncertain vector instances in increasing order of their distance to the reference object. Furthermore, we show how the output of our method can be used to apply probabilistic top-k ranking for the objects, according to different state-of-the-art definitions. We conduct an experimental evaluation on synthetic and real data, which demonstrates the efficiency of our approach. © 2006 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/138036
ISSN
2015 Impact Factor: 2.476
2015 SCImago Journal Rankings: 2.087
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorBernecker, Ten_HK
dc.contributor.authorKriegel, HPen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorRenz, Men_HK
dc.contributor.authorZuefle, Aen_HK
dc.date.accessioned2011-08-26T14:39:02Z-
dc.date.available2011-08-26T14:39:02Z-
dc.date.issued2010en_HK
dc.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 9, p. 1234-1246en_HK
dc.identifier.issn1041-4347en_HK
dc.identifier.urihttp://hdl.handle.net/10722/138036-
dc.description.abstractThis paper introduces a scalable approach for probabilistic top-k similarity ranking on uncertain vector data. Each uncertain object is represented by a set of vector instances that is assumed to be mutually exclusive. The objective is to rank the uncertain data according to their distance to a reference object. We propose a framework that incrementally computes for each object instance and ranking position, the probability of the object falling at that ranking position. The resulting rank probability distribution can serve as input for several state-of-the-art probabilistic ranking models. Existing approaches compute this probability distribution by applying the Poisson binomial recurrence technique of quadratic complexity. In this paper, we theoretically as well as experimentally show that our framework reduces this to a linear-time complexity while having the same memory requirements, facilitated by incremental accessing of the uncertain vector instances in increasing order of their distance to the reference object. Furthermore, we show how the output of our method can be used to apply probabilistic top-k ranking for the objects, according to different state-of-the-art definitions. We conduct an experimental evaluation on synthetic and real data, which demonstrates the efficiency of our approach. © 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.rightsIEEE Transactions on Knowledge & Data Engineering. Copyright © IEEE.-
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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectprobabilistic rankingen_HK
dc.subjectsimilarity searchen_HK
dc.subjectUncertain databasesen_HK
dc.titleScalable probabilistic similarity ranking in uncertain databasesen_HK
dc.typeArticleen_HK
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/TKDE.2010.78en_HK
dc.identifier.scopuseid_2-s2.0-77955134730en_HK
dc.identifier.hkuros190922en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955134730&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume22en_HK
dc.identifier.issue9en_HK
dc.identifier.spage1234en_HK
dc.identifier.epage1246en_HK
dc.identifier.isiWOS:000280134800004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridBernecker, T=24512341500en_HK
dc.identifier.scopusauthoridKriegel, HP=7005718994en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridRenz, M=22433777600en_HK
dc.identifier.scopusauthoridZuefle, A=25029386800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats