REVIEW 2 major objections 5 minor 1 cited by
Parallelizing the Computation of Robustness for Measuring the Strength of Tuples
T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Section 4 (paragraph starting 'Before starting the experiments') and Algorithm 1] 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 3.2 (paragraph 'Finding gres requires...')] 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.
minor comments (5)
- [Algorithm 1] 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.
- [Figure 5 caption] 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 4, paragraph 'Varying the number of representatives'] The phrase 'a smaller average number of actually non-dominates tuples' should be 'a smaller average number of actually non-dominated tuples'.
- [Section 6, first paragraph] The phrase 'the are ultimately required' contains a typo and should read 'they are ultimately required'.
- [Section 5, Related Work] 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.
Circularity Check
No significant circularity: grid resistance is restated from prior work, partitioning algorithms are applied externally, and all performance claims are direct experimental measurements.
full rationale
The paper's only derivation is Algorithm 1, which directly implements Definition 2 by iterating grid sizes and testing membership of grid projections in projected skylines; no fitted parameter is later renamed as a prediction. The partitioning strategies (Grid, Angular, Sliced) and Representative Filtering are taken from prior literature, including two papers by the same author ([3]), but they are used as external building blocks whose behavior is measured in experiments, not as premises that force the conclusions. The self-citation to [2] supplies the gres indicator, but Definition 2 restates it in the paper and no uniqueness or forced-choice claim rests on that citation. The experimental section replaces the exact g-bar bound with a hand-chosen threshold ('we simply set g-bar = 25'), which is an approximation/fidelity issue rather than a circularity; it does not make the speedups equivalent to the input by construction. The asserted stability of gres (Section 3.2) is an unproved lemma, but it is a correctness gap, not a circular step, since the claim is not derived from itself. Overall, the paper is an independent application and measurement study, so the circularity score is 0.
Assumptions & free parameters
free parameters (4)
- maximum grid intervals (g-bar) =
25
- number of partitions (p) =
16 (default); tested 16, 32, 64, 128
- number of representatives (rep) =
tested 0, 1, 10, 100, 1000
- number of cores (c) =
tested 2, 4, 8, 16
assumptions (4)
- standard math Every non-skyline tuple is dominated by at least one skyline tuple.
- ad hoc to paper Dominance is transitive and floor projection is monotone, so if a dominated tuple's projection dominates t's projection, then some skyline tuple's projection does too.
- ad hoc to paper The fixed threshold g-bar = 25 captures the practically significant range of grid sizes.
- domain assumption The number of dominance tests is an objective, hardware-independent measure of computational effort.
Cite this review
Pith. "Pith review of Parallelizing the Computation of Robustness for Measuring the Strength of Tuples." pith.science (2026). https://pith.science/paper/RM33F3RZ
@misc{pith2026241202274,
author = {Pith},
title = {Pith review of: Parallelizing the Computation of Robustness for Measuring the Strength of Tuples},
year = {2026},
howpublished = {\url{https://pith.science/paper/RM33F3RZ}},
note = {Machine review of arXiv:2412.02274}
}
abstract
Several indicators have been recently proposed for measuring various characteristics of the tuples of a dataset -- particularly, the so-called skyline tuples, i.e., those that are not dominated by other tuples. Numeric indicators are very important as they may, e.g., provide an additional criterion to be used to rank skyline tuples and focus on a subset thereof. We concentrate on an indicator of robustness that may be measured for any skyline tuple $t$: grid resistance, i.e., how large value perturbations can be tolerated for $t$ to remain non-dominated (and thus in the skyline). The computation of this indicator typically involves one or more rounds of computation of the skyline itself or, at least, of dominance relationships. Building on recent advances in partitioning strategies allowing a parallel computation of skylines, we discuss how these strategies can be adapted to the computation of the indicator.
Forward citations
Cited by 1 Pith paper
-
Computing the Non-Dominated Flexible Skyline in Vertically Distributed Datasets with No Random Access
An NRA-style algorithm that computes the non-k-dominated flexible skyline in vertically distributed, no-random-access settings, with correctness and instance-optimality proofs.
Reference graph
Works this paper leans on
-
[2]
Ciaccia, P., Martinenghi, D.: Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results. Proc. ACM Manag. Data 2(6) (2024) https://doi.org/10.1145/3698807
doi:10.1145/3698807 2024
-
[1]
B¨ orzs¨ onyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidel- berg, Germany, pp. 421–430 (2001). https://doi.org/10.1109/ICDE.2001.914855 . http://dx.doi.org/10.1109/ICDE.2001.914855
arXiv 2001
-
[3]
https://arxiv.org/abs/2411.14968 14
Ciaccia, P., Martinenghi, D.: Optimization Strategies for Parallel Computation of Skylines (2024). https://arxiv.org/abs/2411.14968 14
arXiv 2024
-
[4]
Mullesgaard, K., Pederseny, J.L., Lu, H., Zhou, Y.: Efficient skyline computation in mapreduce. In: Amer-Yahia, S., Christophides, V., Kementsietsidis, A., Garo- falakis, M.N., Idreos, S., Leroy, V. (eds.) Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014, pp. 37–48 (2014). http...
-
[5]
Vlachou, A., Doulkeridis, C., Kotidis, Y.: Angle-based space partitioning for efficient parallel skyline computation. In: Wang, J.T. (ed.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pp. 227–238 (2008). https: //doi.org/10.1145/1376616.1376642 . https://doi.org/10.1145...
arXiv 2008
-
[6]
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd Edition. MIT Press (2009). http://mitpress.mit.edu/books/ introduction-algorithms
work page 2009
-
[7]
https://data.world/ data-society/employee-compensation-in-sf
San Francisco Open Data: Employee Compensation in SF. https://data.world/ data-society/employee-compensation-in-sf. Last accessed November 23, 2023 (2016)
work page 2016
-
[8]
https://archive.ics.uci.edu/dataset/235/individual+household+electric+power+ consumption
Hebrail, G., Berard, A.: Individual household electric power consumption. https://archive.ics.uci.edu/dataset/235/individual+household+electric+power+ consumption. Last accessed March 4, 2024 (2012)
work page 2012
Show all 34 references
-
[9]
In: Dayal, U., Ramamritham, K., Vijayaraman, T.M
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: Dayal, U., Ramamritham, K., Vijayaraman, T.M. (eds.) Proceedings of the 19th International Conference on Data Engineering, March 5-8, 2003, Banga- lore, India, pp. 717–719 (2003). https://doi.org/10.1...
2003 arXiv
-
[10]
ACM Comput
Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top- k query processing techniques in relational database systems. ACM Comput. Surv. 40(4) (2008) https://doi.org/10.1145/1391729.1391730
2008
-
[11]
Martinenghi, D., Tagliasacchi, M.: Proximity rank join. Proc. VLDB Endow.3(1), 352–363 (2010) https://doi.org/10.14778/1920841.1920889
2010
-
[12]
IEEE Trans
Martinenghi, D., Tagliasacchi, M.: Cost-aware rank join with random and sorted access. IEEE Trans. Knowl. Data Eng.24(12), 2143–2155 (2012) https://doi.org/ 10.1109/TKDE.2011.161
2012 doi
-
[13]
PVLDB 10(11), 1454–1465 (2017) https://doi.org/10.14778/3137628.3137653
Ciaccia, P., Martinenghi, D.: Reconciling skyline and ranking queries. PVLDB 10(11), 1454–1465 (2017) https://doi.org/10.14778/3137628.3137653
2017
-
[14]
In: Li, G., 15 Li, Z., Idreos, S., Srivastava, D
Mouratidis, K., Li, K., Tang, B.: Marrying top-k with skyline queries: Relax- ing the preference input while producing output of controllable size. In: Li, G., 15 Li, Z., Idreos, S., Srivastava, D. (eds.) SIGMOD ’21: International Conference on Management of Data, Virtual Even...
2021
-
[15]
TODS 30(1), 41–82 (2005) https://doi.org/10.1145/1061318
Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. TODS 30(1), 41–82 (2005) https://doi.org/10.1145/1061318. 1061320
2005 doi
-
[16]
ACM Trans
Ciaccia, P., Martinenghi, D.: Flexible skylines: Dominance for arbitrary sets of monotone functions. ACM Trans. Database Syst. 45(4), 18–11845 (2020) https: //doi.org/10.1145/3406113
2020 doi
-
[17]
In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pp
Ciaccia, P., Martinenghi, D.: F A + TA < FSA: Flexible score aggregation. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pp. 57–66 (2018). https://doi.org/10.1145/3269206.3271753 ...
2018
-
[18]
In: Bergamaschi, S., Noia, T.D., Maurino, A
Ciaccia, P., Martinenghi, D.: Beyond skyline and ranking queries: Restricted skylines (extended abstract). In: Bergamaschi, S., Noia, T.D., Maurino, A. (eds.) Proceedings of the 26th Italian Symposium on Advanced Database Sys- tems, Castellaneta Marina (Taranto), Italy, June 2...
2018
-
[19]
In: Amato, G., Gennaro, C., Oria, V., Radovanovic, M
Bedo, M.V.N., Ciaccia, P., Martinenghi, D., Oliveira, D.: A k-skyband approach for feature selection. In: Amato, G., Gennaro, C., Oria, V., Radovanovic, M. (eds.) Similarity Search and Applications - 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2-4, 2019...
2019 doi
-
[20]
In: Mecella, M., Amato, G., Gennaro, C
Ciaccia, P., Martinenghi, D.: Flexible score aggregation (extended abstract). In: Mecella, M., Amato, G., Gennaro, C. (eds.) Proceedings of the 27th Italian Symposium on Advanced Database Systems, Castiglione della Pescaia (Gros- seto), Italy, June 16-19, 2019. CEUR Workshop P...
2019
-
[21]
In: Mendelzon, A.O., Paredaens, J
Fagin, R.: Fuzzy queries in multimedia database systems. In: Mendelzon, A.O., Paredaens, J. (eds.) Proceedings of the Seventeenth ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA, pp. 1–10 (1998). https://doi.org/1...
1998
-
[22]
IEEE Trans
Cui, B., Chen, L., Xu, L., Lu, H., Song, G., Xu, Q.: Efficient skyline computation in structured peer-to-peer systems. IEEE Trans. Knowl. Data Eng. 21(7), 1059– 1072 (2009) https://doi.org/10.1109/TKDE.2008.235 16
2009 doi
-
[23]
In: Halevy, A.Y., Ives, Z.G., Doan, A
Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: Halevy, A.Y., Ives, Z.G., Doan, A. (eds.) Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pp...
2003
-
[24]
PVLDB 8(12), 1554– 1565 (2015)
Mouratidis, K., Zhang, J., Pang, H.: Maximum rank query. PVLDB 8(12), 1554– 1565 (2015)
2015
-
[25]
In: 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2009, Higashi Hiroshima, Japan, 8-11 December 2009, pp
Nakagawa, M., Man, D., Ito, Y., Nakano, K.: A simple parallel convex hulls algorithm for sorted points and the performance evaluation on the multicore pro- cessors. In: 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 20...
2009 doi
-
[26]
In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G
Wang, Y., Yesantharao, R., Yu, S., Dhulipala, L., Gu, Y., Shun, J.: Pargeo: A library for parallel computational geometry. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algo- rithms, ESA 2022, September 5-9, 2022, Berlin/Potsd...
2022 doi
-
[27]
Symmetry 16(12) (2024) https://doi
Kwon, H., Oh, S., Baek, J.-W.: Algorithmic efficiency in convex hull computation: Insights from 2d and 3d implementations. Symmetry 16(12) (2024) https://doi. org/10.3390/sym16121590
2024 doi
-
[28]
ACM Comput
Guerreiro, A.P., Fonseca, C.M., Paquete, L.: The hypervolume indicator: Compu- tational problems and algorithms. ACM Comput. Surv. 54(6), 119–111942 (2022) https://doi.org/10.1145/3453474
2022 doi
-
[29]
Bringmann, K., Friedrich, T.: Approximating the least hypervolume contributor: Np-hard in general, but fast in practice. Theor. Comput. Sci.425, 104–116 (2012) https://doi.org/10.1016/J.TCS.2010.09.026
2012 doi
-
[30]
In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011, pp
Soliman, M.A., Ilyas, I.F., Martinenghi, D., Tagliasacchi, M.: Ranking with uncer- tain scoring functions: semantics and sensitivity measures. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011, pp. 8...
2011
-
[31]
In: Andreasen, T., Yager, R.R., Bulskov, H., Christiansen, H., Larsen, H.L
Masciari, E.: Trajectory clustering via effective partitioning. In: Andreasen, T., Yager, R.R., Bulskov, H., Christiansen, H., Larsen, H.L. (eds.) Flexible Query Answering Systems, 8th International Conference, FQAS 2009, Roskilde, Den- mark, October 26-28, 2009. Proceedings. ...
2009 doi
-
[32]
Masciari, E., Mazzeo, G.M., Zaniolo, C.: Analysing microarray expression data through effective clustering. Inf. Sci. 262, 32–45 (2014) https://doi.org/10.1016/ J.INS.2013.12.003
2014
-
[33]
In: Desai, B.C., Sacc` a, D., Greco, S
Fazzinga, B., Flesca, S., Masciari, E., Furfaro, F.: Efficient and effective RFID data warehousing. In: Desai, B.C., Sacc` a, D., Greco, S. (eds.) International Database Engineering and Applications Symposium (IDEAS 2009), September 16-18, 2009, Cetraro, Calabria, Italy. ACM I...
2009
-
[34]
ACM Trans
Fazzinga, B., Flesca, S., Furfaro, F., Masciari, E.: Rfid-data compression for supporting aggregate queries. ACM Trans. Database Syst. 38(2), 11 (2013) https://doi.org/10.1145/2487259.2487263 18
2013
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.