Jump label

Service navigation

Main navigation

You are here:

Main content

Parallel Computation of Skyline Queries

Publication Details

Title

Parallel Computation of Skyline Queries

Authors

Louis Woods, Gustavo Alonso, and Jens Teubner

Published

Proceedings of the 21st Int'l Symposium on Field-Programmable Custom Computing Machines (FCCM)

Download

paper (PDF)

Abstract

Due to stagnant clock speeds and high power consumption of commodity microprocessors, database vendors have started to explore massively parallel co-processors such as FPGAs to further increase performance. A typical approach is to push simple but compute-intensive operations (e.g., pre-filtering, (de)compression) to FPGAs for acceleration. In this paper, we show how a significantly more complex operation—the computation of the skyline—can be holistically implemented on an FPGA. A skyline query computes the pareto optimal set of multi-dimensional data points. These queries have been studied in software extensively over the last decade but this paper is the first to examine skyline computation in hardware. We propose a methodology that interleaves data storage and computation, allowing multiple operations to be executed on the same working set in parallel, while accounting for all data dependencies. Our experiments show that we achieve very promising results compared to CPU-based solutions.

Publication Log

Marc 2013

camera-ready for FCCM 2013

January 2013

submission to FCCM 2013 (accepted)

September 2012

submission to FPGA 2013 (rejected)

March 2012

submission to (P)VLDB 2012 (rejected)

November 2011

submission to SIGMOD 2012 (rejected)



Sub content

Contact

Prof. Dr. Jens Teubner
Tel.: 0231 755-6481