Skylines, and other directly related problems such as multiobjective opti- mization [Steuer 1986], maximum vectors [Kung et al. 1975; Matousek 1991], and the contour problem [McLain 1974], have been extensively studied and nu- merous algorithms have been proposed formain-memory processing. To the best of our knowledge, however, the first work addressing skylines in the context of databaseswasBorzsonyi et al. [2001],which develops algorithms based on block nested loops, divide-and-conquer, and index scanning. An improved version of block nested loops is presented in Chomicki et al. [2003]. Tan et al. [2001] pro- posed progressive (or on-line) algorithms that can output skyline points without having to scan the entire data input. Kossmann.
