Pith. sign in

REVIEW 4 major objections 5 minor 13 references

Beyond the Inverted Index

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The group-list index claims to beat the inverted index on Boolean queries by grouping document identifiers inside a prefix tree.

desk verdict 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. read the letter →

arxiv 1908.04517 v1 pith:KT3UFLUL submitted 2019-08-13 cs.DS cs.DB

Zhi-Hong Deng This is my paper · ORCID
classification cs.DScs.DB
keywords group-listinvertedindexBooleanqueryprocessingintersectionunionprefixtreefrequenttermsdatastructure
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Section 3, Algorithm 3, lines 8-15] 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.
  2. [Section 3, Algorithm 3] 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.
  3. [Section 4, Tables 3 and 4] 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.
  4. [Section 2, Property 1] 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.
minor comments (5)
  1. [Section 3] 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.
  2. [Section 4] 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).
  3. [Section 3] 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.
  4. [Section 4] 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.
  5. [Figures] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the group-list is explicitly built on the author's independently published Node-list, and the claimed speedup is measured against the inverted index, not derived from fitted inputs.

full rationale

The claimed derivation chain is not circular. The group-list is defined as an extension of the author's Node-list, and the paper explicitly says 'the group-list is the same as the node-list [Deng and Wang 2010]' and that it 'naturally possesses' Node-list properties. Property 1 and the code-intersection routine are cited to Deng and Wang (2010), a published, parameter-free result whose assumptions do not include the group-list or the present performance numbers; that is independent support, not a self-referential reduction. The central performance claim is an empirical comparison against the standard inverted index on a synthetic dataset (Tables 3-4), with no parameter fitted to the query workload and then reported as a prediction. Algorithm 3's correctness does depend on Property 1, which is not proved in this paper and is instead inherited by 'proof methods' from the self-citation, and the text also references a nonexistent 'Algorithm 4' for infrequent-term intersection; these are proof/completeness gaps and potential correctness risks, but they are not circularity because no equation or fitted value reduces the output to the input. The paper is therefore self-contained against an external baseline for its performance claim.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central algorithmic content is largely inherited from the author's prior Node-list work, and the empirical claim relies on an unspecified inverted index baseline and a single synthetic dataset. No new physical or mathematical entities are introduced.

free parameters (1)
  • percentage threshold ζ = 81% and 90%
    Hand-chosen threshold that defines which terms are frequent; it changes the P-tree shape and the number of tuples in the group-list, and the performance comparison is reported for these two values only.
assumptions (4)
  • domain assumption Property 1: the group-list of a termset, obtained by intersecting the group-lists of its terms, contains exactly the documents containing all terms.
    Stated in Section 2 without proof; deferred to [Deng and Wang 2010]. The correctness of Algorithm 3 depends on it, and its validity for infrequent terms in shared leaf nodes is not demonstrated.
  • standard math Pre-order/post-order ancestor test (pre(A) < pre(B) and post(A) > post(B) iff A is an ancestor of B).
    This is a standard tree property, invoked through references to [Deng and Wang 2010] for the code-intersection method.
  • domain assumption The P-tree constructed by Algorithm 1 correctly records the document sets for each term.
    No correctness proof is given for the construction; the paper relies on this to claim the group-list contains the same document identifiers as the inverted index.
  • domain assumption The synthetic dataset generated by the IBM Quest generator is representative enough to support the claimed performance advantage.
    Section 4 uses only this dataset; no real corpora are tested.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond the Inverted Index." pith.science (2026). https://pith.science/paper/KT3UFLUL

@misc{pith2026190804517,
  author       = {Pith},
  title        = {Pith review of: Beyond the Inverted Index},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KT3UFLUL}},
  note         = {Machine review of arXiv:1908.04517}
}
read the original abstract

In this paper, a new data structure named group-list is proposed. The group-list is as simple as the inverted index. However, the group-list divides document identifiers in an inverted index into groups, which makes it more efficient when it is used to perform the intersection or union operation on document identifiers. The experimental results on a synthetic dataset show that the group-list outperforms the inverted index.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    [Aryabarzan et al. 2018] N. Aryabarzan, B. Minaei-Bidgoli, and M. Teshnehlab. negFIN: An efficient algorithm for fast mining frequent itemsets. Expert Systems with Applications, 105: 129-143,

    work page 2018

  2. [9]

    Lemire and L

    [Lemire and Boytsov 2013] D. Lemire and L. Boytsov. Decoding billions of integers per second through vectorization. Software: Practice & Experience,

    work page 2013

  3. [13]

    2017] B.Vo, S

    [Vo et al. 2017] B.Vo, S. Pham, T. Le , and Z. H. Deng. A novel approach for mining maximal frequent patterns. Expert Systems with Applications, 73: 178-186,

    work page 2017

  4. [2000]

    Ottaviano and R

    [Ottaviano and Venturini 2014] G. Ottaviano and R. Venturini. Partitioned Elias -Fano Indexes. In SIGIR 2014,pages: 273-282. [Salomon 2007] D. Salomon. Variable-length Codes for Data Compression. Springer,

    work page 2014

  5. [2007]

    [Stepanov et al. 2011] A. A. Stepanov, A. R. Gangolli, D. E. Rose, R. J. Ernst, and P. S. Oberoi. Simd -based decoding of posting lists. In CIKM 2011, pages 317-326. [Yan et al. 2009] H. Yan, S. Ding, and T. Suel. Inverted inde x compression and query processing with optimized document ordering. In WWW 2009, pages 401-410. [Vo et al. 2016] B. Vo, T. Le, F...

    work page 2011

  6. [2010]

    [Deng et al. 2012] Z. H.Deng , Z. H. Wang, and J. J. Jiang. A New Algorithm for Fast Mining Frequent Itemsets Using N -Lists. SCIENCE CHINA Information Sciences, 55(9), 2008 – 2030,

    work page 2012

  7. [2012]

    [Han et al. 2019] X. X.Han, X. M. Liu, J. Chen, G. J. Lai, H. Gao, J. Z. Li. Efficiently Mining Frequent Itemsets on Massive Data. IEEE ACCESS, 7:31409-31421,

    work page 2019

  8. [2013]

    Moffat and L

    [Moffat and Stuiver 2000] A. Moffat and L. Stuiver. Binary interpolative coding for effective index compression. Information Retrieval, 3(1),

    work page 2000

Show all 13 references
  1. [2014]

    [Deng and Lv 2015] Z. H. Deng and S. L. Lv. PrePost+: An efficient N -Lists-based Algorithm for Mining Frequent Itemsets via Children-Parent Equivalence Pruning. Expert Systems with Applications, 42(13): 5424 - 5432,

    2015

  2. [2015]

    [Deng and Wang 2010] Z. H. Deng and Z. H.Wang. A New Fast Vertical Method for Mining Frequent Itemsets. International Journal of Computational Intelligence Systems, 3(6), 733 – 744,

    2010

  3. [2016]

    [Deng and Lv 2014] Z. H. Deng and S. L. Lv. Fast mining frequent itemsets using Nodesets. Expert Systems with Applications, 41(10), 4505 - 4512,

    2014

  4. [2018]

    [Deng 2016] Z. H. Deng. DiffNodesets: An efficient structure for fast mining frequent itemsets. Applied Soft Computing, 41, 214-223,

    2016

  5. [2019]

    [Huynh et al. 2019] B. Huynh, C. Trinh, V. Dang, and B. Vo. A Parallel Method For Mining Frequent Patterns With Multiple Minimum Support Thresholds. International Journal Of Innovative Computing Information And Contr ol, 15(2): 479-488,

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.