{"id":"5338b1b0-6a6d-4e60-bfc5-dc61dd392b1e","arxiv_id":"2411.16990","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A skip graph variant that swaps the roles of keys and membership vectors, using z-order of k-dimensional data for grouping, is proposed to improve range-query message counts in mobile sensor networks.","lead":"This paper proposes a new version of a skip graph, a structure for finding data spread across many sensors, where geographic coordinates instead of random values decide how nodes are grouped. The authors claim this can make range queries faster for moving sensor networks such as drone swarms, but they present no measurements or simulations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Query procedure in Sec. 5.3 can require Θ(n) messages for sparse or skewed ranges, so the claimed message-count advantage over standard skip graphs is unsupported.","rationale":"The construction is coherent, and the paper is honest that evaluation is future work, but the central claim rests entirely on a single 8-node example. The reader's weakest assumption correctly targets the base-list prefix search. I would qualify it: the expected distance to a one-bit L1 match is actually constant when data are uniform, so the linear-scan risk comes from the full multi-level climb and from low-selectivity or skewed queries, where the target prefix is a small fraction of its parent group. A further structural point strengthens the reader's argument: the standard skip graph's sorted base list makes range results contiguous, while the inverted graph's random-key base list scatters them, so any range requiring more than one z-order prefix has to repeat prefix searches. The paper gives no analytical bound, no simulation, and no comparison, and Section 7 confirms this. These observations do not change the reader's REJECT verdict; they refine why it is correct.","tokens_in":6990,"tokens_out":11354,"duration_ms":118594,"concrete_test":"Evaluate the Sec. 5.3 procedure analytically or by simulation for n = 2^10 through 2^16 points uniformly distributed in [0,1]^2 with random keys: issue point queries and 1%-selectivity range queries, count messages (nodes visited in all level scans), and compare with a standard skip graph under the same load. Repeat with a skewed placement, e.g., 90% of nodes in one quadrant. If inverted-graph mean messages grow faster than O(log n + output) or exceed the standard skip graph's count, the central message-count claim is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's only stated performance conclusion (Sec. 6) is that the inverted skip graph reduces total query messages 'if certain query conditions are met,' but no model, bound, or simulation is supplied; Sec. 7 explicitly lists simulation as future work. The query algorithm (Sec. 5.3) starts at L0 and, at each level, scans a list sorted by random keys until it finds a node whose deterministic z-order membership-vector prefix extends one more bit. Since keys are random and independent of the z-order prefix, matching nodes are scattered in every list. The expected scan length at a level is roughly (size of the current prefix group)/(size of the target child prefix group). For a point query, a low-selectivity range, or a skewed spatial deployment, this ratio can be Θ(n), and the problem recurs at every level of the climb. Additionally, a range that decomposes into multiple z-order prefixes requires repeated searches, because results are not contiguous in the random-key base list, unlike in the standard skip graph, which locates a boundary key in O(log n) expected messages and then traverses a contiguous base-list run. Thus the load-bearing property behind the claimed improvement—cheap discovery of the first matching prefix—is neither proved nor plausibly bounded.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an extension to the distributed skip graph, called the multi-dimensional inverted skip graph, for answering k-dimensional range queries in mobile sensor networks such as UAV swarms. The construction inverts the roles of keys and membership vectors in a standard skip graph: node keys are computed randomly, while membership vectors are computed deterministically from the z-order linearization of the node's k-D coordinates. Range queries are executed by starting at the base level and moving upward through lists whose membership-vector prefixes match the query prefix, until the full prefix is matched or the top level is reached. The paper illustrates the construction and query execution on an eight-node example with 2-D coordinates, and Section 6 claims better performance in terms of total messages sent under certain query conditions, especially in mobile environments. Section 7 defers insert, delete, and repair functions, as well as simulation studies, to future work.","tokens_in":11,"tokens_out":2905,"duration_ms":87944,"significance":"If the claimed improvement were established, the inverted skip graph would be a useful application-layer routing structure for k-D range queries in mobile sensor networks, since it would group nodes by spatial proximity via deterministic z-order membership vectors while keeping keys random. The paper's construction is clearly described, and the worked example demonstrates that the query procedure can return correct results in at least one small instance. Those are genuine strengths. However, the paper supplies no theorem, no asymptotic bound, no simulation, and no experimental data supporting the central performance claim. The base-level scan in Section 5.3 appears to threaten the claimed efficiency gain, and the maintenance operations required for mobile environments are explicitly left for future work. The idea of inverting key and membership-vector roles is interesting, but the manuscript currently offers only an untested proposal rather than a demonstrated contribution.","major_comments":[{"comment":"The query algorithm starts at the base level L0 and scans the list, which is sorted by random keys, in both directions to find a node whose L1 membership-vector prefix matches the query. Because the random key order is independent of the deterministic z-order membership vectors, the expected length of this scan can be Θ(n) for a sparse or skewed query range, and the problem can recur at each higher level when the query decomposes into multiple z-order prefixes. The paper provides no complexity analysis for this step, so the claim in Section 6 that the inverted skip graph reduces total messages sent relative to a standard skip graph is unsupported; the standard skip graph locates a boundary key in O(log n) expected messages and then traverses a contiguous base-list run.","section":"Section 5.3"},{"comment":"Section 6 states that the proposed construction 'yields better performance in terms of total messages sent' under certain query conditions, but no theorem, asymptotic bound, simulation, or experiment is presented anywhere in the paper. Section 7 explicitly lists simulation studies as future work, and no analytical argument is supplied to justify the performance claim. Since the paper's central contribution is this claimed improvement, the manuscript currently presents only a conjecture and an illustrative example, not a supported result.","section":"Sections 6 and 7"},{"comment":"The paper defines only the static construction and query procedure; Section 7 states that insert, delete, and repair functions are left for future work. Yet Section 6 claims the structure is especially beneficial in mobile environments, where node arrivals, departures, and link changes are the norm. Without maintenance operations, the claimed mobile-environment performance advantage cannot be evaluated, and it is unclear that the inverted skip graph can even remain functional under mobility.","section":"Section 7"}],"minor_comments":[{"comment":"There is a typo in the first paragraph: 'nodes haveing key values' should read 'nodes having key values.'","section":"Section 3.2"},{"comment":"The description of the example query (0010002–0010112) would be easier to follow if the text explicitly identified which nodes lie inside the range and how the traversal at each level proceeds, since the figure's dense labels make the path hard to verify.","section":"Section 5.3 and Figure 5"},{"comment":"The coordinate list for the eight nodes contains duplicate coordinates (0,7) for two nodes; the text should clarify whether this is intentional and how duplicate z-order keys are handled in the standard skip graph.","section":"Section 4.1"},{"comment":"The figures lack captions and use very dense notation without a legend; adding captions and explaining the underlining and binary subscripts would improve readability.","section":"Figures 3, 4, and 5"}],"recommendation":"reject","confidential_remarks":"The manuscript is more a position paper or extended abstract than a complete research article. The core performance claim is unverified, and the query procedure as described in Section 5.3 may well be less efficient than a standard skip graph for typical range queries. If the authors can provide a complexity analysis of the base-level scan and simulation results comparing message counts for both structures, a substantially revised version could be reconsidered; in its current form the paper does not meet the evidentiary standard for a journal in this field."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The inverted skip graph is a genuinely new structural variant: swap the deterministic keys and random membership vectors, and group nodes by z-order prefixes. That's a clean twist, and the paper explains it clearly, with a worked example that shows correct query execution. The paper is also honest about its status: Section 7 explicitly says insert/delete/repair functions are not defined, and simulation studies are future work. The citation list is appropriate.\n\nWhat is missing is evidence for the central claim in Section 6: that the inverted skip graph 'yields better performance in terms of total messages sent' under certain query conditions. No simulation, no analytical bound, no comparison against a standard skip graph. A correctness example is not a performance result.\n\nAnd the proposed query algorithm has a cost problem. Section 5.3 starts at L0 and traverses the base list, which is sorted by random keys, looking for a node with a matching z-order prefix. Since random keys are independent of z-order coordinates, matching nodes are scattered everywhere. The expected scan length to find the first match at a level can be Θ(n), and this repeats at each level. For point queries, low-selectivity ranges, or skewed spatial distributions, that linear scanning swamps any grouping benefit. The standard skip graph, by contrast, locates a boundary key in O(log n) and then walks a contiguous run. So the claimed advantage is not merely unproven; as described, it is implausible for exactly the use case the paper targets.\n\nThe authors deserve credit for clearly delimiting what is done and what is not. The structural idea is worth keeping in mind, and the worked example is readable. But the paper does not establish its stated improvement.\n\nThis is a note for a reading group, not a paper to build on. I would not cite it as a source of performance guarantees. The authors should run the simulations they mention and produce even a rough expected-message-cost calculation. With that, the variant might become a legitimate contribution. As it stands, I would desk reject.","headline":"A clean structural twist on skip graphs—inverting keys and membership vectors—but the central message-count claim is unsupported and the proposed query algorithm may be linear-time per query.","tokens_in":7710,"tokens_out":3428,"would_cite":false,"duration_ms":33980,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An inverted skip graph that swaps the roles of keys and membership vectors—using z-order coordinates for grouping and random keys for sorting—is proposed to reduce messages sent in k-dimensional range queries on mobile sensor networks…","keywords":["skip graph","range query","z-order curve","membership vector","k-dimensional data","mobile sensor network","distributed data structure","Morton order"],"falsifier":"Simulate both skip graphs on a uniform 2-D field of $n = 10{,}000$ nodes and count total messages for range queries of fixed radius (e.g., 1% of the field). If the inverted skip graph's average messages per query grow linearly with $n$ while the standard skip graph's grow logarithmically, the central claim is false; more directly, instrument the inverted graph's base-list scan and check whether its average length stays $\\mathcal{O}(\\log n)$ for typical queries.","tokens_in":6793,"feed_emoji":"📍","tokens_out":7915,"duration_ms":65286,"temperature":0.7,"pith_summary":"The paper proposes an inverted skip graph for k-dimensional range queries in mobile sensor networks. In a standard skip graph, nodes are grouped by random membership vectors and sorted by deterministic keys; the new design swaps the roles, deriving each node's membership vector from the z-order value of its k-dimensional coordinates and using a locally generated random value as its key. The paper claims this rearrangement yields better performance in terms of total messages sent for range queries when certain query conditions are met, especially in mobile environments, because nodes close in $k$-D space share long membership-vector prefixes and can be reached by traversing a single compact list. The paper presents the construction and query procedure but provides no complexity analysis or simulation results.","feed_headline":"Role swap in skip graphs cuts range-query messages","feed_subtitle":"Grouping nodes by their coordinates instead of random IDs lets range queries hit just the right cluster.","key_machinery":"The central mechanism is the inversion of keys and membership vectors combined with z-order linearization of the $k$-D data. Z-ordering maps each node's coordinates to a 1-D bit string by interleaving the bits of the $k$ coordinate values; in the inverted skip graph this bit string becomes the node's membership vector, while the node's key is a random number. Because z-ordering preserves locality, nodes whose coordinates are close in $k$-D space have membership vectors that share long common prefixes, so a range query expressed as a z-order interval corresponds to a single prefix. The query procedure climbs from the base list upward by matching successively longer membership-vector prefixes, and when the prefix matches exactly it traverses exactly the list containing the queried group, which is claimed to reduce the total number of messages sent relative to a standard skip graph under favorable conditions.","core_discovery":"On its own terms, the paper constructs a multi-dimensional inverted skip graph in which the roles of keys and membership vectors are exchanged: a node's membership vector is the deterministic z-order bit string of its $k$-dimensional coordinates, while its key is a random number computed locally. A range query is converted into a z-order interval and then into a membership-vector prefix; the query starts at the base list $L_0$, traverses it in both directions until it finds a node whose $L_1$ prefix matches, and climbs the levels by matching increasingly long prefixes, stopping when the prefix fully matches, when the top level is reached, or when no node in the current list has the next-level prefix. The paper states that grouping nodes by the $k$-D information being queried yields better performance in terms of total messages sent than a standard skip graph, if certain query conditions are met, especially in mobile environments.","pith_inferences":["The paper gives no bound on the base-level scan needed to find the first matching prefix; if that scan is $\\mathcal{O}(n)$ in the worst case, the inverted graph's message savings over a standard skip graph's $\\mathcal{O}(\\log n + r)$ search would disappear for typical query sizes.","A simulation varying range size and node count could pin down the 'certain query conditions': the inverted graph should win exactly when the z-order interval of the query collapses to a short prefix.","Other locality-preserving linearizations (e.g., Hilbert order) could be substituted for z-ordering to improve prefix matching for non-rectangular query regions, an extension the paper does not explore.","Because the base list is sorted by random keys, adding a secondary index or a coarse coordinate ordering could make the bottom-up climb cheaper; the paper does not consider this."],"forward_implications":["A $k$-D range query that maps to a single z-order prefix contacts exactly the nodes in that prefix's list, avoiding a full traversal of the base list.","Each node computes its own membership vector and key locally, so the inverted structure preserves the decentralized construction of standard skip graphs.","If the claimed condition holds, the inverted skip graph sends fewer total messages per range query than a standard skip graph, which matters for time-critical queries in bandwidth-limited mobile swarms such as UAV networks.","The bottom-up prefix-climb query procedure replaces the standard top-down search, so the structure's usefulness depends on the cost of finding the first matching prefix at the base level."],"supporting_citations":[{"why":"Defines the standard skip graph and its range-query procedure, the baseline the inverted design modifies.","marker":"[1]"},{"why":"Independent proposal of skip graphs, cited as the other origin of the structure being extended.","marker":"[6]"},{"why":"Introduces skip lists, the probabilistic list structure underlying skip graphs.","marker":"[9]"},{"why":"Introduces Morton z-ordering, the linearization used to derive deterministic membership vectors.","marker":"[7]"},{"why":"A prior multi-dimensional skip graph variant that the paper contrasts with its own construction.","marker":"[3]"},{"why":"Another multi-dimensional P2P query structure used as a baseline for dimensionality reduction.","marker":"[5]"},{"why":"Documents z-order and quadtree equivalence, supporting the locality argument for prefix grouping.","marker":"[11]"}],"fun_headline_variants":["Inverted skip graph targets k-D range queries","Z-order grouping cuts range-query messages","Key-vector swap optimizes mobile range lookups","Skip graph role reversal boosts UAV range queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that scanning the random-key-sorted base list to find the first node with a matching membership-vector prefix is cheap enough to keep total messages below the standard skip graph's logarithmic search; the paper gives no bound on this scan, so if it costs $\\mathcal{O}(n)$ per query the claimed improvement fails.","fun_headline_variants_meta":{"raw":{"variants":["Inverted skip graph targets k-D range queries","Z-order grouping cuts range-query messages","Key-vector swap optimizes mobile range lookups","Skip graph role reversal boosts UAV range queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000169,"raw_usage":{"total_tokens":1191,"prompt_tokens":798,"completion_tokens":393,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":414,"completion_tokens_details":{"reasoning_tokens":335}},"tokens_in":414,"tokens_out":393,"duration_ms":4387,"temperature":1.0,"reasoning_tokens":335,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:38:49.189734+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate both skip graphs on a uniform 2-D field of $n = 10{,}000$ nodes and count total messages for range queries of fixed radius (e.g., 1% of the field). If the inverted skip graph's average messages per query grow linearly with $n$ while the standard skip graph's grow logarithmically, the central claim is false; more directly, instrument the inverted graph's base-list scan and check whether its average length stays $\\mathcal{O}(\\log n)$ for typical queries.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the standard skip graph and its range-query procedure, the baseline the inverted design modifies."},{"cited_title":"Thus, the query range becomes (0010002 – 0010112)","cited_arxiv_id":null,"evidence_quote":"Independent proposal of skip graphs, cited as the other origin of the structure being extended."},{"cited_title":"Standard skip graphs group nodes based on common prefixes of randomly computed membership vectors and sorted on deterministically computed key values","cited_arxiv_id":null,"evidence_quote":"Introduces skip lists, the probabilistic list structure underlying skip graphs."},{"cited_title":"Overview Our proposed modification to the standard skip graph inverts the roles of deterministic key values and random membership vectors","cited_arxiv_id":null,"evidence_quote":"Introduces Morton z-ordering, the linearization used to derive deterministic membership vectors."},{"cited_title":"find” all nodes according to the parameters of the query. In a range query, all nodes haveing key values in the specified range should be notified of the query. To “find","cited_arxiv_id":null,"evidence_quote":"A prior multi-dimensional skip graph variant that the paper contrasts with its own construction."},{"cited_title":"A node maps its k-D data (locally) to a 1-D key using a linearization method, such as z-ordering (cf","cited_arxiv_id":null,"evidence_quote":"Another multi-dimensional P2P query structure used as a baseline for dimensionality reduction."},{"cited_title":"We also thank Hanan Samet for providing us an advance copy of [11]","cited_arxiv_id":null,"evidence_quote":"Documents z-order and quadtree equivalence, supporting the locality argument for prefix grouping."}],"review_version":1}