{"id":"a373fe9f-eb95-4978-ba5f-644211622e12","arxiv_id":"2412.15468","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper presents a new algorithm for computing non-dominated flexible skyline queries, a hybrid of top-k and skyline ranking, when data is spread across separate lists that can only be scanned top-down without random access. The algorithm is proved correct and optimal within its class, and tested on synthetic and real datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 is specified over unbounded R+ but its worst-bound comparisons require a finite per-attribute maximum; without stating that assumption, wb/bb are undefined and the claimed early exit collapses to a full scan.","rationale":"On a good-faith reading, the central contribution is an NRA-style algorithm whose correctness and instance-optimality depend on the standard threshold-and-bounds machinery. The paper supplies only the lower endpoint for unseen values (via the threshold point) and leaves the upper endpoint implicit. The reader's weakest-assumption identification matches mine: the finite-upper-bound assumption is the place where the argument is least secure. This concern is not merely stylistic; it changes the algorithm's behavior in the formal model. I also reviewed the instance-optimality proof and found a secondary gap: it bounds only the growing phase, not the shrinking-phase accesses, so the proof is terse and incomplete as written. That secondary gap is patchable and less fundamental than the missing bounded-domain assumption. The experiments are broad and the algorithm is plausible once the missing assumption is stated, so no rejection is warranted; the conditional verdict stands.","tokens_in":13984,"tokens_out":31427,"duration_ms":282223,"concrete_test":"Take a finite 2-attribute dataset with values 1..N on both lists and run Algorithm 1 exactly as specified, with no externally supplied maxima and with domains R+. Instrument wb/bb and check whether, for every tuple not yet seen on both lists, wb contains an unbounded value, so that Line 7 never becomes true before depth N. Compare the resulting depth with the early-exit depths reported in Figures 2-4. Then add a formal definition of wb/bb with a declared per-attribute upper bound U and re-check Theorems 2 and 3 under that assumption; if the theorems require the bound, the paper must state it explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 fixes attribute domains as R+ ('non-negative real numbers') with no upper bound. Algorithm 1's growing phase (Line 7) and shrinking phase (Line 15) rely on wb(t) and bb(t), which the text defines only as 'the best or worst still possible' completion for attributes not yet seen on a tuple. Over R+, the worst still possible value of an unseen attribute is unbounded: no finite tuple can serve as wb(t). If one represents it as infinity, then wb(t) is never F-dominated by tau at any finite depth, so the growing-phase stopping condition (Lines 7-8) never fires and the shrink-phase test treats every partially seen tuple as possibly F-dominated, forcing a full scan. The paper never states a finite-domain or known-maximum assumption, yet Theorems 2 and 3 are asserted for all instances with attributes in R+. This is the load-bearing gap: the algorithm's early-exit behavior, which the experiments quantify, depends on a boundedness assumption that is absent from the formal model.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the non-k-dominated flexible skyline (NDk) in vertically distributed (\"middleware\") datasets where only sorted access is available. It proposes Algorithm 1 with a growing phase that accumulates candidate tuples until k seen tuples have worst-case completions F-dominating the threshold point, followed by a shrinking phase that removes tuples F-dominated by k others and decides whether further sorted accesses are needed. The paper claims Theorem 2 (correctness) and Theorem 3 (instance optimality with ratio d over all no-wild-guess, no-random-access algorithms), and reports experiments on synthetic and real (NBA) data varying size, dimensionality, k, constraint spread, and batch size.","tokens_in":14182,"tokens_out":18831,"duration_ms":180874,"significance":"If the central claims were fully established, this would be a valuable contribution: it is, to the author's knowledge, the first NRA-style algorithm for the NDk operator, and it cleanly separates the F-dominance test as a black box from the access strategy, reusing prior results [8,9,10]. The experimental study is broad and honestly reports adverse cases (ANT distributions, high d, full-spread constraints) where early exit collapses. The instance-optimality target is the right notion for this setting. However, the formal development currently leaves three load-bearing gaps—the unbounded-domain treatment of worst completions, the unspecified shrinking-phase removal/output-completeness rule, and the unproved bound on shrinking-phase depth in Theorem 3—so the claimed correctness and optimality are not yet established.","major_comments":[{"comment":"Section 2 fixes attribute domains as R+ with no upper bound, but Algorithm 1 relies on wb(t) and bb(t) for partially seen tuples, which the text defines only as \"the best or worst still possible\" completion of unseen attributes. Over R+ the worst possible completion of an unseen attribute is unbounded; if it is represented as infinity, then Line 7's test wb(t) ≺F τ is never true for finite τ and Line 15's test bb(t) ⊀F wb(s) is always false (since every finite bb dominates an infinite wb), so the growing phase never stops early and the shrinking phase treats every partial tuple as possibly dominated, i.e., the claimed early exit degenerates to a full scan. The paper needs an explicit bounded-domain or known-maximum-per-attribute assumption and a formal definition of wb and bb; this is load-bearing for Theorems 2 and 3 and for the experimental early-exit results.","section":"Section 2; Algorithm 1, Lines 7 and 15"},{"comment":"The shrinking phase is underspecified for partial tuples. Line 11 says \"remove from B tuples F-dominated by other k tuples\" but does not say how F-dominance is decided when the dominating or dominated tuples are only partially seen; if removal is based on optimistic completions it can remove a tuple that is not actually dominated, and if it is based only on fully seen tuples the proof must say so. Moreover, the algorithm can stop deepening while a tuple s in B is still partial (the Line 17 condition can fail even when s has unseen attributes, e.g., with k=1 and all other tuples provably non-dominators), so `return B` at Line 21 can output tuples whose attribute values are unknown, and no random access is available to complete them. A precise removal rule and a final completion phase are needed before Theorem 2 can be considered proved.","section":"Algorithm 1, Lines 10-21; Theorem 2"},{"comment":"The instance-optimality proof only bounds the growing phase. It shows that Algorithm 1's growing phase stops by the time it reaches depth δ = max_i δ_i on all lists, and then concludes sumDepths(Algorithm 1,I) ≤ δ·d. But sumDepths is defined over all accesses until the solution is returned, and the shrinking phase (Lines 10-20) may perform additional sorted accesses—indeed the experiments in Section 4 measure a separate shrinking-phase depth that is sometimes larger than the growing-phase depth (e.g., Figure 8a). The proof gives no bound on these extra accesses, so Theorem 3's claimed optimality ratio d for total cost is not established. The proof also silently treats the virtual threshold tuple τA as if correctness of A on the actual instance implies that τA is F-dominated by k seen result tuples; this needs the standard adversarial-instance argument and a justification that those k result tuples are fully seen.","section":"Theorem 3 proof"}],"minor_comments":[{"comment":"\"shrinking phrase\" should be \"shrinking phase\".","section":"Section 3, first paragraph"},{"comment":"\"for t in seen tuples\" should be \"for t in B\" (or \"seen tuples\" should be defined), otherwise the iteration is ambiguous after tuples are removed in the shrinking phase.","section":"Algorithm 1, Line 6"},{"comment":"\"Output siez\" should be \"Output size\".","section":"Figure 5 caption"},{"comment":"The headings \"V arying\" should be \"Varying\" (e.g., \"Varying the dataset size N\").","section":"Section 4 headings"},{"comment":"The symbols wb(t) and bb(t) should be defined formally in the preliminaries or at the start of Section 3, with an explicit statement of what \"worst still possible\" means when the domain is unbounded; the current prose definition is insufficient for the pseudocode.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The paper builds heavily on the author's prior work [8,9,10], which is legitimate because the F-dominance test is explicitly treated as a black box. The main concern for the editor is that the correctness and optimality proofs are currently too terse for the claims made: the unbounded-domain issue and the partial-output issue are not mere presentation problems, and the instance-optimality proof omits the shrinking phase entirely. These are fixable within the manuscript's scope, but they require substantive changes to the formal model and proofs, hence the major-revision recommendation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Martinenghi's paper. The headline: it's the first NRA algorithm for the NDk flexible skyline, and the core two-phase scheme is a reasonable adaptation of the classical NRA pattern. But the paper claims correctness over unbounded R+ domains, and the algorithm's worst-bound computation is not well-defined there. That's a load-bearing gap, though it's fixable by adding a finite upper bound per attribute.\n\nWhat's genuinely new: no prior work has an NRA-style algorithm for NDk. The author correctly identifies this gap. The algorithm uses growing/shrinking phases with F-dominance bounds on threshold and per-tuple worst/best completions. The instance optimality proof, while terse, is actually sound: at depth δ=max(δ_i) the threshold point is worse than or equal to the threshold of any correct algorithm A that halts at depths δ_i, so the k witness tuples that F-dominate A's threshold also F-dominate this worse threshold. Ratio d is clean.\n\nThe experimental section is honest: it reports depth, F-dominance tests, and time across synthetic and real data, and it explicitly documents the expected collapse to near-full-scan on anti-correlated data. That's good practice.\n\nSoft spots, in order of severity. First, the unbounded domain issue. Section 2 sets attributes to R+ with no upper bound, but wb(t) for a partially seen tuple is defined as the worst 'still possible' completion of unseen attributes. Over R+, that is +∞ on each missing attribute. Then wb(t) never F-dominates the finite threshold τ, so the growing-phase stopping condition (Lines 7-8) never fires, and the shrinking phase's comparisons also become undefined or vacuous. The early-exit behavior that the experiments quantify depends on a known finite maximum that the paper never states. This is not a fatal mathematical error in the algorithm itself—classical NRA work typically assumes bounded scores—but it is a missing assumption that invalidates Theorems 2 and 3 as stated for the claimed domain. Fixing it requires a sentence and a few adjusted definitions, but it must be addressed.\n\nSecond, the shrinking-phase removal rule (Line 11) is under-specified for partial tuples: it says remove tuples F-dominated by k other tuples, but until a tuple is fully read, you only have bounds. Readers can guess it means using best/worst bounds, but the pseudocode should say so.\n\nThird, the proofs are terse. Theorem 2's argument is one paragraph, and Theorem 3's proof uses the 'virtual tuple' threshold without spelling out the monotonicity of F-dominance under component-wise ordering. It works, but it's easy to misread (I did on first pass).\n\nNo code or data is linked, so the experiments are not independently reproducible, which is a minor concern for a paper whose main claim is algorithmic.\n\nOverall: this is a useful, niche contribution for the middleware/no-random-access setting. The central gap is an omitted assumption, not a wrong idea. I'd send it to peer review, but I'd expect the reviewers to demand the boundedness assumption be stated upfront and the pseudocode clarified. The honest experimental reporting earns credit.\n\nRecommendation: send it out for review; with a proper revision it could become a solid reference for this specific query class.","headline":"First NRA algorithm for NDk is a sensible extension of the classical threshold pattern, but the unbounded R+ domain leaves wb/bb undefined and breaks the early-exit claim; fixable, but must be addressed.","tokens_in":14677,"tokens_out":6551,"would_cite":true,"duration_ms":51461,"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 introduces an algorithm that computes the non-dominated flexible skyline when only sorted access is available, and proves it correct and instance-optimal among no-random-access algorithms.","keywords":["non-dominated flexible skyline","flexible skyline","top-k query","skyline query","no random access","vertically distributed data","middleware scenario","instance optimality"],"falsifier":"Fix d=2 and a known NDk instance, run Algorithm 1 and any candidate correct no-random-access, no-wild-guess algorithm, and compare their depths per list: if a competitor ever reads on the shorter list less than half of Algorithm 1's reads there while remaining correct, Theorem 3's optimality ratio d=2 is violated.","tokens_in":13757,"feed_emoji":"📊","tokens_out":6172,"duration_ms":42977,"temperature":0.7,"pith_summary":"This paper asks whether the non-k-dominated flexible skyline (NDk), a hybrid of top-k and skyline queries, can be computed when data is vertically distributed across ranked lists and only sorted access is available. It answers yes: the proposed two-phase algorithm reads the lists from top to bottom, first collecting candidates until k seen tuples F-dominate the threshold point, then shrinking the buffer until only tuples F-dominated by fewer than k others remain. The paper proves the algorithm correct and shows it is instance optimal over all correct no-random-access, no-wild-guess algorithms, with an optimality ratio equal to the number of ranked lists. This matters because random access may be impossible or too costly in privacy-sensitive, streamed, or externally hosted datasets, where the classical NRA top-k approach already applies but no NRA method existed for flexible skylines.","feed_headline":"No-random-access skyline algorithm is correct and instance-optimal","feed_subtitle":"A two-phase sorted-access scan computes the non-dominated flexible skyline with provably minimal depth.","key_machinery":"The load-bearing device is the threshold point τ, the tuple formed by the last score read on each ranked list: because lists are sorted, no unseen tuple can beat τ on any attribute. Alongside τ the algorithm maintains, for every partially seen tuple, a worst bound and a best bound built from the best or worst possible completion of its unseen attributes. The growing phase stops when k tuples' worst bounds F-dominate τ; the shrinking phase repeatedly removes tuples F-dominated by k others and keeps digging deeper only when at least k surviving tuples could still F-dominate a candidate. F-dominance testing itself is treated as a black box.","core_discovery":"The central claim is that Algorithm 1 computes NDk(r;F) exactly in the middleware scenario when random access is unavailable, and that among all correct algorithms that only use sorted access and never guess unseen tuples it is instance optimal for the sum-of-depths cost measure, with optimality ratio d, the number of ranked lists (Theorems 2 and 3). The algorithm's stopping rule is that once k seen tuples F-dominate the threshold point—the virtual tuple of last-seen values on every list—no unseen tuple can enter the result, so the shrinking phase only needs to eliminate F-dominated candidates already in the buffer.","pith_inferences":["Implicit in the proofs but never stated: the early-exit guarantee presupposes a known finite upper bound on each attribute, so that the worst possible completion of a partially seen tuple is a finite tuple; over unbounded R+ domains the growing-phase stopping condition may never fire before a full scan.","A natural extension the author does not explore is adaptive batching, where the check frequency µ is chosen during execution on the basis of observed dominance density, potentially preserving more of the depth advantage while keeping F-dominance tests low.","The same two-phase threshold argument should transfer to other flexible-skyline variants such as POk, which the paper names as future work, and likely to any operator whose output can be characterized by F-dominance by k tuples.","The depth-optimality result is about sorted accesses, not about F-dominance tests; total time may still be dominated by the quadratic shrinking phase, so the practical bottleneck is test count rather than I/O."],"forward_implications":["A correct and instance-optimal NRA method now exists for NDk, so applications with only sorted access can run flexible-skyline-style preference queries without random access.","The optimality ratio d confirms that any correct no-random-access, no-wild-guess competitor can save at most a factor of d in sorted-access depth; no such algorithm can be asymptotically better.","For uniformly distributed data the experiments show early exit at a depth that grows sublinearly with dataset size, so the algorithm is practical in that regime.","Batching sorted accesses (parameter µ) trades a small depth increase for a large reduction in F-dominance tests, giving a tunable cost balance.","The algorithm inherits the known curse of dimensionality: with anticorrelated data or higher dimensions, NRA-type early exit degrades toward a full scan, limiting the operator's no-random-access usefulness to low-dimensional, non-anticorrelated settings."],"supporting_citations":[{"why":"Supplies the classical NRA algorithm and the instance-optimality framework that the paper generalizes to NDk.","marker":"[16]"},{"why":"Introduces the non-dominated flexible skyline ND, the operator this paper extends to the NRA scenario.","marker":"[8]"},{"why":"Defines NDk and the FSA algorithm for the random-access middleware case that the new NRA algorithm complements.","marker":"[9]"},{"why":"Provides the F-dominance testing machinery, used as a black box in Algorithm 1 and in the experiments.","marker":"[10]"},{"why":"Establishes the sorted-access/random-access middleware model and the FA algorithm that NRA-style methods build on.","marker":"[14]"},{"why":"Defines the k-skyband, of which NDk is a preference-aware generalization.","marker":"[30]"},{"why":"Source of the growing-phase/shrinking-phase structure used in Algorithm 1.","marker":"[21]"}],"fun_headline_variants":["No-random-access ND skyline: correct and instance-optimal","Instance-optimal skyline without random access","Two-phase sorted scan achieves optimal ND skyline","Skyline without random access: correctness and optimality","Optimal ND skyline with no random access in distributed data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every attribute has a known finite upper bound, so the worst possible completion of a partially seen tuple is a finite tuple usable in F-dominance comparisons; the paper defines attribute domains as unbounded non-negative reals and never states this requirement.","fun_headline_variants_meta":{"raw":{"variants":["No-random-access ND skyline: correct and instance-optimal","Instance-optimal skyline without random access","Two-phase sorted scan achieves optimal ND skyline","Skyline without random access: correctness and optimality","Optimal ND skyline with no random access in distributed data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001473,"raw_usage":{"total_tokens":5948,"prompt_tokens":996,"completion_tokens":4952,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":4875}},"tokens_in":612,"tokens_out":4952,"duration_ms":24010,"temperature":1.0,"reasoning_tokens":4875,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:25:34.181635+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix d=2 and a known NDk instance, run Algorithm 1 and any candidate correct no-random-access, no-wild-guess algorithm, and compare their depths per list: if a competitor ever reads on the shorter list less than half of Algorithm 1's reads there while remaining correct, Theorem 3's optimality ratio d=2 is violated.","supporting_citations":[{"cited_title":"Optimal aggregation algo- rithms for middleware","cited_arxiv_id":null,"evidence_quote":"Supplies the classical NRA algorithm and the instance-optimality framework that the paper generalizes to NDk."},{"cited_title":"Reconciling skyline and ranking queries","cited_arxiv_id":null,"evidence_quote":"Introduces the non-dominated flexible skyline ND, the operator this paper extends to the NRA scenario."},{"cited_title":"Flexible skylines: Dominance for arbitrary sets of monotone functions","cited_arxiv_id":null,"evidence_quote":"Provides the F-dominance testing machinery, used as a black box in Algorithm 1 and in the experiments."},{"cited_title":"Combining fuzzy information from multiple systems","cited_arxiv_id":null,"evidence_quote":"Establishes the sorted-access/random-access middleware model and the FA algorithm that NRA-style methods build on."},{"cited_title":"Progressive skyline computation in database systems","cited_arxiv_id":null,"evidence_quote":"Defines the k-skyband, of which NDk is a preference-aware generalization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the growing-phase/shrinking-phase structure used in Algorithm 1."}],"review_version":1}