Multi-criteria decision making has been made possible with the advent of skyline queries. However, processing such queries for high dimensional datasets remains a time consuming task. Real-time applications are thus infeasible, especially for non-indexed skyline techniques where the datasets arrive online. In this paper, we propose a caching mechanism that uses the semantics of previous skyline queries to improve the processing time of a new query. In addition to exact queries, utilizing such special semantics allow accelerating related queries. We achieve this by generating partial result sets guaranteed to be in the skyline sets. We also propose an index structure for efficient organization of the cached queries. Experiments on synthetic and real datasets show the effectiveness and scalability of our proposed methods.
@cite_6: Skyline queries ask for a set of interesting points from a potentially large set of data points. If we are traveling, for instance, a restaurant might be interesting if there is no other restaurant which is nearer, cheaper, and has better food. Skyline queries retrieve all such interesting restaurants so that the user can choose the most promising one. In this paper, we present a new online algorithm that computes the Skyline. Unlike most existing algorithms that compute the Skyline in a batch, this algorithm returns the first results immediately, produces more and more results continuously, and allows the user to give preferences during the running time of the algorithm so that the user can control what kind of results are produced next (e.g., rather cheap or rather near restaurants).
@cite_3: The skyline of a set of d-dimensional points 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 (or online) algorithms that can quickly return the first skyline points without having to read the entire data file. Currently, the most efficient algorithm is NN ( n earest n eighbors), which applies the divide -and-conquer framework on datasets indexed by R-trees. Although NN has some desirable features (such as high speed for returning the initial skyline points, applicability to arbitrary data distributions and dimensions), it also presents several inherent disadvantages (need for duplicate elimination if d>2, multiple accesses of the same node, large space overhead). In this paper we develop BBS ( b ranch-and- b ound s kyline), a progressive algorithm also based on nearest neighbor search, which is IO optimal, i.e., it performs a single access only to those R-tree nodes that may contain skyline points. Furthermore, it does not retrieve duplicates and its space overhead is significantly smaller than that of NN. Finally, BBS is simple to implement and can be efficiently applied to a variety of alternative skyline queries. An analytical and experimental comparison shows that BBS outperforms NN (usually by orders of magnitude) under all problem instances.
@cite_5: We propose to extend database systems by a Skyline operation. This operation filters out a set of interesting points from a potentially large set of data points. A point is interesting if it is not dominated by any other point. For example, a hotel might be interesting for somebody traveling to Nassau if no other hotel is both cheaper and closer to the beach. We show how SSL can be extended to pose Skyline queries, present and evaluate alternative algorithms to implement the Skyline operation, and show how this operation can be combined with other database operations, e.g., join.
@cite_16: Finding the maximals in a collection of vectors is relevant to many applications. The maximal set is related to the convex hull---and hence, linear optimization---and nearest neighbors. The maximal vector problem has resurfaced with the advent of skyline queries for relational databases and skyline algorithms that are external and relationally well behaved.The initial algorithms proposed for maximals are based on divide-and-conquer. These established good average and worst case asymptotic running times, showing it to be O(n) average-case. where n is the number of vectors. However, they are not amenable to externalizing. We prove, furthermore, that their performance is quite bad with respect to the dimensionality, k, of the problem. We demonstrate that the more recent external skyline algorithms are actually better behaved, although they do not have as good an apparent asymptotic complexity. We introduce a new external algorithm, LESS, that combines the best features of these. experimentally evaluate its effectiveness and improvement over the field, and prove its average-case running time is O(kn).
@cite_13: H. T. KUNG Carnegze-Mellon Un verszty, P2ttsburgh, Pennsylvanza F. LUCCIO Unwerszht d P sa, P sa, Italy F. P. PREPARATA University of Ilhno s, Urbana, Illinois ASSTRACT. Let U1 , U2, . . . , Ud be totally ordered sets and let V be a set of n d-dimensional vectors In U X Us. . X Ud . A partial ordering is defined on V in a natural way The problem of finding all maximal elements of V with respect to the partial ordering s considered The computational com- plexity of the problem is defined to be the number of required comparisons of two components and is denoted by Cd(n). It is tnwal that C (n) = n - 1 and C, (n) _ flog2 n!l for d _> 2
@cite_11: The skyline, or Pareto, operator selects those tuples that are not dominated by any others. Extending relational systems with the skyline operator would offer a basis for handling preference queries. Good algorithms are needed for skyline, however, to make this efficient in a relational setting. We propose a skyline algorithm, SFS, based on presorting that is general, for use with any skyline query, efficient, and well behaved in a relational setting.
Skyline queries have been imported to databases from the maximum vector problem or Pareto curve @cite_13 in computational geometry. The first algorithm was proposed by @cite_13 . BNL @cite_5 uses a nested loop approach by repeatedly reading the set of tuples. SFS @cite_11 improves it by sorting the data based on a monotone function. LESS @cite_16 combines the best features of these external algorithms; however, its performance depends on the availability of pre-sorted data. A approach to partition the data so as to fit into the main memory was proposed in @cite_11 . Using index structures, algorithms such as NN @cite_6 and BBS @cite_3 have been proposed.