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
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)
- submission (PDF)
- reviews (results: 5, 5, 5, 5)
September 2012
submission to FPGA 2013 (rejected)
- submission (PDF)
- reviews (results: 5, 5, 5, 5)
March 2012
submission to (P)VLDB 2012 (rejected)
- submission (PDF)
- reviews (results: Weak Accept, Weak Reject, Weak Reject)
November 2011
submission to SIGMOD 2012 (rejected)
- submission (PDF)
- reviews (results: Weak accept, Reject, Weak accept)