{"id":"33295909-657d-4a45-9036-0b79937fb212","arxiv_id":"2507.01696","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A dynamic data structure maintains approximate kernel density estimates for all query points and a sparse similarity graph under point insertions, with n^(1/4+o(1)) amortized update time for the Gaussian kernel.","lead":"This paper presents fast algorithms for updating kernel density estimates and similarity graphs when new data points arrive over time. For the Gaussian kernel, each update costs around n^0.25 amortized operations instead of rebuilding everything from scratch.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma C.2 reverses Lemma B.1 and is false: in a sphere configuration the expected number of query points colliding with a new data point is n^{1-o(1)}, not eO(2^j μ_i), so E|A|=eO(1) and the n^{1/4+o(1)} graph-update time are unsupported.","rationale":"The reader's weakest assumption (d=O(log n)) is a limitation, but it does not invalidate the theorems under the stated assumption. A more serious, internal problem is in the proof of the dynamic similarity graph theorem: Lemma C.2, the formal version of Lemma 4.5, asserts a bound that is false. The proof reverses Lemma B.1, which is valid only for counting data points around a fixed query, not queries around a fixed new point. The sphere counterexample above satisfies the paper's assumptions (d=O(log n) via JL, 1≤μ_q≤n, Gaussian kernel) and shows the expected number of colliding queries can be n·2^{-(j+1)}, which for j<log n is superconstant and can be as large as n^{1-o(1)}. Since Lemma C.3's E|A|=eO(1) is derived from Lemma C.2, the claimed expected update time n^{o(1)}cost(k) for UPDATE GRAPH is unsupported, and the data structure can, on a single insertion, update Ω(n) query estimates in the root KDE structure. This is not a stylistic or presentational gap; the central claim of the first dynamic sparse similarity graph with sublinear update time fails with the stated algorithm. The dynamic KDE contribution (Theorem 3.1) may still be valuable, and a revised algorithm could possibly add significance checks before updating queries, but as written the main contribution does not hold. Hence the conditional acceptance should be changed to reject pending a corrected analysis.","tokens_in":35901,"tokens_out":37123,"duration_ms":437667,"concrete_test":"Analytically verify (C.2) on the sphere construction: set n=2^{2j}, let X consist of n points on a sphere of radius r with Gaussian bandwidth σ satisfying e^{-r^2/σ^2}=2^{-j}, and insert z at the sphere centre. For μ_i=1, j, compute the expected size of {q∈T'.kde.Q_{μ_i}: H(z)=H(q)}. Since all q are within distance r_j, Lemma 2.5 gives collision probability at least p_{near,j}^{k_j}, and K2_j=200 log n·p_{near,j}^{-k_j} recovers each q with probability 1-o(1); the LHS is at least n·p_{near,j}^{k_j} = n^{1-o(1)}, while the claimed RHS is O(2^j)=n^{o(1)}. If this calculation reproduces the failure of (4.2), Lemma C.3 and Theorem 4.1's update time cannot stand.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 4.1's update time rests on Lemma 4.5 / C.2, which bounds the expected number of query points q in T'.kde.Q_{μ_i} whose LSH bucket matches the new point z by eO(2^{j+1} μ_i). The proof's step (C.2) is obtained by applying Lemma B.1 with the roles of data and query points swapped. Lemma B.1 bounds, for a fixed query q, the expected number of data points x with H(q)=H(x), using |L_q^{j'}| ≤ 2^{j'} μ_q. It gives no bound on the number of queries q with H(z)=H(q) for a fixed z; the collision probability is symmetric, but the count bound is not. Concretely, fix j and take n=2^{2j} points on a sphere of radius r with e^{-r^2/σ^2}=2^{-j}, in dimension O(log n). Pairwise distances are ≈√2 r, so pairwise kernel values are ≈2^{-2j}, giving μ_q≈1 for every q. Then all n points lie in L_z^j, and for the iteration μ_i≈1, j, the sampling probability is 2^{-(j+1)}, while each q is recovered with probability 1-o(1) because K2_j=200 log n · p_{near,j}^{-k_j}. The expected number of recovered queries is therefore n·2^{-(j+1)} = 2^{j-1}, which is ω(1) and, for j=ω(log log n), much larger than the claimed eO(2^j μ_i)=eO(2^j). Hence Lemma C.2 is false, E|A|=eO(1) in Lemma C.3 is unsupported, and the expected update time n^{o(1)}cost(k) in Theorem 4.1 does not follow; the algorithm as written can spend polynomial time updating a single insertion.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces dynamic data structures for kernel density estimation (KDE) and approximate similarity graph construction under data-point insertions. The KDE structure maintains (1±ε)-approximate estimates for a set of query points, with an amortised update time of ε^{-2} n^{o(1)} cost(k) (Theorem 3.1), improving over full recomputation and being independent of the number of queries. The graph structure maintains a cluster-preserving sparse approximation of the fully connected similarity graph, with expected amortised update time n^{o(1)} cost(k) (Theorem 4.1), which for the Gaussian kernel is n^{1/4+o(1)}. The algorithms build on CKNS (Charikar et al., 2020) and Macgregor & Sun (2023), adding query-hash data structures and path-tracking to enable dynamic updates. The paper also reports experiments on several datasets. The proofs are detailed, but several load-bearing steps have gaps, most notably the derivation of the expected number of colliding query points in Lemma C.2 and the concentration argument in Lemma B.7.","tokens_in":36293,"tokens_out":23526,"duration_ms":246473,"significance":"If the main theorems are correct, the results are significant: a dynamic KDE algorithm whose update time does not grow with the number of queries, and a dynamic approximate similarity graph with sublinear expected update time, are new contributions. The paper provides an LSH-based framework with explicit algorithmic procedures, and the empirical section demonstrates scalability on some datasets. The strengths include the clear problem formulation, the use of established static machinery (CKNS and Macgregor & Sun with appropriate reweighting), and the availability of open-source code. However, the significance is contingent on repairing the technical gaps in the time-complexity proofs; as written, the theoretical guarantees are not fully established.","major_comments":[{"comment":"The proof of Lemma C.2 applies Lemma B.1 with the roles of data points and query points swapped. Lemma B.1 bounds, for a fixed query q, the expected number of data points x with H(q)=H(x), using the geometric level bound |L_q^{j'}| ≤ 2^{j'} μ_q. It does not supply a bound on the expected number of query points q with H(z)=H(q) for a fixed z. The subsequent steps (C.3)–(C.5) depend on this swapped bound, so the inequality E[|{q ∈ T'.kde.Q_{μ_i} : H(z)=H(q)}|] = eO(μ_i 2^{j+1}) is not established by the cited lemma. The authors need to give a direct proof, for example by partitioning the queries into weight levels relative to z and using Lemma 2.4 with the kernel-cost definition, or otherwise demonstrating that the restriction q ∈ Q_{μ_i} controls the count. The stress-test counterexample in the anonymous report appears inconsistent with Lemma 2.4 (the stated combination n=2^{2j} and μ_q≈1 with all points at level j violates |L_q^j| ≤ 2^j μ_q), but the proof gap is real and load-bearing for Lemma C.3 and Theorem 4.1.","section":"Section C.2"},{"comment":"The proof of Lemma B.7 applies the Chernoff bound to the sum of indicators Y^q_{a,t} across t, but the events E^q_{a,t} are not independent over time: the same hash functions are reused across insertions, and the evolving data structure is deterministic given the randomness. No martingale or negative-dependence argument is provided. A Markov bound would only give a constant-probability guarantee, whereas the derivation in Section B.3 (proof of Theorem 3.1) requires the high-probability statement U_q^T = eO(1) to obtain the claimed amortised bound with high probability. The authors should either supply a valid concentration argument or restate the amortised time guarantee as an expectation bound.","section":"Section B.2"},{"comment":"Assumption 2.1 sets d = O(log |X_t|) based on the JL lemma, but the JL lemma preserves distances only up to (1±ε), which does not generally preserve Gaussian (or other smooth) kernel values multiplicatively for far-apart pairs; a small relative distance change induces a large relative error in the kernel value. Consequently the theorems as stated are silent for the high-dimensional datasets used in the experiments (cifar10 d=2048, mnist d=728, glove d=100). The paper should clarify whether the analysis is intended for data that are already low-dimensional, or whether an additional kernel-preserving dimension reduction is assumed; otherwise the practical claims in the experimental section are not supported by the theoretical results.","section":"Section 2.4"},{"comment":"The correctness proof of CONSTRUCT GRAPH is not given explicitly; the text states that the analysis of Macgregor & Sun (2023) can be followed after replacing b̂p(i,j) with b̂w(i,j), since the two are within a constant factor. This is a nontrivial substitution: the constant-factor bound alone does not automatically preserve the required cluster-conductance and eigenvalue-gap conditions in Definition A.3, because those conditions depend on the exact sampling probabilities and edge weights. The authors should either provide the details of the carrying-over argument or state precisely which lemmas of the static paper apply unchanged and what verification is needed for the modified reweighting.","section":"Section C.1"}],"minor_comments":[{"comment":"Line 23 of Algorithm 1 calls DELETE FROMDATA(z) but the parameter is the query point q; the name should be consistent (e.g., DELETE QUERY POINT(q)), since 'z' elsewhere denotes a data point.","section":"Algorithm 1"},{"comment":"The second sentence of the proof says 'the data points XL ≜ T ′′.left.data and XR ≜ T ′′.left.data'; the second of these should be T ′′.right.data.","section":"Lemma C.1"},{"comment":"The statement lists 'with high probability' for the amortised update time, but the proof in Section B.3 derives the bound through an amortised accounting that itself relies on the high-probability statement of Lemma B.7; the dependency between these probabilistic guarantees should be made explicit.","section":"Section 3"},{"comment":"The reported relative errors for the proposed algorithm on some datasets are noticeably worse than the DYNAMIC RS baseline (e.g., census 0.102 vs 0.005, covtype 0.196 vs 0.018); the text's statement that the algorithm 'maintains low relative errors' is accurate only when compared with CKNS, so the description should be more balanced.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Steinar, Peter, and He Sun have a real result here. The paper gives the first dynamic KDE algorithm that maintains (1±ε) estimates for all queries under insertions, and leverages that to maintain a sparse similarity graph with n^{1/4+o(1)} expected amortised update time for the Gaussian kernel. The two new components—the query-hash that locates affected queries, and the path-resampling tree that reweights only affected edges—are genuinely new, and the main theorems are plausible extensions of CKNS and Macgregor-Sun.\n\nI checked the stress-test note claiming Lemma C.2 is false. That objection doesn't land. The sphere example misplaces the geometric level: with pairwise distances √2 r, the kernel is 2^{-2j}, not 2^{-j}, so all points sit in L_z^{2j}, not L_z^j. And the computed expectation 2^{j-1} is well within the claimed eO(2^j) bound once μ_i≈1. So the central update-time theorem isn't obviously broken.\n\nThe real soft spots are smaller. Lemma B.7 applies a Chernoff bound to update indicators that are not clearly independent across time; the hash functions are fixed and the incoming points are adversarial, so that concentration argument needs repair or a different approach. I would also want the graph initialisation proof checked against Macgregor-Sun, since the paper delegates with only a reweighting-factor substitution. The d=O(log n) assumption is explicit but the experiments run at d=100–2048, so the theory does not cover the empirical regime; the paper should say this clearly. And the abstract's \"low relative errors\" is not really what Table 1 shows—the dynamic KDE algorithm is often less accurate than DynamicRS, though much faster on large data; that should be described as a speed-accuracy tradeoff.\n\nBottom line: the paper deserves a serious referee. The main technical advance is real, the proofs are mostly detailed, and the one potentially fatal objection I saw doesn't hold up. I'd send it out with requests to fix the concentration argument in Lemma B.7 and to tighten the experimental claims. It belongs at a theory venue, and I'd cite it if I worked on dynamic KDE or similarity graph maintenance.","headline":"Real dynamic KDE and similarity-graph results with a solid main proof, a Chernoff gap in Lemma B.7, and a stress-test objection that does not hold up.","tokens_in":36844,"tokens_out":6450,"would_cite":true,"duration_ms":71467,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W25","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that kernel density estimates can be maintained under data insertions with amortised update time ε^-2 · n^o(1) · cost(k), and that this yields the first dynamic approximate similarity graph with sublinear update time.","keywords":["kernel density estimation","dynamic data structures","similarity graph","spectral clustering","locality-sensitive hashing","sublinear update time","Gaussian kernel","JL lemma"],"falsifier":"Take a dataset with dimension d much larger than log n, insert points one at a time, and measure the wall-clock per-insertion cost and the maximum relative KDE error at every query point; if the per-insertion cost grows with d or the (1 ± ε) error guarantee degrades, then Assumption 2.1 is violated and Theorem 3.1's stated bound does not hold as written.","tokens_in":35671,"feed_emoji":"⏱️","tokens_out":3988,"duration_ms":48608,"temperature":0.7,"pith_summary":"The paper tries to establish that the static KDE framework of Charikar et al. can be made fully dynamic under data point insertions, while preserving (1 ± ε)-approximate estimates for every maintained query point. The key gain is that updating one new data point costs only $ε^{-2}$ · n^o(1) · cost(k), which is independent of the number of query points, instead of recomputing all estimates. For the Gaussian kernel this is n^(1/4+o(1)) per insertion, and the paper further argues this powers a dynamic sparse similarity graph with expected amortised update time n^o(1) · cost(k), preserving cluster structure for downstream spectral clustering. If correct, these are the first dynamic KDE and first dynamic sparse similarity graph constructions under insertions with such sublinear guarantees.","feed_headline":"Per-insertion KDE updates drop to n^(1/4+o(1))","feed_subtitle":"A query-hash structure keeps (1±ε) estimates for every point as data streams in, and powers a dynamic similarity graph.","key_machinery":"The load-bearing objects are the geometric weight levels L_j^q, which partition data points by their kernel distance to a query, and a carefully maintained query hash: buckets B*_{H_{μ_i,a,j,ℓ}}(q) that store query points under the same LSH functions used for data buckets. This pairing lets ADDDATAPOINT(z) find exactly the query points whose estimates should incorporate z without scanning all queries. For the graph result, the central mechanism is a complete binary tree T where each internal node stores a dynamic KDE structure and each sampled neighbour of a vertex corresponds to a stored sampling path P_{x,ℓ}; updates resample only the paths whose estimated densities changed, with the number of resampled paths shown to be eO(1) in expectation.","core_discovery":"The central claim is that the CKNS hash-based KDE estimator can be extended to the streaming-insertion setting by maintaining a parallel structure of query-hash buckets. When a new data point z arrives, the procedure samples z into the existing data buckets exactly as a full re-initialisation would, then recovers precisely those query points whose estimates would have changed, updating their KDE values in place. This gives amortised update time $ε^{-2}$ · n^o(1) · cost(k), and the same machinery supports inserting and deleting query points. The paper then builds a complete binary tree whose internal nodes hold such dynamic KDE structures, samples L neighbours per vertex through the tree, and stores the sampling paths so that after inserting z it can resample only the affected paths; this maintains an approximate similarity graph (a cluster-preserving sparsifier) with expected amortised update time n^o(1) · cost(k), which is n^(1/4+o(1)) for the Gaussian kernel.","pith_inferences":["The paper's theory assumes d = O(log n) via the JL lemma, but its own experiments run at d = 728, 2048 and 100; extending the analysis to genuinely high-dimensional data without projection is an open gap implicit in the paper.","The update machinery handles data insertions and query insertions/deletions but not deletion of data points; a streaming setting with arbitrary deletions would require additional rebuilding arguments beyond the ones given.","Because the cost(k) term varies by kernel, the same dynamic structure would give an n^o(1) update time for the t-student kernel and n^(4/27+o(1)) for the exponential kernel, which the paper states but does not test experimentally.","The maintained KDE tree effectively offers a dynamic sampling-by-kernel-weight primitive, so it could be reused as a building block for dynamic versions of other similarity-graph and kernel-matrix algorithms, an extension the paper only gestures toward in its conclusion."],"forward_implications":["For the Gaussian kernel, each new data point can be incorporated in n^(1/4+o(1)) amortised time while keeping (1 ± ε) KDE estimates for every query point, independent of how many query points are maintained.","The dynamic KDE data structure supports insertion and deletion of query points, with each new query point estimated at ε^-2 · n^o(1) · cost(k) cost.","An approximate similarity graph with eO(n) edges can be maintained under insertions, and as long as the data set has a clear cluster structure the maintained graph preserves the conductance-cluster structure of the fully connected graph.","Spectral clustering can therefore be run dynamically: the paper reports competitive normalised mutual information on real datasets while updating the graph much faster than recomputing the fully connected or k-nearest-neighbour graphs.","The amortisation rests on rebuilding the whole structure only when the data size doubles, so the per-step cost stays sublinear across a long insertion sequence."],"supporting_citations":[{"why":"Supplies the static CKNS KDE framework, the geometric weight levels L_j^q, and the kernel cost function cost(k) that the dynamic structure preserves.","marker":"Charikar et al. (2020)"},{"why":"Provides the static approximate similarity graph construction whose tree sampling and cluster-preserving sparsifier analysis the dynamic graph update extends.","marker":"Macgregor & Sun (2023)"},{"why":"Shows how to maintain the CKNS buckets under a point replacement, the dynamic-update pattern that ADDDATAPOINT adapts to pure insertions.","marker":"Liang et al. (2022)"},{"why":"Gives the LSH collision probability bounds and the parameter ρ that control the number of hash repetitions in the bucket structures.","marker":"Andoni & Indyk (2008)"},{"why":"The JL lemma is the basis of Assumption 2.1, which lets the paper omit the dimension d from all runtime bounds.","marker":"Johnson (1984)"},{"why":"Provides the Euclidean LSH family whose near/far collision probabilities are used to separate nearby from distant points in the kernel value levels.","marker":"Datar et al. (2004)"}],"fun_headline_variants":["Streaming KDE powers dynamic similarity graph","Dynamic KDE with n^(1/4+o(1)) per insertion","Keeping KDE estimates fresh as data arrives","Query-hash structure speeds dynamic spectral clustering","Sublinear update for kernel density estimates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The runtime bounds assume that every data set can be treated as living in d = O(log n) dimensions via a JL projection that preserves the kernel values and cluster structure, and if that projection fails for real high-dimensional data the claimed n^(1/4+o(1)) update time does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Streaming KDE powers dynamic similarity graph","Dynamic KDE with n^(1/4+o(1)) per insertion","Keeping KDE estimates fresh as data arrives","Query-hash structure speeds dynamic spectral clustering","Sublinear update for kernel density estimates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000334,"raw_usage":{"total_tokens":1842,"prompt_tokens":919,"completion_tokens":923,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":535,"completion_tokens_details":{"reasoning_tokens":850}},"tokens_in":535,"tokens_out":923,"duration_ms":126877,"temperature":1.0,"reasoning_tokens":850,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:46:07.574714+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a dataset with dimension d much larger than log n, insert points one at a time, and measure the wall-clock per-insertion cost and the maximum relative KDE error at every query point; if the per-insertion cost grows with d or the (1 ± ε) error guarantee degrades, then Assumption 2.1 is violated and Theorem 3.1's stated bound does not hold as written.","supporting_citations":[{"cited_title":"Kernel density estimation through density constrained near neighbor search","cited_arxiv_id":null,"evidence_quote":"Supplies the static CKNS KDE framework, the geometric weight levels L_j^q, and the kernel cost function cost(k) that the dynamic structure preserves."},{"cited_title":"and Sun, H","cited_arxiv_id":null,"evidence_quote":"Provides the static approximate similarity graph construction whose tree sampling and cluster-preserving sparsifier analysis the dynamic graph update extends."},{"cited_title":"Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory","cited_arxiv_id":"2208.03915","evidence_quote":"Shows how to maintain the CKNS buckets under a point replacement, the dynamic-update pattern that ADDDATAPOINT adapts to pure insertions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The JL lemma is the basis of Assumption 2.1, which lets the paper omit the dimension d from all runtime bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Euclidean LSH family whose near/far collision probabilities are used to separate nearby from distant points in the kernel value levels."}],"review_version":1}