Skyline query processing for incomplete data (2022)

Abstract

Recently, there has been much interest in processing skyline queries for various applications that include decision making, personalized services, and search pruning. Skyline queries aim to prune a search space of large numbers of multi-dimensional data items to a small set of interesting items by eliminating items that are dominated by others. Existing skyline algorithms assume that all dimensions are available for all data items. This paper goes beyond this restrictive assumption as we address the more practical case of involving incomplete data items (i.e., data items missing values in some of their dimensions). In contrast to the case of complete data where the dominance relation is transitive, incomplete data suffer from non-transitive dominance relation which may lead to a cyclic dominance behavior. We first propose two algorithms, namely, "Replacement" and "Bucket" that use traditional skyline algorithms for incomplete data. Then, we propose the "ISkyline" algorithm that is designed specifically for the case of incomplete data. The "ISkyline" algorithm employs two optimization techniques, namely, virtual points and shadow skylines to tolerate cyclic dominance relations. Experimental evidence shows that the "ISkyline" algorithm significantly outperforms variations of traditional skyline algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Pages556-565
Number of pages10
DOIs
StatePublished - 2008
Event2008 IEEE 24th International Conference on Data Engineering, ICDE'08 - Cancun, Mexico
Duration: Apr 7 2008Apr 12 2008

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Country/TerritoryMexico
CityCancun
Period4/7/084/12/08

Publisher link

Other files and links

Fingerprint

Dive into the research topics of 'Skyline query processing for incomplete data'. Together they form a unique fingerprint.

View full fingerprint

Cite this

  • APA
  • Standard
  • Harvard
  • Vancouver
  • Author
  • BIBTEX
  • RIS

