NDLI: Probabilistic n-of-N skyline computation over uncertain data streams

Content Provider	Springer Nature Link
Author	Zhang, Wenjie Li, Aiping Cheema, Muhammad Aamir Zhang, Ying Chang, Lijun
Copyright Year	2014
Abstract	Skyline operator is a useful tool in multi-criteria decision making in various applications. Uncertainty is inherent in real applications due to various reasons. In this paper, we consider the problem of efficiently computing probabilistic skylines against the most recent N uncertain elements in a data stream seen so far. Specifically, we study the problem in the n-of-N model; that is, computing the probabilistic skyline for the most recent n (∀ n ≤ N) elements, where an element is a probabilistic skyline element if its skyline probability is not below a given probability threshold q. Firstly, an effective pruning technique to minimize the number of uncertain elements to be kept is developed. It can be shown that on average storing only O(log $^{ d }$ N) uncertain elements from the most recent N elements is sufficient to support the precise computation of all probabilistic n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. A novel encoding scheme is then proposed together with efficient update techniques so that computing a probabilistic n-of-N skyline query in a d-dimension space is reduced to O(dloglogN + s) if the data distribution is independent, where s is the number of skyline points. A trigger based technique is provided to process continuous n-of-N skyline queries. Extensive experiments demonstrate that the new techniques on uncertain data streams can support on-line probabilistic skyline query computation over rapid data streams.
Starting Page	1331
Ending Page	1350
Page Count	20
File Format	PDF
ISSN	1386145X
Journal	World Wide Web
Volume Number	18
Issue Number	5
e-ISSN	15731413
Language	English
Publisher	Springer US
Publisher Date	2014-07-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Skyline Stream Query processing Uncertain Information Systems Applications (incl. Internet) Database Management Operating Systems
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications 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

Efficient group-by reverse skyline computation

Probabilistic nearest neighbor query processing on distributed uncertain data

Top- $symbol{k}$ query processing over uncertain data in distributed environments

Efficient processing of top-k twig queries over probabilistic XML data

ELCA evaluation for keyword search on probabilistic XML data

Evaluating continuous top-k queries over document streams

Probabilistic Web Data Management

Aggregate nearest neighbor queries in uncertain graphs

Tracking frequent items over distributed probabilistic data

Probabilistic n-of-N skyline computation over uncertain data streams

Similar Documents

Efficient group-by reverse skyline computation

Probabilistic nearest neighbor query processing on distributed uncertain data

Top- $symbol{k}$ query processing over uncertain data in distributed environments

Efficient processing of top-k twig queries over probabilistic XML data

ELCA evaluation for keyword search on probabilistic XML data

Evaluating continuous top-k queries over document streams

Probabilistic Web Data Management

Aggregate nearest neighbor queries in uncertain graphs

Tracking frequent items over distributed probabilistic data

Probabilistic n-of-N skyline computation over uncertain data streams