{"id":"cebceba4-50b1-46ad-a28c-0c5a34f8da71","arxiv_id":"2411.14968","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Parallel skyline computation can be sped up by sharing strong tuples across partitions and replacing the final sequential cleanup with a parallel pass.","lead":"This paper tests two tricks for speeding up skyline searches, which find the best options in a dataset, on parallel computers. One trick shares strong candidate values across partitions; the other parallelizes the final cleanup step that other methods run one at a time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sliced+NoSeq correctness hinges on an unspecified, dominance-consistent total ordering; an allowed tie-breaking can make the final parallel phase return dominated tuples.","rationale":"The paper's core theoretical identity (Proposition 2) is mathematically sound: if pdi contains a dominator for every globally dominated tuple in ui, the parallel relative-skyline computation returns exactly Sky(r). The load-bearing step is thus condition (2). For Random/Angular, pdi = u \\ ui trivially satisfies it. For Sliced, however, condition (2) follows only if the partition order is a topological sort with respect to dominance: whenever s dominates t, s must appear before t, and thus in an earlier partition. Sorting by a single attribute and adding an arbitrary tie-breaker does not guarantee this. The paper states 'possibly with a tie-breaking criterion' but never specifies a dominance-preserving rule. Under a permitted tie-break the method can return dominated tuples, as the concrete counterexample shows. This is a correctness gap, not merely a missing experimental parameter. The reader's weakest_assumption correctly flagged the unspecified Sliced sort attribute, but treated it as a performance or reproducibility concern; our analysis shows it can invalidate the algorithm's output. Secondary: the Grid variant in §4.2 has an independent flaw—Definition 5's 'at least one inequality is not strict' excludes strict grid dominance (ci=[0,0], ch=[1,1] is not weakly dominating even though every tuple in ci dominates every tuple in ch), so the stated pdi for Grid can omit true dominators. This does not affect the Sliced-based experiments but undermines the claimed general applicability. Because both issues are correctable by specifying a monotone tie-breaker or fixing Definition 5, the conditional verdict stands; the authors must state the exact ordering used and prove or witness the topological property.","tokens_in":13248,"tokens_out":14074,"duration_ms":130744,"concrete_test":"Run the counterexample from §4.2's Sliced definition: dataset {(4,100),(5,10),(5,5),(6,1)}, d=2, p=2, sort key A1 ascending with tie-break A2 descending. Compute SFS local skylines per partition and NoSeq with pdi = {uj | j < i}. If the output contains (5,10), Proposition 2 fails as stated; then re-run with a monotone tie-breaker (e.g., A2 ascending) and verify the output is {(4,100),(5,5),(6,1)}. Additionally request the exact sort attribute and tie-breaking used in §5 experiments and verify it satisfies: whenever s ≺ t, s precedes t in the ordering; if not, the reported skylines are suspect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 2 is correct conditional on condition (2), but the paper never establishes (2) for its main experimental configuration. In §3.4, Sliced sorts by one chosen dimension 'possibly with the addition of a tie-breaking criterion to obtain a total ordering.' No tie-breaker is specified, and not every total order is a topological sort with respect to dominance. If s ≺ t and s[1] = t[1], an arbitrary tie-breaker may place t before s. Then the partition index j of s can exceed i of t, so pdi = {uj | j < i} (§4.2) omits the actual dominator and condition (2) fails. Concretely, with tuples u=(4,100), t=(5,10), s=(5,5), and v=(6,1), p=2, sorting by A1 ascending and tie-break A2 descending yields order u, t, s, v; partition 1 = {u, t} and partition 2 = {s, v}. NoSeq returns {u, t, s, v} instead of Sky = {u, s, v}. Since Algorithm 1 (SFS) also relies on the topological property, even the local skylines can be wrong under such an order. The paper's experimental results therefore rest on an unstated assumption that the chosen sort attribute and tie-breaking are dominance-consistent; without specifying them, the central claim is not guaranteed by the text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper surveys partitioning strategies for parallel skyline computation (Random, Grid, Angular, and a new Sliced scheme) and proposes two orthogonal optimizations: Representative Filtering, which shares a small set of strong tuples across partitions to prune dominated tuples early, and NoSeq, which replaces the final sequential skyline pass with a second parallel phase. The authors prove two elementary propositions (Proposition 1: skyline of union equals skyline of union of local skylines; Proposition 2: the relative-skyline identity that justifies NoSeq) and report a PySpark experimental study on synthetic and real datasets, concluding that Sliced and Angular with the proposed optimizations outperform Random and Grid, and that NoSeq is usually the fastest configuration.","tokens_in":13506,"tokens_out":7037,"duration_ms":64603,"significance":"If the results hold, the paper makes a useful practical contribution: NoSeq removes the sequential bottleneck that limits standard two-phase parallel skyline algorithms, and Sliced is a simple, effective partitioning method. The theoretical propositions are correct and elementary, and the experimental comparison covers a wide parameter space. However, the central correctness claim for Sliced+NoSeq depends on an unstated tie-breaking assumption in the sorting step, and key experimental parameters are left unspecified, so the reproducibility and the strength of the empirical conclusions are currently limited. The paper also ships no code or data, which further reduces the immediate utility of the experimental claims.","major_comments":[{"comment":"The correctness of Sliced Partitioning and of the NoSeq identity for Sliced depends on the sorted order being a topological sort with respect to dominance: if s ≺ t, then s must appear before t. The paper only says that the dataset is sorted by one chosen dimension 'possibly with the addition of a tie-breaking criterion to obtain a total ordering', which is not enough. An arbitrary tie-break can violate the topological property and make both SFS and the final parallel phase return dominated tuples. For example, with tuples u=(4,100), t=(5,10), s=(5,5), v=(6,1) and p=2, sorting by A1 ascending and breaking ties by A2 descending yields order u,t,s,v and partitions {u,t} and {s,v}; then t is dominated by s but is processed first, so SFS on the first partition returns {u,t,s} instead of {u,s}, and NoSeq returns {u,t,s,v} instead of the true skyline {u,s,v}. The paper never states the tie-breaking rule used in the experiments, so the text as written does not establish that Sliced and Sliced+NoSeq compute Sky(r) correctly. The fix is to require a dominance-consistent total order (e.g., full lexicographic order on all attributes, or sorting by any monotone scoring function) and to specify the choice in the experimental configuration.","section":"§3.4, §4.2"},{"comment":"The experimental section does not report several parameters that directly determine the results: the number of representative tuples used by Representative Filtering, the sort attribute (and tie-breaking rule) for Sliced, and the default values that Table 1 promises in bold (no bold values appear in the rendered table). Without these, the efficiency numbers cannot be reproduced, and the comparison between Sorted and Region filtering in Figure 3 cannot be independently checked. Please provide a complete configuration table with explicit default values and state the number of representatives and the Sliced sort specification.","section":"§5.2, Table 1"},{"comment":"The conclusion that both optimization strategies are 'always beneficial, with any number of partitions and cores' is too strong and is contradicted by the paper's own data. In the 'Varying number of partitions' experiment, the text states that NoSeq shows degraded performance as p becomes large (e.g., 164,183 local-skyline tuples at p=3600 vs. 27,328 at p=120), and Figure 7a exhibits this degradation. Also, on the RES dataset (Figure 6c), Angular+ outperforms Sliced+, so the claim of uniform benefit needs to be restricted to the tested configurations and to the comparison of each optimization against its plain baseline (Sliced+ vs. Sliced, Angular+ vs. Angular), not as an absolute statement across all strategies and parameters.","section":"§5 (Varying number of partitions), Conclusion"},{"comment":"All efficiency plots report a single run per configuration with no error bars, variance, or statistical significance. Since the experiments run on a Spark cluster of virtual machines, scheduling and network variability are expected to cause measurable run-to-run differences. Without repeated runs (or at least reporting mean and standard deviation over a few runs), the performance ordering among Sliced+, Angular+, and NoSeq could be within noise. Please add variance information or justify why single runs are representative.","section":"§5.2, Figures 4–7"}],"minor_comments":[{"comment":"The formula p(t) = floor((i-1)*p/(N-1)) appears to be off by one: for N=4 and p=2 it yields indices 0, 0, 1, 2, i.e., three distinct partitions instead of two. The intended formula is probably floor((i-1)*p/N) or the range of the index should be clarified.","section":"§3.4"},{"comment":"In Proposition 2, pdi is defined as a subset of u \\ ui, i.e., a set of tuples, but for Grid and Sliced it is written as a set of local skylines {uj | ...}. This is a type inconsistency; the text should say pdi = ⋃_{j in ...} uj (or use a notation that distinguishes indices from tuple sets).","section":"§4.2"},{"comment":"The Region strategy for representative selection requires normalized data, and the paper says 'in the following we shall always implicitly refer to the [0,1] domain', but it is not stated whether the real datasets (HOU, RES) were normalized before applying Region or any other strategy that uses the dominance-region volume. Please clarify.","section":"§4.1"},{"comment":"The sentence 'Figure 4c shows ... on other synthetic dataset types is available in [8–10]' appears to be a truncated fragment; please rewrite it to specify where the additional results are reported.","section":"§5.2"},{"comment":"The abbreviation NoSeq is never expanded at first use; consider defining it as 'no sequential phase'. Also, the paper would benefit from a short statement about code/data availability, since none is currently provided.","section":"Throughout"},{"comment":"References [8], [9], and [10] are master's theses that are not publicly identified by URL or repository; if they are meant to support the 'fuller account' of experiments, please make them accessible or summarize the relevant results in the paper.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a database systems journal and the core algorithmic idea (parallelizing the final skyline phase) is publishable if the correctness condition is clearly stated and the experimental configuration is fully specified. The main risk is the unstated tie-breaking assumption in Sliced, which, if left as is, invalidates the correctness claims. The self-citations are numerous but do not appear to load-bear. I recommend major revision, not rejection, because the error is fixable within the paper's scope and the experimental claims are otherwise plausible. Please also ask the authors to report variance and to soften the 'always beneficial' claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. First, the core algorithmic idea is sound: Proposition 2 correctly identifies when the final skyline cleanup can be parallelized, and the experimental sweep is the first real implementation of Representative Filtering and of a fully parallel NoSeq over local skylines. Second, the paper's main correctness claim for Sliced partitioning is underspecified: the tie-breaking rule for the one-dimensional sort is never given, and not every total order is dominance-consistent. The stress-test example is real—with an allowed tie-break, NoSeq returns a dominated tuple. That is a fixable but load-bearing omission.\n\nWhat's new: Sliced partitioning (sort by one attribute, divide into equi-sized ranges) is simple and demonstrably strong on anti-correlated data. The two optimizations are orthogonal to the partitioning scheme, and the experimental matrix (size, dimensions, partitions, cores, two real datasets) is unusually broad. Propositions 1 and 2 are elementary and correct. The paper is honest about the RES dataset where Angular+ beats Sliced+, and about NoSeq degrading at very large partition counts.\n\nSoft spots, in proportion. The missing tie-breaker is the main one: for SFS to work on a pre-sorted relation, the order must be a topological sort with respect to dominance; sorting on one attribute with arbitrary tie-break does not guarantee that, and then condition (2) of Proposition 2 fails. The paper should either specify a dominance-consistent tie-breaker (e.g., lexicographic on all attributes) or restrict the claim. The reader's other complaints are real but less severe: no code/data, no error bars, and key parameters (representative count, chosen sort attribute) are not reported, so the performance numbers are not reproducible as published. The 'always beneficial' language is a bit loose but the conclusion itself carries the necessary qualification.\n\nVerdict: this is a legitimate systems paper, not a conceptual breakthrough. With the tie-breaker fixed and configuration details added, it would be a solid contribution to the parallel skyline literature. It deserves a serious referee; the correctness gap is exactly what peer review should catch.","headline":"Sound and useful experimental paper on parallel skyline optimization, but the NoSeq correctness claim for Sliced partitioning rests on an unspecified tie-breaking rule that can break the algorithm.","tokens_in":13980,"tokens_out":4881,"would_cite":true,"duration_ms":45173,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Two orthogonal optimizations for parallel skyline computation: representative filtering and a parallel final phase.","keywords":["skyline queries","parallel computation","PySpark","partitioning strategies","representative filtering","NoSeq","dominance","multi-core"],"falsifier":"Take an anticorrelated dataset with high dimensionality, set the number of partitions $p$ much larger than the number of cores (for example $p = 20c$), and compare NoSeq against Sliced with representative filtering: if NoSeq is not faster, or if the broadcast and checking time for the union $u$ exceeds the sequential final-pass time, the practical claim fails. A more direct check is to measure $|u|/|r|$: if the local skylines occupy a large fraction of the dataset, NoSeq's overhead should dominate.","tokens_in":1704,"feed_emoji":"⚡","tokens_out":8266,"duration_ms":97996,"temperature":0.7,"pith_summary":"This paper tries to establish that the standard two-phase scheme for parallel skyline computation—local skylines per partition, then a final global pass—can be improved by two orthogonal optimizations, and that the supposedly sequential final phase can itself be parallelized. The key is a relative-skyline identity: if each partition's local skyline is re-checked against only its potential dominators among the other local skylines, the union of those re-checked results is exactly the global skyline. The authors propose Sliced partitioning, show that representative filtering nearly always helps, and report experiments where NoSeq, the parallel-cleanup scheme, is fastest except when the number of partitions far exceeds the number of cores. A sympathetic reader would care because skyline computation is quadratic in the worst case, so removing a sequential bottleneck is exactly the step that makes distributed skyline computation scale.","feed_headline":"Skyline queries lose their final sequential pass.","feed_subtitle":"A relative-skyline identity lets each compute node prune its own local skyline, removing the dominant bottleneck.","key_machinery":"The workhorse is the relative skyline $\\mathrm{Sky}_c(r)$, defined as the tuples in $r$ not dominated by any tuple in $c$. Proposition 2's identity is the mechanism: it decomposes the global skyline into relative skylines computed per partition with respect to potential-dominator sets $\\mathit{pd}_i$. For Sliced partitioning, tuples are assigned to partitions by sorting on one attribute, so $\\mathit{pd}_i=\\{u_j\\mid j<i\\}$; for Grid, weak grid dominance among cells gives $\\mathit{pd}_i$; for Random and Angular, $\\mathit{pd}_i=u\\setminus u_i$. This identity is what lets the final sequential phase of Algorithm 2 be replaced by parallel relative-skyline computations.","core_discovery":"The central claim is Proposition 2: with a relation $r$ partitioned into $r_1,\\dots,r_p$, local skylines $u_i=\\mathrm{Sky}(r_i)$, and $u$ their union, if for each $i$ the set $\\mathit{pd}_i\\subseteq u\\setminus u_i$ contains every tuple that can dominate a non-skyline tuple of $u_i$, then $\\mathrm{Sky}(r)=\\mathrm{Sky}_{\\mathit{pd}_1}(u_1)\\cup\\dots\\cup\\mathrm{Sky}_{\\mathit{pd}_p}(u_p)$. This identity turns the final cleanup of Algorithm 2 into another parallel phase: each node keeps only the tuples of its local skyline not dominated by $\\mathit{pd}_i$. For Grid and Sliced partitioning, $\\mathit{pd}_i$ is much smaller than $u$ because the partitioning induces a weak dominance order; for Random and Angular one must use $\\mathit{pd}_i=u\\setminus u_i$. The paper also reports experiments on synthetic and real datasets in a 120-core PySpark cluster showing that Sliced partitioning with NoSeq is the fastest configuration in most scenarios, and that representative filtering helps with every partitioning strategy.","pith_inferences":["Since Proposition 2 does not dictate how $\\mathit{pd}_i$ must be chosen, an adaptive implementation could select per-partition potential dominators based on data statistics, possibly shrinking the broadcast even further than the paper's fixed choices.","Because representative filtering and NoSeq are described as orthogonal, combining both is a direct testable extension; the paper evaluates them separately, so stacking them should give at least the benefit of either alone.","The relative-skyline formulation suggests a streaming or incremental variant: as new partitions arrive, only the affected $\\mathit{pd}_i$ sets need re-checking instead of recomputing the global skyline from scratch.","The paper does not report the Sliced sort attribute or the exact number of representatives used, so a natural test is to vary those choices and check whether the qualitative ranking among Sliced+, Angular+, and NoSeq survives."],"forward_implications":["The final phase of Algorithm 2 ceases to be a sequential bottleneck: each node can prune its own local skyline in parallel once it receives the potential-dominator sets.","For Sliced and Grid partitioning, the potential-dominator sets are much smaller than the full union of local skylines, so NoSeq's communication cost is bounded by the partition structure rather than the whole dataset.","Representative filtering is reported to reduce execution time for every partitioning strategy and dataset tested, with Sorted representatives preferable on anticorrelated data and Region on uniform and correlated data.","NoSeq on Sliced is the recommended configuration unless the number of partitions greatly exceeds the number of cores, in which case Sliced or Angular with representative filtering is the preferred alternative.","Because higher dimensionality yields larger skylines, NoSeq remains the most efficient option there, since the union of local skylines stays manageable enough to broadcast to all nodes."],"supporting_citations":[{"why":"Defines the skyline operator and dominance, the object that all of the paper's algorithms compute.","marker":"[2]"},{"why":"Supplies the Sort Filter Skyline algorithm, used as the sequential local skyline method inside the parallel pattern.","marker":"[4]"},{"why":"Provides the Random partitioning baseline against which the improved strategies are compared.","marker":"[5]"},{"why":"Supplies the MapReduce grid-based skyline method that partially inspired NoSeq and provides the grid-dominance machinery.","marker":"[6]"},{"why":"Provides angle-based space partitioning, one of the surveyed and experimentally compared partitioning strategies.","marker":"[7]"},{"why":"Proposed an early distributed representative-filtering idea that the paper adapts as Representative Filtering.","marker":"[23]"}],"fun_headline_variants":["Skyline's sequential bottleneck bypassed","Parallel skyline: final prune goes local","Skyline final pass parallelized with tiny dominator sets","Divide-and-conquer skyline: final step now parallel"],"cache_read_input_tokens":16128,"weakest_assumption_plain":"The load-bearing premise is that the union $u$ of local skylines is small enough that sending it to every node and running the parallel relative-skyline checks costs less than one sequential scan of $u$; the paper's own partition-count experiments show this premise fails when $p$ grows too large.","fun_headline_variants_meta":{"raw":{"variants":["Skyline's sequential bottleneck bypassed","Parallel skyline: final prune goes local","Skyline final pass parallelized with tiny dominator sets","Divide-and-conquer skyline: final step now parallel"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000881,"raw_usage":{"total_tokens":3789,"prompt_tokens":908,"completion_tokens":2881,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":2830}},"tokens_in":524,"tokens_out":2881,"duration_ms":21701,"temperature":1.0,"reasoning_tokens":2830,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:39:11.297304+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an anticorrelated dataset with high dimensionality, set the number of partitions $p$ much larger than the number of cores (for example $p = 20c$), and compare NoSeq against Sliced with representative filtering: if NoSeq is not faster, or if the broadcast and checking time for the union $u$ exceeds the sequential final-pass time, the practical claim fails. A more direct check is to measure $|u|/|r|$: if the local skylines occupy a large fraction of the dataset, NoSeq's overhead should dominate.","supporting_citations":[{"cited_title":"In: 21st Annual International Symposium on High Performance Com- puting Systems and Applications (HPCS 2007), 13-16 May 2007, Saskatoon, Saskatchewan, Canada, p","cited_arxiv_id":null,"evidence_quote":"Provides the Random partitioning baseline against which the improved strategies are compared."},{"cited_title":"In: Antonellis, V.D., Diamantini, C., Tiberio, P","cited_arxiv_id":null,"evidence_quote":"Proposed an early distributed representative-filtering idea that the paper adapts as Representative Filtering."}],"review_version":1}