NDLI: DeltaSky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation

Content Provider	IEEE Xplore Digital Library
Author	Ping Wu Agrawal, D. Egecioglu, O. El Abbadi, A.
Copyright Year	2007
Description	Author affiliation: Dept. of Comput. Sci., California Univ., Santa Barbara, CA, USA (Ping Wu; Agrawal, D.; Egecioglu, O.; El Abbadi, A.)
Abstract	This paper addresses the problem of efficient maintenance of a materialized skyline view in response to skyline removals. While there has been significant progress on skyline query computation, an equally important but largely unanswered issue is on the incremental maintenance for skyline deletions. Previous work suggested the use of the so called exclusive dominance region (EDR) to achieve optimal I/O performance for deletion maintenance. However, the shape of an EDR becomes extremely complex in higher dimensions, and algorithms for its computation have not been developed. We derive a systematic way to decompose a d-dimensional EDR into a collection of hyper-rectangles. We show that the number of such hyper-rectangles is O(md), where m is the current skyline result size. We then propose a novel algorithm DeltaSky which determines whether an intermediate R-tree MBR intersects with the EDR without explicitly calculating the EDR itself. This reduces the worse case complexity of the EDR intersection check from O(md) to O(md). Thus DeltaSky helps the branch and bound skyline algorithm achieve I/O optimality for deletion maintenance by finding only the newly appeared skyline points after the deletion. We discuss implementation issues and show that DeltaSky can be efficiently implemented using one extra B-Tree. Moreover, we propose two optimization techniques which further reduce the average cost in practice. Extensive experiments demonstrate that DeltaSky achieves orders of magnitude performance gain over alternative solutions.
Starting Page	486
Ending Page	495
File Size	311031
Page Count	10
File Format	PDF
ISBN	1424408024
DOI	10.1109/ICDE.2007.367894
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-04-15
Publisher Place	Turkey
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer science Shape Cost function Performance gain Query processing Algorithm design and analysis Acceleration Database systems
Content Type	Text
Resource Type	Article

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

Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation (2007)

Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation (2007)

Decoupled query optimization for federated database systems

1continuous skyline queries for moving objects.

A modular query optimizer generator

An efficient grid-based framework for answering tolerance-based skyline queries

Skyline Query algorithm based on MB-tree

Finding All Competitive Products Using the Dominant Relationship Analysis

Maintenance of placement dependency in distributed multidatabase systems

DeltaSky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation

Similar Documents

Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation (2007)

Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation (2007)

Decoupled query optimization for federated database systems

1continuous skyline queries for moving objects.

A modular query optimizer generator

An efficient grid-based framework for answering tolerance-based skyline queries

Skyline Query algorithm based on MB-tree

Finding All Competitive Products Using the Dominant Relationship Analysis

Maintenance of placement dependency in distributed multidatabase systems

DeltaSky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation