A study on external memory scan-based skyline algorithms

Bikakis, N, Sacharidis, D and Sellis, T 2014, 'A study on external memory scan-based skyline algorithms', in Decker, H., Lhotská, L., Link, S., Spies, M., Wagner, R.R. (ed.) Proceedings of the 25sth International Conference, Database and Expert Systems Applications (DEXA 2014) Part I [LNCS 8644], Munich, Germany, 1-4 September 2014, pp. 156-170.


Document type: Conference Paper
Collection: Conference Papers

Title A study on external memory scan-based skyline algorithms
Author(s) Bikakis, N
Sacharidis, D
Sellis, T
Year 2014
Conference name DEXA 2014
Conference location Munich, Germany
Conference dates 1-4 September 2014
Proceedings title Proceedings of the 25sth International Conference, Database and Expert Systems Applications (DEXA 2014) Part I [LNCS 8644]
Editor(s) Decker, H., Lhotská, L., Link, S., Spies, M., Wagner, R.R.
Publisher Springer
Place of publication Germany
Start page 156
End page 170
Total pages 15
Abstract Skyline queries return the set of non-dominated tuples, where a tuple is dominated if there exists another with better values on all attributes. In the past few years the problem has been studied extensively, and a great number of external memory algorithms have been proposed. We thoroughly study the most important scan-based methods, which perform a number of passes over the database in order to extract the skyline. Although these algorithms are specifically designed to operate in external memory, there are many implementation details which are neglected, as well as several design choices resulting in different flavors for these basic methods. We perform an extensive experimental evaluation using real and synthetic data. We conclude that specific design choices can have a significant impact on performance. We also demonstrate that, contrary to common belief, simpler skyline algorithm can be much faster than methods based on pre-processing.
Subjects Database Management
Keyword(s) Experimental evaluation
experimental survey
disk-based algorithm
DOI - identifier 10.1007/978-3-319-10073-9
Copyright notice © 2014 Springer-Verlag
ISBN 9783319100722
Versions
Version Filter Type
Altmetric details:
Access Statistics: 129 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Apr 2015, 11:43:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us