Mining thick skylines over large databases

Wen Jin, Jiawei Han, Martin Ester

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

People recently are interested in a new operator, called skyline [3], which returns the objects that are not dominated by any other objects with regard to certain measures in a multi-dimensional space. Recent work on the skyline operator [3, 15, 8, 13, 2] focuses on efficient computation of skylines in large databases. However, such work gives users only thin skylines, i.e., single objects, which may not be desirable in some real applications. In this paper, we propose a novel concept, called thick skyline, which recommends not only skyline objects but also their nearby neighbors within ε-distance. Efficient computation methods are developed including (1) two efficient algorithms, Sampling-and-Pruning and Indexing-and-Estimating, to find such thick skyline with the help of statistics or indexes in large databases, and (2) a highly efficient Microcluster-based algorithm for mining thick skyline. The Microcluster-based method not only leads to substantial savings in computation but also provides a concise representation of the thick skyline in the case of high cardinalities. Our experimental performance study shows that the proposed methods are both efficient and effective.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJean-Francois Boulicaut, Floriana Esposito, Fosca Giannotti, Dino Pedreschi
PublisherSpringer-Verlag Berlin Heidelberg
Pages255-266
Number of pages12
ISBN (Print)3540231080, 9783540231080
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3202
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Mining thick skylines over large databases'. Together they form a unique fingerprint.

  • Cite this

    Jin, W., Han, J., & Ester, M. (2004). Mining thick skylines over large databases. In J-F. Boulicaut, F. Esposito, F. Giannotti, & D. Pedreschi (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 255-266). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3202). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-540-30116-5_25