NDLI: Stabbing the sky: efficient skyline computation over sliding windows

Content Provider	IEEE Xplore Digital Library
Author	Xuemin Lin Yidong Yuan Wei Wang Hongjun Lu
Copyright Year	2005
Description	Author affiliation: Univ. of New South Wales, Sydney, NSW, Australia (Xuemin Lin; Yidong Yuan; Wei Wang)
Abstract	We consider the problem of efficiently computing the skyline against the most recent N elements in a data stream seen so far. Specifically, we study the n-of-N skyline queries; that is, computing the skyline for the most recent n (/spl forall/n/spl les/N) elements. Firstly, we developed an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average storing only O(log/sup d/ N) elements from the most recent N elements is sufficient to support the precise computation of all n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. Then, a novel encoding scheme is proposed, together with efficient update techniques, for the stored elements, so that computing an n-of-N skyline query in a d-dimension space takes O(log N+s) time that is reduced to O(d log log N+s) if the data distribution is independent, where s is the number of skyline points. Thirdly, a novel trigger based technique is provided to process continuous n-of-N skyline queries with O(/spl delta/) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where /spl delta/ is the number of element changes from the current result to the new result. Finally, we extend our techniques to computing the skyline against an arbitrary window in the most recent N element. Besides theoretical performance guarantees, our extensive experiments demonstrated that the new techniques can support on-line skyline query computation over very rapid data streams.
Sponsorship	IEEE Comput. Soc. Database Soc. of Japan (DBSJ) Inf. Process. Soc. of Japan (IPSJ) Inst. of Electron., Inf. and Commun. Eng. (IEICE)
Starting Page	502
Ending Page	513
File Size	349493
Page Count	12
File Format	PDF
ISBN	0769522858
ISSN	10844627
DOI	10.1109/ICDE.2005.137
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-04-05
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Distributed computing Australia Encoding Decision making Stock markets Statistics Query processing Databases Algorithm design and analysis Computational modeling
Content Type	Text
Resource Type	Article
Subject	Signal Processing Information Systems Software

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

Probabilistic Skyline Operators over Sliding Windows Windows

Stabbing the sky: Efficient skyline computation over sliding windows (2005)

Probabilistic skyline operator over sliding windows (2009)

Stabbing the Sky: Efficient Skyline Computation over Sliding Windows (2005)

Efficient and Progressive Algorithms for Distributed Skyline Queries over Uncertain Data

Multi-criteria decision making with skyline computation

An efficient scheme for continuous skyline query processing over dynamic data set

Evaluation of communication and computation efficient algorithms for distributed skyline queries

Skyline-join in distributed databases

Stabbing the sky: efficient skyline computation over sliding windows

Similar Documents

Probabilistic Skyline Operators over Sliding Windows Windows

Stabbing the sky: Efficient skyline computation over sliding windows (2005)

Probabilistic skyline operator over sliding windows (2009)

Stabbing the Sky: Efficient Skyline Computation over Sliding Windows (2005)

Efficient and Progressive Algorithms for Distributed Skyline Queries over Uncertain Data

Multi-criteria decision making with skyline computation

An efficient scheme for continuous skyline query processing over dynamic data set

Evaluation of communication and computation efficient algorithms for distributed skyline queries

Skyline-join in distributed databases

Stabbing the sky: efficient skyline computation over sliding windows