- Rating
- 2
- Confidence
- 4(+1)
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes a SMinHash, which represents embeddings by repeatedly sampling a shared reference set and recording the index of the nearest reference in each set. The paper establishes a finite reference conflict expression that incorporates shared order relations, conditional locality, and candidate word accuracy guarantees, as well as a bound that correlates reference coverage and concentration with bucket load. Experimental results show that this method achieves higher candidate word selectivity compared to spherical reference control.
Critical strengths
- This paper clearly distinguishes between fixed-pair collision probability, geometric locality, candidate precision, and fitted bucket concentration. Its handling of shared order relationships and counterexamples demonstrate that data-derived references do not necessarily produce balanced buckets, providing relevant evidence.
- Experimental results show that on the QQP dataset, SMinHash retains approximately 99.48% of cosine positive sample pairs while allowing 0.338% of independent background probe sample pairs. Furthermore, reporting recall failures, full execution costs, and adverse results enhances the credibility of the evaluation.
Critical weaknesses
- Despite its length and complexity, this paper offers limited methodological innovation. For example, Equation (1) explicitly applies WTA hashing to negative reference distances. However, distance feature interpretation, binary MinHash specialization, and a strict order collision expression already exist in the cited WTA work. Similarly, Section 5, with its specified full-pool, row-by-row setting, is essentially equivalent to single-probe DFLSH. In essence, this paper enhances its contribution through a large amount of additional analysis. Therefore, in my opinion, this extension considering relevant factors and its associated analytical improvements do not represent a sufficiently significant improvement compared to existing methods.
- The experimental results did not yield satisfactory performance improvements. SMinHash failed to achieve the 95% recall target in all three fits across four of the eight datasets, particularly on the DBpedia and COYO datasets, where, despite its superior performance, it still fell short of the quality target (Table 18). Furthermore, regardless of whether SMinHash completed the task, its graph construction speed was slower than Flat and IVF-Flat, and it exceeded the release budget on the GIST and NYTimes datasets (Table 11). While the proposed SMinHash outperforms in some experimental results, its applicability is limited. Specifically: (1) the cost of constructing additional connections is reduced on the COCO and Deep datasets; (2) both are essentially the same on the SIFT dataset; (3) IVF is superior on the NYTimes dataset; and (4) IVF is faster during the query phase on all four datasets (Table 12). Therefore, in summary, while the experimental results show some improvement, there is a lack of clear, usable practical application value to compensate for the lack of theoretical innovation.
Questions for authors
- Of the reported selected operating points, is there any that can provide quantitative guarantees of locality, candidate accuracy, or workload based on Theorem 3.3, Corollary 3.4, or Proposition 3.2?
- Regarding the join results of COCO and Deep, can the authors demonstrate whether the overall cost advantage still exists when the recall is comparable and the index building cost is amortized across repetitive workloads?
rebuttal
Thanks for your review and comments.
A1: Even good coverage can send many objects to the same reference; Proposition 3.2 exposes the two sources through reverse-neighbor concentration plus the number of uncovered objects. Continuous counterexamples further rule out duplicates or distance ties as necessary explanations of concentration: with ambient dimension 257, N=65,536, ψ=1024, and T=100, at least one coordinate bucket among the 100 rounds contains more than 95% of the objects with probability greater than 0.999 over the joint data and encoder draws. A separate construction shows that sparse true threshold output can coexist with quadratic candidate work.
A2: The new experiments add joint checks of achieved quality and complete cost. In Table 4, all three Deep99 fits meet the quality-matching rule, and SMinHash has lower mean total cost at every measured reuse count, with construction reuse measured directly. COCO, DBpedia, and COYO, three of the datasets that failed in the original table, plus Deep all reach actual returned Recall@10≥95% at the new band-OR T=50 points (Table 23). Semantic screening supplies a complementary use. On identical MiniLM representations, both methods retain at least 99% of cosine-positive QQP pairs in every fit, while SMinHash produces approximately 37.2 times fewer candidates than embedding hyperplanes. On MRPC it retains more human positives with about one quarter of the candidates (Table 39). This reduces pairs reaching an existing semantic decision rule; Table 2 further demonstrates actual query and retained-state benefits in the evaluated hashing pipeline.
A3: We have not established guarantees certifying useful locality, candidate precision, or the execution budget for the selected retrieval/join points.
A4: Mean total cost remains lower at all three measured reuse counts, with the benefit narrowing as reuse increases. SMinHash/IVF-Flat mean edge recalls are 99.141%/99.106%; every fit reaches 99%, each gap satisfies the predeclared 0.5-percentage-point tolerance, and every output has precision 1. One actual construction plus K=1/4/16 complete joins costs 0.545/0.797, 2.030/2.315, and 8.009/8.455 s, respectively (Table 4). Every repetition regenerates complete outputs without caching final edge sets; SMinHash is faster in all three fits at K=1 and 4, and in two fits at K=16. Per-fit results appear in Table 32.