Shooting Stars in the Sky

Publisher Summary

Skyline queries are important for several database applications, including customer information systems, decision support, and data visualization. This chapter presents a study on new online algorithm to compute Skyline queries. This algorithm is called the NN algorithm, because it is based on nearest neighbor search, a well-studied database operation. It compares this new algorithm to existing algorithms that compute the Skyline in a batch and to existing algorithms that work progressively. Skyline queries can also involve more than two dimensions and they could depend on the current position of a user. For instance, (mobile) users could be interested in restaurants that are near, cheap, and have good food (according to some rating system). The distance is based on the current location of the user. Again, the idea is to give the user the big picture of interesting options and then let the user make a decision. If the user moves on, the Skyline should be recomputed continuously in order to give the user a choice of interesting restaurants based on the user's new location.