Khalefa, M. E., Mokbel, M. F., & Levandoski, J. J. (2008). Skyline query processing for incomplete data. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08 (pp. 556-565). [4497464] (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2008.4497464

Skyline query processing for incomplete data. / Khalefa, Mohamed E.; Mokbel, Mohamed F.; Levandoski, Justin J.

Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08. 2008. p. 556-565 4497464 (Proceedings - International Conference on Data Engineering).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

(Video) 041 skyline queries

Khalefa, ME, Mokbel, MF & Levandoski, JJ 2008, Skyline query processing for incomplete data. in Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08., 4497464, Proceedings - International Conference on Data Engineering, pp. 556-565, 2008 IEEE 24th International Conference on Data Engineering, ICDE'08, Cancun, Mexico, 4/7/08. https://doi.org/10.1109/ICDE.2008.4497464

Khalefa ME, Mokbel MF, Levandoski JJ. Skyline query processing for incomplete data. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08. 2008. p. 556-565. 4497464. (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2008.4497464

Khalefa, Mohamed E. ; Mokbel, Mohamed F. ; Levandoski, Justin J. / Skyline query processing for incomplete data. Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08. 2008. pp. 556-565 (Proceedings - International Conference on Data Engineering).

@inproceedings{b86f609c804d49b8aa02609350d93ce8,

title = "Skyline query processing for incomplete data",

abstract = "Recently, there has been much interest in processing skyline queries for various applications that include decision making, personalized services, and search pruning. Skyline queries aim to prune a search space of large numbers of multi-dimensional data items to a small set of interesting items by eliminating items that are dominated by others. Existing skyline algorithms assume that all dimensions are available for all data items. This paper goes beyond this restrictive assumption as we address the more practical case of involving incomplete data items (i.e., data items missing values in some of their dimensions). In contrast to the case of complete data where the dominance relation is transitive, incomplete data suffer from non-transitive dominance relation which may lead to a cyclic dominance behavior. We first propose two algorithms, namely, {"}Replacement{"} and {"}Bucket{"} that use traditional skyline algorithms for incomplete data. Then, we propose the {"}ISkyline{"} algorithm that is designed specifically for the case of incomplete data. The {"}ISkyline{"} algorithm employs two optimization techniques, namely, virtual points and shadow skylines to tolerate cyclic dominance relations. Experimental evidence shows that the {"}ISkyline{"} algorithm significantly outperforms variations of traditional skyline algorithms.",

author = "Khalefa, {Mohamed E.} and Mokbel, {Mohamed F.} and Levandoski, {Justin J.}",

(Video) Skyline Preference Query Based on Massive and Incomplete Dataset

year = "2008",

doi = "10.1109/ICDE.2008.4497464",

language = "English (US)",

isbn = "9781424418374",

series = "Proceedings - International Conference on Data Engineering",

pages = "556--565",

booktitle = "Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08",

note = "2008 IEEE 24th International Conference on Data Engineering, ICDE'08 ; Conference date: 07-04-2008 Through 12-04-2008",

}

TY - GEN

T1 - Skyline query processing for incomplete data

AU - Khalefa, Mohamed E.

AU - Mokbel, Mohamed F.

AU - Levandoski, Justin J.

(Video) Adaptive Processing for Distributed Skyline Queries over Uncertain Data

PY - 2008

Y1 - 2008

N2 - Recently, there has been much interest in processing skyline queries for various applications that include decision making, personalized services, and search pruning. Skyline queries aim to prune a search space of large numbers of multi-dimensional data items to a small set of interesting items by eliminating items that are dominated by others. Existing skyline algorithms assume that all dimensions are available for all data items. This paper goes beyond this restrictive assumption as we address the more practical case of involving incomplete data items (i.e., data items missing values in some of their dimensions). In contrast to the case of complete data where the dominance relation is transitive, incomplete data suffer from non-transitive dominance relation which may lead to a cyclic dominance behavior. We first propose two algorithms, namely, "Replacement" and "Bucket" that use traditional skyline algorithms for incomplete data. Then, we propose the "ISkyline" algorithm that is designed specifically for the case of incomplete data. The "ISkyline" algorithm employs two optimization techniques, namely, virtual points and shadow skylines to tolerate cyclic dominance relations. Experimental evidence shows that the "ISkyline" algorithm significantly outperforms variations of traditional skyline algorithms.

AB - Recently, there has been much interest in processing skyline queries for various applications that include decision making, personalized services, and search pruning. Skyline queries aim to prune a search space of large numbers of multi-dimensional data items to a small set of interesting items by eliminating items that are dominated by others. Existing skyline algorithms assume that all dimensions are available for all data items. This paper goes beyond this restrictive assumption as we address the more practical case of involving incomplete data items (i.e., data items missing values in some of their dimensions). In contrast to the case of complete data where the dominance relation is transitive, incomplete data suffer from non-transitive dominance relation which may lead to a cyclic dominance behavior. We first propose two algorithms, namely, "Replacement" and "Bucket" that use traditional skyline algorithms for incomplete data. Then, we propose the "ISkyline" algorithm that is designed specifically for the case of incomplete data. The "ISkyline" algorithm employs two optimization techniques, namely, virtual points and shadow skylines to tolerate cyclic dominance relations. Experimental evidence shows that the "ISkyline" algorithm significantly outperforms variations of traditional skyline algorithms.

UR - http://www.scopus.com/inward/record.url?scp=52649139904&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52649139904&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2008.4497464

DO - 10.1109/ICDE.2008.4497464

M3 - Conference contribution

AN - SCOPUS:52649139904

SN - 9781424418374

T3 - Proceedings - International Conference on Data Engineering

SP - 556

EP - 565

BT - Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08

T2 - 2008 IEEE 24th International Conference on Data Engineering, ICDE'08

(Video) Skyline Query

Y2 - 7 April 2008 through 12 April 2008

ER -

Videos

1. Constrained Skyline Query Processing Against Distributed Data Sites
(SKIVE PROJECTS CHENNAI)
2. Top-k Dominating Queries on Incomplete Data
(JP INFOTECH PROJECTS)
3. Secure and Efficient Query Processing in Sensor Networks - preserving privacy and integrity of data
(Ebby Marshall)
4. Efficient Processing of Skyline Queries Using
(Kalaiselvi Elumalai)
5. Top k query processing Malicious Node Grouping MANETs projects
(PHDPROJECTS. ORG)
6. Skyline Preference Query Based
(SivaKumar ChennaiSunday)

Top Articles

You might also like

Latest Posts

Article information

Author: Nathanael Baumbach

Last Updated: 01/09/2023

Views: 5998

Rating: 4.4 / 5 (75 voted)

Reviews: 90% of readers found this page helpful

Author information

Name: Nathanael Baumbach

Birthday: 1998-12-02

Address: Apt. 829 751 Glover View, West Orlando, IN 22436

Phone: +901025288581

Job: Internal IT Coordinator

Hobby: Gunsmithing, Motor sports, Flying, Skiing, Hooping, Lego building, Ice skating

Introduction: My name is Nathanael Baumbach, I am a fantastic, nice, victorious, brave, healthy, cute, glorious person who loves writing and wants to share my knowledge and understanding with you.