{"id":"ffb37d08-cd49-40b6-a1e4-11998b771efc","arxiv_id":"1908.04517","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The group-list, an extension of the author's Node-list, speeds up AND/OR queries on frequent terms but is slower on infrequent terms and is tested only against an unspecified inverted index on one synthetic dataset.","lead":"This paper proposes a new index structure, the group-list, that organizes document identifiers into groups to speed up Boolean AND/OR queries. It reports speedups over the inverted index on a synthetic dataset, but only for frequent or mixed term queries, and the comparison baseline is not described.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's frequent-term join replaces each tuple with at most one descendant, so multi-branch descendants are dropped and BAND results may be incomplete.","rationale":"The central claim is that the group-list enables correct and faster BAND/BOR query processing, so Algorithm 3 must be a correct implementation of Property 1. Property 1 itself is plausible: count-sorted insertion packs co-occurring infrequent terms into a common leaf node, so the same-preorder intersection used for infrequent terms is sound. The more concrete vulnerability is in the frequent-term join of Algorithm 3: lines 10–15 replace a current tuple by a single descendant tuple, whereas multiple descendant tuples may exist for a frequent term under the same ancestor. Omitting any of these descendants removes whole document sets from the result. The reported speedups are obtained by running this algorithm, so incomplete query results would invalidate the experimental comparison. The paper provides no code or data, the inverted-index baseline is unspecified, and its own tables show the group-list is slower for infrequent-term queries, so the unqualified 'outperforms' claim is overbroad even setting the algorithm issue aside. A small adversarial test would settle whether the implementation follows the pseudocode or the referenced code-intersection. Given the correctness risk and the lack of reproducibility, the paper in its current form should be rejected; a corrected join and new experiments would be needed for reconsideration.","tokens_in":7794,"tokens_out":14825,"duration_ms":157974,"concrete_test":"Construct a small corpus where one frequent term has two descendant nodes for another frequent term (e.g., documents {b,a}, {b,c,a}, {b,a}); build the P-tree, generate group-lists, run Algorithm 3 as written for the BAND query {a,b}, and compare Res_did against the ground-truth document set {1,2,3}. If Res_did misses document 2, the algorithm is incomplete. Also run the check on random datasets and compare with a brute-force intersection to confirm the scope of the omission.","verdict_should_be":"REJECT","load_bearing_attack":"In Algorithm 3 (BAND query processing), the frequent-term join in lines 8–15 processes each tuple tp in GL1:f by checking whether there exists a descendant tuple tp* in the group-list of the next term and, if so, replacing tp with tp* (lines 11–13). This collapses all matching descendants into a single tuple. But Property 1, and the Node-list intersection method cited from [Deng and Wang 2010], requires retaining every descendant tuple of the next term, because each such tuple carries a did_set of documents that satisfy the full termset. In a P-tree, a frequent term can have several descendant nodes for another frequent term via different intermediate branches (e.g., the same term b node may have descendants a under b→c→…→a and b→e→…→a). Keeping only the first such descendant drops the documents in the other branches from Res_did, yielding incorrect BAND answers. The same flaw affects the mixed frequent/infrequent step at lines 17–19 if GL1:f omits descendants. If the intended implementation instead uses Algorithm 2 of [Deng and Wang 2010] to keep all descendants, the paper must state this; as written, the pseudocode is not a correct implementation of Property 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript proposes a new index structure, the group-list, which records for each term a set of (pre-order, post-order, did_set) tuples obtained from a prefix tree over the document collection. Frequent terms are stored in non-leaf nodes and infrequent terms are packed into leaf-node labels, so the group-list indexes both frequent and infrequent terms, unlike the author's earlier Node-list. The paper gives construction and generation algorithms, presents a BAND query-processing algorithm, and reports a comparison with an inverted index on a synthetic dataset, claiming that the group-list outperforms the inverted index. The conclusion repeats this claim, but the experimental tables show the inverted index is faster on several infrequent-term query groups.","tokens_in":7979,"tokens_out":8820,"duration_ms":84211,"significance":"The group-list idea is a natural extension of the author's previous Node-list line of work, and if the query-processing algorithm were correct, the structure could offer a simple index with space comparable to an inverted index and faster Boolean intersection/union on frequent-term queries. The paper also explicitly provides construction pseudocode and a comparison on a public synthetic data generator. However, the significance of the current manuscript is diminished by (i) an apparent correctness bug in the frequent-term join in Algorithm 3, (ii) a mismatch between the stated claim and the reported IQ-group results, and (iii) the absence of a described inverted-index baseline. These issues prevent the paper from substantiating its central claim.","major_comments":[{"comment":"The frequent-term join replaces each tuple tp with at most one descendant tuple tp*, but Property 1 requires retaining every descendant tuple of the next term, because each descendant carries a distinct did_set whose union forms the correct result. Concretely, if term t_i appears in two descendant nodes of a given node via different branches (e.g., documents {b,c,a} and {b,e,a} create two a-nodes under the b-node), the algorithm keeps only one of the two a tuples in GL1:f; the did_set of the other branch is then absent from GL1:f, and the ancestor test at lines 17-19 will miss any infrequent tuple whose documents lie in that branch. The pseudocode must be revised to collect all descendant tuples (or explicitly invoke the Node-list code-intersection method that does so); as written, Algorithm 3 is not a correct implementation of Property 1.","section":"Section 3, Algorithm 3, lines 8-15"},{"comment":"The pseudocode is not well-formed when all query terms are frequent, which is exactly the FQ2/FQ4/FQ6 test cases. When f = K, GL_{f+1}:K in lines 1 and 16 denotes GL_{K+1}:K, an undefined object, and the final loop over GLf+1:K is empty, so Res_did would be empty even though the preceding join lines 8-15 computed GL1:f. The experiments report nonzero running times for FQ queries, so the actual implementation must differ from the printed algorithm; the paper should present the implemented algorithm, including how GL1:f is converted into Res_did.","section":"Section 3, Algorithm 3"},{"comment":"The abstract and conclusion state that the group-list 'outperforms the inverted index,' but the paper's own data contradict this for infrequent-term queries: in Table 3, the inverted index is faster for IQ2, IQ4, and IQ6 (4.93 vs 7.37, 7.97 vs 10.85, 9.10 vs 12.01 seconds), and in Table 4 it is faster for IQ2 and IQ6 (7.35 vs 8.96, 13.07 vs 13.23). The claim should be restricted to frequent-term and mixed queries. In addition, the inverted-index baseline is not described: the posting-list representation, merge/intersection algorithm, and whether it is compressed or uncompressed are all unspecified, making the comparison unreproducible; no standard deviations, confidence intervals, or significance tests are reported.","section":"Section 4, Tables 3 and 4"},{"comment":"Property 1 is the sole correctness foundation of the query-processing algorithms, yet it is not proven here; the paper refers to the proof methods of [Deng and Wang 2010]. Because the group-list extends the Node-list to include infrequent terms that may be packed into shared leaf-node labels, the paper should provide a self-contained argument (or at least identify the specific conditions under which the Node-list intersection proof carries over) rather than asserting inheritance. This matters in particular for tuples representing several infrequent terms in a single leaf node, a case not covered by the Node-list construction.","section":"Section 2, Property 1"}],"minor_comments":[{"comment":"The text refers to 'algorithm 4' for handling intersection of infrequent terms, but no Algorithm 4 appears in the manuscript; either include it or cite the relevant code-intersection routine.","section":"Section 3"},{"comment":"The group-list size '2,086,760,13 bytes' appears to be a typo for 2,086,760,013 bytes; the text also contains 'parellelly' (Section 5) and 'is not less than he count' (Section 3).","section":"Section 4"},{"comment":"BOR query processing is only described as 'almost the same' as BAND; the union-based algorithm should be stated explicitly so that results can be reproduced.","section":"Section 3"},{"comment":"The paper reports results for only two values of the percentage threshold ζ and does not analyze how the number of frequent terms affects query time, although Section 2 promises such discussion.","section":"Section 4"},{"comment":"All figures (Figures 1-7) are referenced but not embedded in the text extract; the authors should ensure the final version includes legible figures and tables with captions.","section":"Figures"}],"recommendation":"major_revision","confidential_remarks":"The paper's reference list is overwhelmingly to the author's own prior work, and the key Property 1 is imported from a self-citation without proof. This is not itself a reason to reject, but it does mean the novelty relative to the Node-list is limited to the extension to infrequent terms, which is where the correctness gap appears. The authors should be encouraged to make the manuscript self-contained. Also, the use of a single synthetic dataset from IBM Quest is a weak evaluation for a data structure intended for IR systems; real corpora (e.g., TREC, Wikipedia) would be more convincing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe group-list idea is a straightforward extension of the author's own Node-list to infrequent terms, applied to information retrieval. That's a reasonable and maybe useful thing to try, and the paper gives a clean example and simple construction algorithms. The writing is clear and the figures help.\n\nThe serious problem is Algorithm 3. The BAND query processing loop (lines 8–15) replaces each tuple in the accumulator with at most one descendant tuple from the next term's group-list. But a term can appear in multiple branches of the P-tree under the same ancestor — documents diverge after that ancestor. The correct intersection, as Property 1 states, is the union of all matching descendant tuples. The pseudocode keeps only one, dropping the documents in the other branches. Lines 17–19 then inherit that loss. So as written, Algorithm 3 does not compute the intersection the paper relies on. This is a correctness bug, not a stylistic issue.\n\nThe experiments don't help. The abstract and conclusion claim group-list outperforms the inverted index, but Tables 3 and 4 show the opposite for all three infrequent-term query groups (IQ2, IQ4, IQ6). The improvement shows up only for frequent-term queries, and even there the baseline is unspecified: no details on the inverted index implementation, no error bars, no statistical tests, no code or data. At least the space numbers are honest — the group-list is about the same size as the inverted index.\n\nWhat's actually new is extending Node-list to handle infrequent terms by packing them into leaf nodes. The construction is simple and the idea is not silly. But the correctness argument is inherited from [Deng and Wang 2010] without proof, and the multi-branch issue shows the inheritance doesn't transfer cleanly.\n\nMy take: this is not ready for peer review in its current form. The algorithm needs to be fixed or reformulated, the baseline needs to be described properly, and the claims need to be scoped to the regime where the method actually wins. If the author does that, it could become a short systems-style paper. As is, I'd reject with an invitation to revise.\n\nStill, it's a short paper with a clear bug, so it might be worth a quick look at a reading group if you want a concrete example of an intersection algorithm going wrong.","headline":"A clean write-up of a Node-list extension for IR, but Algorithm 3's intersection is incorrect, and the experiments only support a narrow claim.","tokens_in":8525,"tokens_out":7520,"would_cite":false,"duration_ms":73875,"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":"The group-list index claims to beat the inverted index on Boolean queries by grouping document identifiers inside a prefix tree.","keywords":["group-list","inverted index","Boolean query processing","intersection","union","prefix tree","frequent terms","data structure"],"falsifier":"Take the paper's own Example 1, or any small collection with at least two infrequent terms in one leaf node, enumerate the documents containing both terms by brute force, and run Algorithm 3. Any mismatch between the brute-force result and the algorithm's output invalidates Property 1 and with it the claimed correctness of the speed-up.","tokens_in":7543,"feed_emoji":"🗂️","tokens_out":6700,"duration_ms":68248,"temperature":0.7,"pith_summary":"This paper proposes the group-list, an index that stores each term's document identifiers as groups attached to nodes of a prefix tree, with each group labelled by the node's pre-order and post-order numbers. The paper claims that because documents are gathered into groups, Boolean AND and OR queries can be answered by intersecting or unioning groups rather than comparing individual document identifiers, which makes the group-list faster than the inverted index. The experiments on a synthetic collection with one million documents and one thousand distinct terms report large speed-ups on queries built from frequent terms or mixed terms, at the cost of slightly slower infrequent-term queries and roughly equal index size. A sympathetic reader would care because the group-list is described as being as simple and almost as compact as the inverted index, so the speed-up, if it generalises, offers a nearly drop-in replacement for the classic index.","feed_headline":"Group-list beats inverted index on frequent-term queries","feed_subtitle":"The group-list splits each term's postings into prefix-tree groups, accelerating Boolean queries while staying nearly the same size.","key_machinery":"The central object is the group-list itself: for each term, an ordered list of tuples `(pre-order, post-order)` paired with a set of document identifiers. The pre-order/post-order pair encodes a node of the prefix tree built over the document collection, and the did_set collects the documents containing the term that were inserted at that node. Ancestor–descendant tests between nodes are constant-time comparisons of these two numbers, so joining two group-lists reduces to checking code pairs rather than scanning posting lists. The paper's Algorithm 3 uses this code-intersection operation, borrowed from the node-list work, to intersect or union the did_sets of the query terms.","core_discovery":"The central claim is that the group-list, a variant of the inverted index where each term's document identifiers are divided into groups labelled by prefix-tree node codes, evaluates Boolean AND and OR queries faster than the inverted index. The paper establishes this by construction: every term's group-list is a sorted sequence of tuples `<pre-order, post-order> : did_set`; Property 1, inherited from the node-list, says that intersecting the group-lists of query terms and taking the union of did_sets returns exactly the documents containing all terms. Algorithm 3 then answers BAND queries by joining tuples through their pre-order/post-order codes instead of matching individual document ids, with BOR queries treated by union. On a synthetic collection of 1,000K documents and 1K distinct terms, the reported running times show the group-list several times faster than the inverted index on frequent-term queries (for example, at 90% threshold, FQ6 drops from 74.82 s to 13.76 s), slightly slower on infrequent-term-only queries, and almost equal in total size.","pith_inferences":["If Property 1 is verified for infrequent terms packed into shared leaf nodes, the group-list could replace the inverted-index posting list in existing engines with only an index-build change, because the query interface remains 'given terms, return doc ids'.","The reported advantage likely depends on the degree to which query terms co-occur in documents; a natural test is to vary the correlation structure of the synthetic generator or use real corpora to find the crossover point where group-based joining stops paying.","The same grouping construction based on pre-order/post-order codes could be applied to N-list, Nodeset, and DiffNodeset structures, which the paper mentions as future work, giving each of them the ability to index infrequent items."],"forward_implications":["BAND and BOR queries on frequent-term sets run several times faster: e.g., at 90% threshold FQ6 drops from 74.82 s to 13.76 s.","Since the group-list is nearly the same size as the inverted index (about 2.06 GB vs 2.01 GB on the synthetic collection), the speed-up is not bought with a large space penalty.","For queries consisting only of infrequent terms, the inverted index remains faster, so a practical system might keep both indexes or choose by query type.","Because tuples are grouped and sorted by pre-order, the structure is naturally suited to parallel or distributed query processing, as the paper notes as future work."],"supporting_citations":[{"why":"Defines the node-list structure that the group-list is identical to and supplies the proof methods for the inherited intersection property (Property 1).","marker":"[Deng and Wang 2010]"},{"why":"Provides the standard inverted-index query-processing framing that the paper adopts and compares against.","marker":"[Ottaviano and Venturini 2014]"},{"why":"Generates the synthetic collection Syn_data on which the reported timings are measured.","marker":"IBM Quest Synthetic Data Generator"}],"fun_headline_variants":["Group-list accelerates frequent-term Boolean queries","New data structure beats inverted index on frequent terms","Group-list: faster Boolean queries for frequent terms","Group-list trims Boolean query time on common terms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Property 1—intersecting group-lists and taking the union of the resulting did_sets returns exactly the documents containing all query terms—remains true when infrequent terms are packed into shared leaf nodes, since the paper only inherits the proof from an earlier node-list paper for frequent items.","fun_headline_variants_meta":{"raw":{"variants":["Group-list accelerates frequent-term Boolean queries","New data structure beats inverted index on frequent terms","Group-list: faster Boolean queries for frequent terms","Group-list trims Boolean query time on common terms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000552,"raw_usage":{"total_tokens":2561,"prompt_tokens":803,"completion_tokens":1758,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":419,"completion_tokens_details":{"reasoning_tokens":1700}},"tokens_in":419,"tokens_out":1758,"duration_ms":11686,"temperature":1.0,"reasoning_tokens":1700,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:40:32.007347+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's own Example 1, or any small collection with at least two infrequent terms in one leaf node, enumerate the documents containing both terms by brute force, and run Algorithm 3. Any mismatch between the brute-force result and the algorithm's output invalidates Property 1 and with it the claimed correctness of the speed-up.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the node-list structure that the group-list is identical to and supplies the proof methods for the inherited intersection property (Property 1)."},{"cited_title":"Ottaviano and R","cited_arxiv_id":null,"evidence_quote":"Provides the standard inverted-index query-processing framing that the paper adopts and compares against."}],"review_version":1}