NDLI: Probabilistic skylines on uncertain data: model and bounding-pruning-refining methods

Content Provider	Springer Nature Link
Author	Jiang, Bin Pei, Jian Lin, Xuemin Yuan, Yidong
Copyright Year	2010
Abstract	Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedicated to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced analysis on uncertain data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all objects whose skyline probabilities are at least p (0 < p ≤ 1). Computing probabilistic skylines on large uncertain data sets is challenging. We develop a bounding-pruning-refining framework and three algorithms systematically. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Combining the advantages of the bottom-up algorithm and the top-down algorithm, we develop a hybrid algorithm to further improve the performance. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our algorithms are efficient on large data sets.
Starting Page	1
Ending Page	39
Page Count	39
File Format	PDF
ISSN	09259902
Journal	Journal of Intelligent Information Systems
Volume Number	38
Issue Number	1
e-ISSN	15737675
Language	English
Publisher	Springer US
Publisher Date	2010-11-27
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Uncertain data Skyline queries Probabilistic queries Algorithms Business Information Systems Information Storage and Retrieval Data Structures, Cryptology and Information Theory Document Preparation and Text Processing Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Computer Networks and Communications Information Systems Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Processing skyline queries in incomplete distributed databases

Efficient pruning for top-K ranking queries on attribute-wise uncertain datasets

Mining Bayesian networks out of ontologies

Provisional reporting for rank joins

Efficient processing of top-k queries: selective NRA algorithms

Processing continuous K-nearest skyline query with uncertainty in spatio-temporal databases

Link classification with probabilistic graphs

Mining complex patterns

Drum Loops Retrieval from Spoken Queries

Probabilistic skylines on uncertain data: model and bounding-pruning-refining methods

Similar Documents

Processing skyline queries in incomplete distributed databases

Efficient pruning for top-K ranking queries on attribute-wise uncertain datasets

Mining Bayesian networks out of ontologies

Provisional reporting for rank joins

Efficient processing of top-k queries: selective NRA algorithms

Processing continuous K-nearest skyline query with uncertainty in spatio-temporal databases

Link classification with probabilistic graphs

Mining complex patterns

Drum Loops Retrieval from Spoken Queries

Probabilistic skylines on uncertain data: model and bounding-pruning-refining methods