Skyline-sensitive joins with LR-pruning

Mithila Nagendra, Kasim Candan

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

14 Scopus citations


Efficient processing of skyline queries has been an area of growing interest. Most existing techniques assume that the skyline query is applied to a single data table. Unfortunately, this is not true in many applications where, due to the complexity of the schema, the skyline query may involve attributes belonging to multiple tables. Recently, various hybrid skyline-join algorithms have been proposed. However, the current proposals suffer from several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this paper, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely skyline-sensitive join (S 2J) and symmetric skyline-sensitive join (S 3J), to process skyline queries over multiple tables. Our approaches compute the results using a novel layer/region pruning technique (LR-pruning) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S 3J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. We report extensive experimental results that confirm the advantages of the proposed algorithms over the state-of-the-art skyline-join techniques.

Original languageEnglish (US)
Title of host publicationAdvances in Database Technology - EDBT 2012
Subtitle of host publication15th International Conference on Extending Database Technology, Proceedings
Number of pages12
StatePublished - 2012
Event15th International Conference on Extending Database Technology, EDBT 2012 - Berlin, Germany
Duration: Mar 27 2012Mar 30 2012

Publication series

NameACM International Conference Proceeding Series


Other15th International Conference on Extending Database Technology, EDBT 2012


  • skyline-aware join processing

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Skyline-sensitive joins with LR-pruning'. Together they form a unique fingerprint.

Cite this