Evaluating Top-k Skyline Queries Efficiently - Advanced Database Query Systems - page 115

the multicriteria function over the whole Skyline points. Thus, if k is much smaller than the cardinality
of the Skyline, these solutions may be very inefficient because a large number of non-necessary probes
may be evaluated.
In this chapter, we showed the problem of identifying the Top-k that best meet multidimensional
criteria and adapt the TKSI, an efficient solution for the Top-k Skyline that overcomes existing solutions
drawbacks. The TKSI is an index-based algorithm that is able to compute only the subset of the Skyline
that will be required to produce the top-k objects; thus, the TKSI is able to minimize the number of
non-necessary probes. TKSI was empirically compared to extensions of the state-of-the-art algorithms:
BUS. BUS relies on the computation of the whole set of Skyline to identify the Top-k Skyline while
TKSI builds the Skyline until it has computed the k objects. Initial experimental results show that TKSI
computes the Top-k Skyline performing less number of probes, and have shown that our approach is
able to identify good quality objects and outperform state-of-the-art solutions.
REFERENCES
W3C Semantic Web discussion list. (2010). Kit releases 14 billion triples to the linked open data cloud .
Retrieved from http://permalink.gmane.org/gmane.org.w3c.semantic-web/12889
Balke, W., & Güntzer, U. (2004). Multi-objective query processing for database systems. In Proceedings
of the International Conference on Very Large Databases (VLDB), (pp. 936-947).
Balke, W., Güntzer, U., & Zheng, J. (2004). Efficient distributed skylining for Web Information Systems.
In Proceedings of International Conference on Extending Database Technology (EDBT), (pp. 256-273).
Bentley, J., Kung, H.T., Schkolnick, M. & Thompson, C.D. (1978). On the average number of maxima
in a set of vectors and applications. Journal of ACM (JACM).
Börzsönyi, S., Kossmann, D., & Stocker, K. (2001). The skyline operator. In Proceedings of the 17th
International Conference on Data Engineering , (pp. 421- 430). Washington, DC, USA. IEEE Computer
Society.
Carey, M. J., & Kossmann, D. (1997). On saying \Enough already! in SQL. SIGMOD Record , 26 (2),
219-230. doi:10.1145/253262.253302
Chan, C.-Y., Jagadish, H. V., Tan, K.-L., Tung, A. K. H., & Zhang, Z. (2006a). Finding k-dominant sky-
lines in high dimensional space. In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD International
Conference on Management of Data , (pp. 503-514). New York: ACM.
Chan, C. Y., Jagadish, H. V., Tan, K.-L., Tung, A. K. H., & Zhang, Z. (2006b). On high dimensional
Skylines. In Proceedings of International Conference on Extending Database Technology (EDBT), (pp.
478-495).
De Kunder, M. (2010). The size of the World Wide Web . Retrieved from http://www.worldwidewebsize.com
Godfrey, P., Shipley, R., & Gryz, J. (2005). Maximal vector computation in large data sets. In VLDB '05:
Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), (pp. 229-240).