TY - GEN
T1 - Top-k queries over uncertain scores
AU - Liu, Qing
AU - Basu, Debabrota
AU - Abdessalem, Talel
AU - Bressan, Stéphane
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - Modern recommendation systems leverage some forms of collaborative user or crowd sourced collection of information. For instance, services like TripAdvisor, Airbnb and HungyGoWhere rely on usergenerated content to describe and classify hotels, vacation rentals and restaurants. By nature of such independent collection of information, the multiplicity, diversity and varying quality of the information collected result in uncertainty. Objects, such as the services offered by hotels, vacation rentals and restaurants, have uncertain scores for their various features. In this context, ranking of uncertain data becomes a crucial issue. Several data models for uncertain data and several semantics for probabilistic top-k queries have been proposed in the literature. We consider here a model of objects with uncertain scores given as probability distributions and the semantics proposed by the state of the art reference work of Soliman, Hyas and Ben-David. In this paper, we explore the design space of Metropolis-Hastings Markov chain Monte Carlo algorithms for answering probabilistic top-k queries over a database of objects with uncertain scores. We are able to devise several algorithms that yield better performance than the reference algorithm.We empirically and comparatively prove the effectiveness and efficiency of these new algorithms.
AB - Modern recommendation systems leverage some forms of collaborative user or crowd sourced collection of information. For instance, services like TripAdvisor, Airbnb and HungyGoWhere rely on usergenerated content to describe and classify hotels, vacation rentals and restaurants. By nature of such independent collection of information, the multiplicity, diversity and varying quality of the information collected result in uncertainty. Objects, such as the services offered by hotels, vacation rentals and restaurants, have uncertain scores for their various features. In this context, ranking of uncertain data becomes a crucial issue. Several data models for uncertain data and several semantics for probabilistic top-k queries have been proposed in the literature. We consider here a model of objects with uncertain scores given as probability distributions and the semantics proposed by the state of the art reference work of Soliman, Hyas and Ben-David. In this paper, we explore the design space of Metropolis-Hastings Markov chain Monte Carlo algorithms for answering probabilistic top-k queries over a database of objects with uncertain scores. We are able to devise several algorithms that yield better performance than the reference algorithm.We empirically and comparatively prove the effectiveness and efficiency of these new algorithms.
UR - https://www.scopus.com/pages/publications/84995976607
U2 - 10.1007/978-3-319-48472-3_14
DO - 10.1007/978-3-319-48472-3_14
M3 - Conference contribution
AN - SCOPUS:84995976607
SN - 9783319484716
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 245
EP - 262
BT - On the Move to Meaningful Internet Systems
A2 - Dillon, Tharam
A2 - Debruyne, Christophe
A2 - Oâ’Sullivan, Declan
A2 - Panetto, Herve
A2 - Kuhn, Eva
A2 - Ardagna, Claudio Agostino
A2 - Meersman, Robert
PB - Springer Verlag
T2 - Confederated International Conference On the Move to Meaningful Internet Systems, OTM 2016 held in conjunction with Conferences on CoopIS, CandTC and ODBASE 2016
Y2 - 24 October 2016 through 28 October 2016
ER -