ACM Transactions on Database Systems · 2005 · 886 citations · 30 references
ComputingComputer ScienceAlgorithmsComputational GeometryDatabasesData Structure AlgorithmsDatabase ManagementNearest Neighbor SearchQuery ProcessingSearching AlgorithmsIndex StructuresNearest Neighbor Data StructuresScalable IndexingUser Preferences
Skyline queries identify nondominated points in multi‑dimensional data, and while progressive methods promise fast initial results, existing algorithms suffer from practical limitations. The paper introduces BBS, an I/O‑optimal branch‑and‑bound skyline algorithm that accesses only nodes potentially containing skyline points. BBS uses nearest‑neighbor search to prune the search space, is easy to implement, supports arbitrary dimensionality and user preferences, and can be adapted to several skyline variations. BBS efficiently handles multiple skyline variations, demonstrating its versatility.
The skyline of a d -dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.
30
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
S. Borzsony, Donald Kossmann, Konrad Stocker · 2002 · 2.2K citations
Nick Roussopoulos, Stephen Kelley, F. Vincent · 1995 · 1.4K citations · Full text