Reviews for paper Parallel Computation of Skyline Queries, submitted to SIGMOD 2012.
Overall rating: reject
The paper presents an FPGA implementation of a skyline operator using a new abstraction called "shifter lists". Shifter lists utilize pipelined parallelism to provide a scalable locality-preserving chain of hardware operators.
S1. The implementation of the skyline operator on a real device is convincing (although see W1 below).
S2. The use of hardware acceleration is an important trend, and this kind of work is very relevant.
S3. The presentation is very good. The Lemmings example is nice.
W1. It is unclear whether the software implementation used common optimization tricks that can sometimes yield significant performance improvements. In particular, did the software implementations use SIMD (i.e., SSE) instructions, and did it try to avoid conditional branches in the inner loop?
W2. While the skyline implementation is impressive, the authors also claim that the proposed abstraction of shifter lists has wider applicability. Unfortunately, no support for this claim is presented. It would be nice to have seen 2 or 3 other kinds of algorithm that map well to the abstraction. Otherwise, this might be a one-off design.
High
High
Satisfactory
D1. It would be interesting to see how sensitive the software implementation is to whether the working set fits in the L1/L2/L3 cache memories.
Weak accept
This paper proposes a highly parallel, pipelined processing approach claimed to simplify the general problem of extracting parallelism from data processing.
S1. The proposed technique utilizes parallelism effectively, with demonstrated scalability limited only by chip real estate and memory bandwidth.
S2. The lemming example is clever and explains clearly how the algorithms work.
W1. The concept of shifter lists is virtually identical to, but does not cite, the "Soccer Join" proposed by Teubner and Muller in SIGMOD'11. The primary (and rather minor) difference that the latter was presented in the context of streaming joins rather than skyline joins. Author feedback notwithstanding, the work does not distinguish itself from prior approaches that accelerate joins.
W2. Shifter lists are useful only when the amount of computation per element is high (e.g. skyline computations are essentially nested loop joins having quadratic complexity), work per item is both small and uniform (e.g. skyline computations), and where the communication patterns can easily be made point-to-point (i.e. map/reduce problems are unlikely to work well). These limitations cast doubt on the claim that shifter lists are a general-purpose panacea for parallel data processing.
Low
Medium
Satisfactory
D1. The repeated claim of general applicability is unfounded. There is no discussion of algorithms/operators (other than joins) which would benefit. Further, the discussion surrounding Figure 12 claims that the automaton's structure is mostly determined by the fact that it is a shifter list node, but everything about it is presented in terms of the skyline query.
D2. Teubner's SIGMOD'11 paper provides essentially the same algorithm, right down to the bidirectional asynchronous FIFO queues that pass both data and control messages between neighbors in a chain of nodes (and both process joins). If anything, Teubner's paper makes this one easier to understand, as the implementation details given here are scanty.
D3. I'm still not convinced of the authors' argument (in feedback) that shifter lists are more expressive or general than soccer/handshake join is. AFAICT, the only real difference is setting, rather than algorithm: shifter lists (= skyline queries), handshake joins (SIGMOD'11), cyclo-joins (ICDCS'10), and complex event detection (VLDB'10), all target situations with O(n^2) work to be done -- namely nested loop joins -- and all propose essentially the same variant of block-nested-loops join (with windowing thrown in for good measure in some cases). In fact, cyclo-joins and handshake joins were developed by the same people (ETH + CWI), and they openly admit that the two papers apply the same principle in different settings. I would argue that all such techniques are equivalent, and that it's equally hard to generalize *any* of them to operators like non-nested-loops joins, sorting, or aggregation.
D4. It strikes me as somewhat disingenuous to dismiss previous join-related techniques by associating them with QPipe (again, in feedback), because the latter targets inter-operator parallelism and is therefore orthogonal to a discussion about intra-operator parallelism. I would be very surprised if shifter lists can express what QPipe does, and QPipe does not pretend to optimize parallelism within joins or any other operator.
D5. The authors should implement their suggestion from feedback, to express various existing ideas in terms of shifter lists. This would both serve to differentiate from prior work (if the techniques are indeed different) while bolstering the claim of general applicability.
Reject
The authors present a data structure called shifter lists which build an abstraction level to easily support general data processing on modern parallel hardware in a scalable way. They demonstrate the functionality of shifter lists using skyline calculation (block nested loops with shifter lists) and implement the algorithm on FPGAs. In the experiments section the authors analyze the effects of FPGA versus software implementation on different data sets and the effects of the chosen window size on the required number of comparisons (i.e., the performance).
* well written
* relevant topic in two architectures:
+ FPGA as well as
+ multi-core
* experiments are interesting; however, i'm not sure about the comparison of single-fast-core to multiple-slow-cores
* I missed a discussion of the (in my opinion very related) paper on soccer joins:
Jens Teubner, René Müller: How soccer players would do stream joins. SIGMOD Conference 2011: 625-636
The basic idea of moving two streams of objects in opposite directions through processing units is very similar. Maybe the lack of discussing this related paper is an artefact of double blind reviewing.
* The new algorithm shows its strength mainly in high-dimensional cases where the result set of skyline is very large -- and, arguably, also of limited value.
Medium
High
Satisfactory
* To me the main aspect of shifter lists as a general way to parallelize algorithms would possibly have been more clear with a second example (e.g., top-k) provided in the appendix
Minor issues:
* check for singular/plural mistakes again (e.g., Introduction "... is to build specialized algorithm implementations that addresses modern ...", 2.2 "... is probably the most prominent example of a commercial FPGA-powered database appliances")
Weak accept