{"id":"d7626821-809b-4e88-a361-09783e8f6263","arxiv_id":"2412.02274","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Known parallel skyline partitioning strategies can be adapted to compute grid resistance, with Sliced partitioning giving the most stable speedups across datasets.","lead":"This paper adapts existing parallel partitioning methods for skyline queries to compute grid resistance, a robustness score for skyline tuples. Experiments on synthetic and real datasets show partitioning can speed up the computation on large, challenging datasets, with the Sliced strategy being the most consistent.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The experiments replace the exact stopping bound in Algorithm 1 with an arbitrary threshold (g-bar=25), so the measured variant is not necessarily gres from Definition 2; any tuple that leaves the skyline only at g>25 is mislabeled as perfectly robust, and the speedups may not transfer to the…","rationale":"I agree with the reader's CONDITIONAL overall assessment, but I do not think the stability property is the weakest load-bearing point: it is actually provable from monotonicity of the floor projection, and the paper's omission is only a missing proof. The more serious issue is that the experiments deliberately compute a truncated version of gres with g-bar=25, while the abstract, introduction, and conclusion present the work as computing grid resistance. This matters because the exact bound can be impractically large, and the paper gives no evidence that 25 is a faithful proxy for the exact indicator on the tested datasets. If tuples with true gres below 1/25 are common, then a substantial part of the computed values are wrong, and the reported dominance-test reductions and speedups describe a different, easier problem. The reader flagged this as issue (3), so our views partially overlap, but I would place it at the center rather than the stability proof. The concrete test is a sensitivity analysis over g-bar; without it, the central claim that parallelization is useful for computing gres is not fully supported. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":14036,"tokens_out":10965,"duration_ms":117319,"concrete_test":"Rerun the experimental protocol on the RES and SEN datasets with g-bar in {25, 100, 1000} and, where feasible, with the exact l-derived bound, reporting per-tuple gres values as well as dominance-test counts and timings. If a material fraction of skyline tuples change value, or if the relative ranking of Grid, Angular, and Sliced shifts, the headline results are an artifact of the truncation rather than properties of exact gres computation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim concerns the computation of gres, but Section 4 replaces the exact stopping bound of Algorithm 1, namely g-bar = floor(l^{-1}) where l is the smallest non-zero attribute difference, with a hand-chosen threshold g-bar = 25 ('we simply set g-bar = 25'). Consequently, the evaluated algorithm is not the one defined in Section 3: a skyline tuple that first exits the skyline at some g > 25 is assigned gres = 1 by line 8, even though its true grid resistance may be, say, 1/1000. The dominance-test counts and the reported >50% speedups are therefore for a truncated variant of gres whose fidelity to Definition 2 is unknown and dataset-dependent. Because the algorithm's cost grows linearly with g-bar, a dataset with a very small smallest difference l could require a huge number of skyline computations for exact gres, potentially making the parallelization benefits irrelevant to the actual indicator. The paper provides no sensitivity analysis over g-bar and no comparison between the truncated values and exact gres values, so the reader cannot tell whether the strategy rankings and timing improvements transfer to the real indicator. The stability property asserted in Section 3.2 is actually true, since monotonicity of the floor projection guarantees that if a dominated tuple's projection dominates t's projection, some skyline tuple's projection does too; however, the paper omits the proof, which is a rigor gap but not the main risk.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parallel computation of grid resistance (gres), a robustness indicator for skyline tuples defined in prior work [2]. It adapts three partitioning strategies (Grid, Angular, Sliced) and a representative-filtering optimization to an algorithmic pattern (Algorithm 1) that computes gres by repeatedly evaluating skylines of grid-projected datasets. Experiments on synthetic (ANT, UNI) and real (NBA, HOU, EMP, RES, SEN) datasets count dominance tests and measure wall-clock times as dataset size, dimensionality, number of partitions, representatives, and cores vary. The main conclusions are that partitioning can reduce dominance tests and execution time by over 50% on challenging datasets, Sliced gives the most stable speedups, and Representative Filtering is ineffective.","tokens_in":14253,"tokens_out":4421,"duration_ms":43316,"significance":"If the results transfer to the exact grid-resistance indicator, the paper provides a useful practical recipe for ranking skyline tuples in large datasets, an area with few existing algorithmic studies. The experimental methodology is transparent: dominance-test counts are hardware-independent, multiple synthetic and real datasets are used, and no fitted parameters are involved. The paper also correctly identifies that the stability of gres allows restricting computation to skyline tuples, although this property is not proved. The main caveat is that the experiments evaluate a truncated variant of gres (g-bar=25), so the central claim must be qualified until sensitivity to the threshold and fidelity to Definition 2 are demonstrated.","major_comments":[{"comment":"The experiments replace the exact stopping bound of Algorithm 1 (g-bar = floor(l^{-1}), line 2) with an arbitrary threshold g-bar = 25. The measured algorithm therefore computes a truncated version of gres: any skyline tuple that remains in the skyline for all g in {25,...,2} is assigned gres = 1 (line 8), although Definition 2 would give a lower value if it exits at some g > 25. Because the number of iterations is proportional to g-bar, the reported dominance-test counts and speedups may not transfer to exact gres computation, particularly for datasets with very small minimum attribute differences. The paper does not provide a sensitivity analysis over g-bar nor a comparison between truncated and exact gres values; such an analysis is necessary to support the claim that the parallelization strategies benefit the actual indicator.","section":"Section 4 (paragraph starting 'Before starting the experiments') and Algorithm 1"},{"comment":"The assertion that 'the gres operator is stable, i.e., it does not depend on dominated tuples' is stated without proof. Algorithm 1 relies on this property to restrict the input to Sky(r), so a proof is load-bearing. The property is in fact true: because floor projection is monotone with respect to dominance and dominance is transitive, if a dominated tuple u's projection dominates t's projection, then some skyline tuple v that dominates u has gproj(v, g) dominating gproj(u, g), hence also t's projection. This argument should be included explicitly. Without it, the correctness of the algorithmic pattern is incomplete.","section":"Section 3.2 (paragraph 'Finding gres requires...')"}],"minor_comments":[{"comment":"The input/output contract is inconsistent: the input is named 'skylines' but the output map is defined over 'every tuple t in s' and lines 5-8 iterate over s, which is never introduced; this must be fixed for reproducibility. Also, the comment on line 2 says 'where l is the minimum possible value for gres', but l was defined earlier as the smallest non-zero attribute difference.","section":"Algorithm 1"},{"comment":"The caption says 'default number of representatives (rep = 16)', but the default for rep in Table 1 is 0; the caption should read rep = 0.","section":"Figure 5 caption"},{"comment":"The phrase 'a smaller average number of actually non-dominates tuples' should be 'a smaller average number of actually non-dominated tuples'.","section":"Section 4, paragraph 'Varying the number of representatives'"},{"comment":"The phrase 'the are ultimately required' contains a typo and should read 'they are ultimately required'.","section":"Section 6, first paragraph"},{"comment":"The manuscript would benefit from a more explicit statement of the novel contribution relative to the author's prior work [2] and [3], since Algorithm 1 is a direct adaptation of the pattern from those papers.","section":"Section 5, Related Work"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a single-author extension of the author's prior work [2,3], and the novel element is the experimental evaluation of partitioning strategies for gres. The g-bar truncation is the main risk: the central experimental claim is about a variant of the indicator, not Definition 2. I recommend requesting a sensitivity analysis over g-bar and, if possible, a comparison with exact gres values on smaller datasets, before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper adapts three known parallel skyline partitioning strategies (Grid, Angular, Sliced) and Representative Filtering to the computation of grid resistance, an indicator from the author's prior work. The genuinely new part is the experimental study: this is the first time these strategies have been evaluated for gres, and the finding that partitioning pays off on challenging datasets, with Sliced the most stable, is credible from the dominance-test counts and timing runs. The paper is honestly scoped as an experimental study, not a theory contribution.\n\nThe main soft spot is the threshold g-bar = 25. The paper replaces the exact stopping bound from Algorithm 1 with this hand-picked value, so what is measured is a truncated variant of gres, not Definition 2. Any tuple whose true grid resistance is below 1/25 is mislabeled as perfectly robust (gres = 1). That means the reported speedups and strategy rankings apply to the truncated variant; whether they transfer to the exact indicator is unknown. The paper needs a sensitivity analysis over g-bar and, ideally, a comparison with exact values on small instances.\n\nA second issue: the stability of gres is stated without proof in Section 3.2. The property is actually true—monotonicity of the floor projection means any dominator of a tuple's projection can be replaced by a skyline tuple whose projection still dominates—but the paper should prove it or at least sketch it, since the entire reduction to skyline input rests on it.\n\nMinor but real: Algorithm 1 has an input/output variable mismatch (the input lists 'skylines' but the loop uses 's' and calls Sky(gproj(r,g)) without passing r). The experiments report averages over five instances without error bars, and no code or data are released, which weakens reproducibility. These are fixable in revision.\n\nOverall, this is a solid incremental contribution for the skyline-computation community. It deserves serious peer review, but the g-bar issue and the missing proof should be resolved before the central claim about parallelizing gres can be taken at face value.","headline":"A useful but narrow experimental study of parallelizing grid resistance; the measured variant uses a hand-picked g-bar=25, and the stability claim is asserted without proof, so treat the central claim as conditional.","tokens_in":14838,"tokens_out":3059,"would_cite":false,"duration_ms":32286,"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":"This paper shows that partitioning strategies built for parallel skyline computation also speed up the computation of grid resistance, a robustness score for skyline tuples, with sliced partitioning the most stable and execution-time…","keywords":["skyline","grid resistance","parallel computation","partitioning","dominance tests","robustness indicator","tuple ranking"],"falsifier":"Run Algorithm 1 on a diverse set of small datasets and compare every reported grid-resistance value against a brute-force computation that keeps all dominated tuples and recomputes the skyline from the full grid-projected relation for every grid size; the first mismatch would show that a dominated tuple's projection can affect the result, refuting the stability premise.","tokens_in":13687,"feed_emoji":"⚡","tokens_out":6396,"duration_ms":64303,"temperature":0.7,"pith_summary":"This paper tackles a practical bottleneck: giving each skyline tuple a numeric strength score, specifically grid resistance, requires repeated skyline computations on grid-projected data. The author adapts three existing parallel partitioning strategies — grid, angle-based, and sliced — to this setting and measures their effect by counting dominance tests and by timing runs on a 16-core machine. The central claim is that parallelization pays off when the dataset is challenging enough, with sliced partitioning giving the most stable improvements and sometimes halving execution time, while representative filtering does not help. A sympathetic reader would care because it turns an indicator that looked inherently sequential into something that can be computed quickly on ordinary hardware.","feed_headline":"Parallel partitioning cuts skyline robustness computations by half","feed_subtitle":"A study adapts three partitioning strategies to grid resistance; sliced partitioning is the most stable win.","key_machinery":"The load-bearing object is Algorithm 1, a pattern that computes grid resistance by looping over grid sizes $g$ from an upper bound $\\bar g$ down to 2, recomputing $\\mathrm{Sky}(\\mathrm{gproj}(r,g))$ at each step, and marking the first $g$ where a skyline tuple's projection exits the skyline. The reduction that makes parallelization possible is the asserted stability of grid resistance: dominated tuples can be discarded, leaving only skyline tuples as input, so the skyline size determines the workload. The three partitioning strategies — grid, angular, and sliced — each split that skyline-sized input across cores, with dominance-test counts used as a hardware-independent cost measure.","core_discovery":"The discovery is that computing grid resistance can follow the same two-phase pattern used for parallel skylines: partition the input, compute local skylines in parallel, then merge and compute the final skyline. The paper asserts that the grid-resistance operator is stable, meaning dominated tuples can be ignored, so the computation can be restricted to the original skyline; for each grid interval the algorithm recomputes the skyline of the grid projections and records the first interval at which a tuple drops out. The experimental comparison shows that no single partitioning strategy wins everywhere, but sliced partitioning is the most consistent, representative filtering is ineffective because skyline tuples are already strong, and on datasets like ANT, SEN, and RES the parallel strategies cut execution time by more than half.","pith_inferences":["Editorial extension: the same dominance-test cost model likely transfers to other dominance-based indicators, such as skyline variants with modified dominance, whenever the indicator can be restricted to skyline tuples.","Editorial extension: because the experiments fix $\\bar g = 25$ rather than using the exact smallest nonzero attribute difference, the reported grid-resistance values are an approximation, and a natural test is to measure how much tuple rankings change under different thresholds.","Editorial extension: the finding that representative filtering fails is specific to inputs that are already skyline tuples; for indicators computed over the full dataset, representative filtering could regain its usual pruning benefit."],"forward_implications":["On challenging inputs such as the ANT synthetic dataset and the RES and SEN real datasets, adopting any of the three partitioning strategies can cut the execution time of grid-resistance computation by more than 50% with 16 cores.","Sliced partitioning delivers the most stable relative gains across synthetic and real datasets, making it the safest default choice.","Representative filtering adds dominance tests without meaningfully shrinking local skylines, so it should be skipped for grid-resistance computation.","The number of dominance tests is a hardware-independent predictor of whether parallelization will help, separate from wall-clock timing.","Over-partitioning raises overhead because the input is already the skyline, so the default of around 16 partitions is near the practical sweet spot."],"supporting_citations":[{"why":"Defines skyline and dominance, and supplies the synthetic dataset generator used in the experiments.","marker":"[1]"},{"why":"Introduces grid resistance and the sequential computation pattern that Algorithm 1 parallelizes.","marker":"[2]"},{"why":"Provides sliced partitioning, representative filtering, and the two-phase parallel scheme the paper adapts.","marker":"[3]"},{"why":"Supplies the grid partitioning strategy and its cell-level dominance pruning.","marker":"[4]"},{"why":"Supplies the angle-based hyper-spherical partitioning used to balance workload across partitions.","marker":"[5]"},{"why":"The presorting skyline algorithm used as the sequential baseline for timing comparisons.","marker":"[9]"}],"fun_headline_variants":["Parallel algorithm halves time for skyline robustness checks","Sliced partitioning speeds up skyline robustness computation","Faster way to compute robustness of skyline tuples","Parallelizing grid resistance: cut skyline strength computations","Skyline robustness computed in parallel with sliced partitioning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a tuple that is already dominated cannot, after its values are snapped to a grid, knock a skyline tuple out of the skyline; the paper relies on this to throw away all non-skyline tuples before starting, but gives no proof.","fun_headline_variants_meta":{"raw":{"variants":["Parallel algorithm halves time for skyline robustness checks","Sliced partitioning speeds up skyline robustness computation","Faster way to compute robustness of skyline tuples","Parallelizing grid resistance: cut skyline strength computations","Skyline robustness computed in parallel with sliced partitioning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00037,"raw_usage":{"total_tokens":1928,"prompt_tokens":838,"completion_tokens":1090,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":1016}},"tokens_in":454,"tokens_out":1090,"duration_ms":8537,"temperature":1.0,"reasoning_tokens":1016,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:39:09.367578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a diverse set of small datasets and compare every reported grid-resistance value against a brute-force computation that keeps all dominated tuples and recomputes the skyline from the full grid-projected relation for every grid size; the first mismatch would show that a dominated tuple's projection can affect the result, refuting the stability premise.","supporting_citations":[{"cited_title":"In: Amer-Yahia, S., Christophides, V., Kementsietsidis, A., Garo- falakis, M.N., Idreos, S., Leroy, V","cited_arxiv_id":null,"evidence_quote":"Supplies the grid partitioning strategy and its cell-level dominance pruning."}],"review_version":1}