Pith. sign in

REVIEW 1 major objections 4 minor 61 references

Estimating Size of the Union of Sets in Streaming Model

T0 review · 1 major / 4 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read A simple adaptive sampler estimates the size of a stream of union-of-sets whenever each set can be counted, sampled, and tested for membership quickly.

desk verdict Clean adaptive sampler that actually settles the linear-in-d update-time open problem for streaming discrete Klee, with a Lean-checked analysis and a useful unifying abstraction. read the letter →

arxiv 2607.26997 v1 pith:ET56IGBV submitted 2026-07-29 cs.DS cs.CG

Kuldeep S. Meel , N. V. Vinodchandran , Sourav Chakraborty This is my paper · ORCID
classification cs.DScs.CG MSC 68W2768W2068Q25
keywords streamingalgorithmsunionofsetsDelphicKlee'smeasureproblemDNFmodelcountingcombinatorialtestingadaptivesamplingF0estimation
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

Many streaming problems amount to estimating how many distinct elements appear across a long sequence of implicitly defined sets. The paper isolates a clean sufficient condition—called Delphic sets—under which three black-box operations (size, uniform sample, membership) run in logarithmic time, and shows that three classical tasks fall inside this class: discrete Klee’s measure (volume of axis-aligned boxes), combinatorial test-coverage, and DNF model counting. It then gives a single adaptive-sampling algorithm, APS-Estimator, that maintains a small random sketch of the union seen so far, thinning the sketch whenever it grows too large. The algorithm returns an (ε,δ)-approximation using space linear in the sketch size and update time that is only linear in dimension for boxes. Because the same routine works for all three problems, the paper simultaneously settles an open question on multi-dimensional streaming volume and supplies practical streaming estimators for coverage and DNF counting.

What carries the argument

APS-Estimator: an adaptive sketch that keeps every element of the current union independently with a dynamically halved probability p, removing then re-sampling on each new set so that the invariant is restored, and thinning the entire sketch by 1/2 whenever its size exceeds a Chernoff threshold.

What would settle it

Implement APS-Estimator on a stream of random d-dimensional boxes for moderate d and M, compute the true union volume exactly (or by a slower exact method), and check whether the fraction of runs whose relative error exceeds ε is at most δ; a systematic excess would falsify the claimed concentration.

Watch

Extended reading notes

Core claim

There exists a streaming algorithm APS-Estimator that, given any stream of Delphic sets, outputs an (ε,δ)-approximation of the cardinality of their union using worst-case space O(R log|Ω|) and update time O(R log R · log(M/δ) · log|Ω|), where R = O(log(M/δ)·ε^{-2}). Instantiated on axis-aligned boxes this is the first algorithm whose update time depends only linearly on dimension.

Load-bearing premise

The argument that the real algorithm and an idealized immediate-sample version stay coupled on the same random bits, so that any failure of the real algorithm is already charged either to a coupon-collector abort or to a concentration failure of the idealized process.

Editorial extensions

If this is right

  • Discrete Klee’s measure in the streaming model now admits update time linear in dimension, closing the exponential-in-d gap left by earlier sketching approaches.
  • The same black-box routine immediately yields streaming (ε,δ)-approximators for combinatorial t-way coverage and for the number of models of a DNF formula whose terms arrive one-by-one.
  • A second hashing-based estimator for coverage trades the linear-in-log(M) space for near-optimal space at the price of NP-oracle calls per update, exhibiting an explicit time–space trade-off.
  • Any future problem whose sets support fast size/sample/membership queries inherits the same space and update bounds without further algorithmic work.

Reading between the lines

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

  • Because the analysis treats the three Delphic primitives as black boxes, the same sampler can be dropped into any domain (geometric, combinatorial, logical) once those primitives are supplied, suggesting a reusable library pattern.
  • The residual logarithmic dependence on stream length M is inherited from the adaptive thinning schedule; removing it would simultaneously improve distinct-elements, coverage, and DNF counting.
  • The Lean 4 formalization already discharged the coupling step; any later extension to turnstile streams or higher frequency moments can reuse that verified core.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper introduces Delphic sets—families closed under efficient membership, uniform sampling, and counting—and gives a simple adaptive sampling algorithm (APS-Estimator) that returns an (ε,δ)-approximation of the cardinality of the union of a stream of such sets. Space is O(R log|Ω|) and per-item update time is O(R log R · log(M/δ) · log|Ω|) with R = O(log(M/δ)·ε^{-2}). The framework specializes to discrete streaming Klee’s measure (first algorithm whose update time is linear in dimension d for d>1, settling an open question of Tirthapura–Woodruff), combinatorial test-coverage estimation, and streaming DNF model counting. A second, hashing-based estimator for coverage trades near-optimal space for P^NP update time. The revised manuscript reports a Lean 4 formalization of the main algorithm and its correctness argument.

Significance. If correct, the result is a clean and practically usable advance: it unifies three previously separate streaming problems under a single black-box interface, supplies the first linear-in-d update-time algorithm for multi-dimensional discrete Klee’s measure, and does so with an elementary sampling analysis rather than range-efficient sketches. The explicit Lean 4 machine-checked proof of APS-Estimator and the transparent constant derivation for thr_0 are genuine strengths that lower residual risk and make the work easy to reuse. The time–space trade-off for coverage estimation is a useful secondary contribution. Overall the paper is a strong candidate for a theory journal that values simple, implementable streaming algorithms with rigorous guarantees.

major comments (1)
  1. [§4.1 (Observation 4.1, Algorithms 1–3)] §4.1, Observation 4.1 and the surrounding coupling: the written argument equates APS-Estimator with Naive under a shared random tape, yet the control flow for when p is halved differs (APS thins the pending binomial N_i before DistinctSample; Naive samples immediately and then thins). The published text also contains garbled phrasing (“after the loop 5–7). Naive”). While a direct invariant (after the remove step X is an independent p-sample of the prior union minus S_i; cascaded Bin(·,1/2) and X-thinning preserve the invariant; a successful DistinctSample restores an independent p-sample of the full union) already justifies the same Chernoff/coupon-collector bounds, the manuscript should either repair the coupling carefully or replace it by the direct invariant so that the published proof matches what the Lean development discharges.
minor comments (4)
  1. [§2, §4.1] Several local typos remain from the PODS revision (e.g., “seminar work” → “seminal work” in §2; “ofcount sketch”; missing spaces and punctuation around the Naive coupling paragraph). A careful pass would help.
  2. [Corollary 1.7] Corollary 1.7’s update-time expression hides an extra log(1/ε) factor relative to the generic bound of Theorem 1.6; a one-line remark explaining the origin (DistinctSample’s coupon-collector loop) would avoid reader confusion.
  3. [Appendix (Lemma 4.6)] In the appendix proof of Lemma 4.6 the constants 4.92, 10.84, 20.68, 62.5 appear without intermediate arithmetic; expanding one Chebyshev/Paley–Zygmund calculation would make the 1/4-style bound easier to check.
  4. [Front matter / §1] The Lean repository is cited only by URL in the footnote; adding a short “Artifact” paragraph (what is formalized, which axioms remain, how to replay) would strengthen the reproducibility claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: APS-Estimator is a self-contained sampling analysis using standard concentration bounds

full rationale

The load-bearing claim (Theorem 1.6) is proved by maintaining an adaptive independent p-sample of the running union, comparing APS-Estimator to an idealized Naive process, and applying Chernoff bounds plus the classical coupon-collector tail (Theorem 3.1) to thr_0 thresholds. No parameter is fitted to data and re-reported as a prediction; Delphic membership/sampling/counting are black-box assumptions discharged separately for rectangles, Cov_t, and DNF terms by direct constructions. Self-citations (hash families, F0 lower bounds, prior hashing-counting constants, the Aggarwal–Obremski proof sketch) supply tools or presentation cleanup, not premises that force the main (ε,δ) guarantee. The Lean 4 formalization further marks the derivation as independently checkable rather than circular. Score 0 is appropriate.

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

The result rests on standard concentration inequalities, the classical coupon-collector tail, the definition of 2-wise independent Toeplitz hash families, and the modeling assumption that each arriving object admits O(log|Ω|)-time membership, counting, and uniform sampling (the Delphic interface). No parameters are fitted to data. The only invented notion is the Delphic family itself, introduced purely as an interface.

assumptions (6)
  • standard math Chernoff, Chebyshev, and Paley–Zygmund concentration bounds apply to the binomial sketch sizes |Y_j^{(i)}|.
    Invoked throughout the Bad_Naive analysis in §4.1 and in the appendix proof of Lemma 4.6.
  • standard math Coupon-collector tail (Theorem 3.1): Pr[Z_r > β r log r] ≤ r^{-β+1}.
    Used to bound Pr[FailSample] ≤ 2δ/3 after DistinctSample.
  • domain assumption Unit-cost word model with random-access read-only input tape; arithmetic on O(log|Ω|)-bit words is O(1).
    Stated in §3; needed for the claimed O(log|Ω|) Delphic operation times and for space measured in words.
  • domain assumption For every set S in the family, |S|, uniform sampling from S, and membership tests are each supported in O(log|Ω_n|) time (Delphic interface).
    Definition 1.4; the entire complexity claim of Theorem 1.6 is relative to this interface.
  • standard math HTeop (Toeplitz affine maps over F_2) is a 2-wise independent hash family representable in Θ(n+m) bits.
    Definition 3.2 and §3; used only by HashingEstimator (Theorem 1.11), not by APS-Estimator.
  • domain assumption NP-oracle access is permitted for the alternate coverage algorithm; only base-machine space is counted.
    Explicitly stated before Theorem 1.11; standard in proof-complexity-style streaming.
invented entities (1)
  • Delphic family / Delphic sets independent evidence
    purpose: Abstract interface that lets one streaming sampler simultaneously capture discrete Klee ranges, t-way coverage sets, and DNF terms.
    Definition 1.4. Purely definitional; every concrete instance is proved Delphic by a short direct argument (Lemmas 4.2–4.4, 4.8). No ontological commitment beyond the three oracles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Estimating Size of the Union of Sets in Streaming Model." pith.science (2026). https://pith.science/paper/ET56IGBV

@misc{pith2026260726997,
  author       = {Pith},
  title        = {Pith review of: Estimating Size of the Union of Sets in Streaming Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ET56IGBV}},
  note         = {Machine review of arXiv:2607.26997}
}
abstract

We study estimating the size of the union of sets $S_1,\dots,S_M$, where each $S_i\subseteq\Omega$ is presented implicitly and arrives in a stream. We introduce Delphic sets, a class of streaming problems in which membership, sampling, and counting queries to each set are efficient, and show that this notion captures three well-known problems: Klee's measure problem (discrete version), test coverage estimation in combinatorial testing, and model counting of DNF formulas. Our primary contribution is a simple and efficient sampling-based algorithm that outputs an $(\varepsilon,\delta)$-approximation of the cardinality of the union of Delphic sets in the streaming setting. It has space complexity $O(R\log|\Omega|)$ and update time $O(R\log R\cdot\log(M/\delta)\cdot\log|\Omega|)$, where $R=O(\log(M/\delta)\cdot\varepsilon^{-2})$. For the streaming Klee's measure problem, this gives the first algorithm whose update time depends linearly on the dimension $d$ for $d>1$, settling an open problem of Tirthapura and Woodruff (PODS 2012), and it directly yields efficient streaming algorithms for coverage estimation and DNF model counting. We further show that the space for coverage estimation can be made near-optimal at the cost of an update procedure in $\mathrm{P}^{\mathrm{NP}}$, revealing a time-space trade-off. A key strength of our approach is the simplicity of both the algorithm and its analysis, which makes it amenable to practical implementation. In this revised version, the algorithm and its correctness analysis have additionally been formalized and machine-checked in Lean 4. (Shortened for Arxiv)

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 3 canonical work pages

  1. [1]

    Noga Alon, Yossi Matias, and Mario Szegedy. 1999. The Space Complexity of Approximating the Frequency Moments.J. Comput. Syst. Sci.58, 1 (1999), 137–147. https://doi.org/10.1006/jcss.1997.1545

    arXiv 1999

  2. [2]

    Sivakumar

    Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. InProc. of SODA. ACM/SIAM, 623–632

    2002

  3. [3]

    Bellare, O

    M. Bellare, O. Goldreich, and E. Petrank. 2000. Uniform Generation of NP- witnesses using an NP-oracle.Information and Computation163, 2 (2000), 510– 526

    2000

  4. [4]

    1977.Algorithms for Klee’s rectangle problems

    Jon Louis Bentley. 1977.Algorithms for Klee’s rectangle problems. Technical Report. Technical Report, Computer

    1977

  5. [5]

    Valentin Tertius Bickel, Jordan Aaron, Andrea Manconi, Simon Loew, and Urs Mall. 2020. Impacts drive lunar rockfalls over billions of years.Nature Communi- cations11, 2862 (2020)

    2020

  6. [6]

    Vladimir Braverman and Rafail Ostrovsky. 2010. Recursive Sketching For Fre- quency Moments.CoRRabs/1011.2571 (2010)

    arXiv 2010

  7. [7]

    Karl Bringmann and Tobias Friedrich. 2010. Approximating the volume of unions and intersections of high-dimensional geometric objects.Comput. Geom.43, 6-7 (2010), 601–610

    2010

  8. [8]

    Renée C Bryce and Charles J Colbourn. 2009. A density-based greedy algorithm for higher strength covering arrays.Software Testing, Verification and Reliability 19, 1 (2009), 37–53

    2009

Show all 61 references
  1. [9]

    Mengchu Cai, Dinesh Keshwani, and Peter Z Revesz. 2000. Parametric rectangles: A model for querying and animation of spatiotemporal databases. InInternational Conference on Extending Database Technology. Springer, 430–444

    2000

  2. [10]

    J Lawrence Carter and Mark N Wegman. 1977. Universal classes of hash functions. InProceedings of the ninth annual ACM symposium on Theory of computing. ACM, 106–112

    1977

  3. [11]

    Chakraborty, K

    S. Chakraborty, K. S. Meel, and M. Y. Vardi. 2013. A Scalable Approximate Model Counter. InProc. of CP. 200–216

    2013

  4. [12]

    Chakraborty, K

    S. Chakraborty, K. S. Meel, and M. Y. Vardi. 2016. Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls. InProc. of IJCAI

    2016

  5. [13]

    Timothy M Chan. 2010. A (slightly) faster algorithm for Klee’s measure problem. Computational Geometry43, 3 (2010), 243–250

    2010

  6. [14]

    Chen, and Martin Farach-Colton

    Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. 2004. Finding frequent items in data streams.Theor. Comput. Sci.312, 1 (2004), 3–15

    2004

  7. [15]

    Eric Y Chen and Timothy M Chan. 2005. Space-efficient algorithms for Klee’s measure problem.algorithms3, 5 (2005), 6

    2005

  8. [16]

    Bogdan S Chlebus. 1998. On the Klee’s measure problem in small dimensions. In International Conference on Current Trends in Theory and Practice of Computer Science. Springer, 304–311

    1998

  9. [17]

    Cohen, Siddhartha R

    David M. Cohen, Siddhartha R. Dalal, Michael L. Fredman, and Gardner C. Patton

  10. [18]

    Jeffrey Considine, Feifei Li, George Kollios, and John Byers. 2004. Approximate aggregation techniques for sensor databases. InProceedings. 20th International Conference on Data Engineering. IEEE, 449–460

    2004

  11. [19]

    Copado-Méndez, Carlos Pozo, Gonzalo Guillén-Gosálbez, and Lau- reano Jiménez

    Pedro J. Copado-Méndez, Carlos Pozo, Gonzalo Guillén-Gosálbez, and Lau- reano Jiménez. 2016. Enhancing the 𝜀-constraint method through the use of objective reduction and random sequences: Application to environmental problems.Computers & Chemical Engineering87 (2016), 36 – 48....

    2016 doi

  12. [20]

    Graham Cormode and Shanmugavelayutham Muthukrishnan. 2003. Estimating dominance norms of multiple data streams. InEuropean Symposium on Algorithms. Springer, 148–160

    2003

  13. [21]

    Dagum, R

    P. Dagum, R. Karp, M. Luby, and S. Ross. 2000. An optimal algorithm for Monte Carlo estimation.SIAM Journal on computing29, 5 (2000), 1484–1496

    2000

  14. [22]

    Nilesh Dalvi and Dan Suciu. 2007. Efficient query evaluation on probabilistic databases.The VLDB Journal16, 4 (2007), 523–544

    2007

  15. [23]

    Michael L Fredman and Bruce Weide. 1978. On the complexity of computing the measure of Ð[ai, bi].Commun. ACM21, 7 (1978), 540–544

    1978

  16. [24]

    Phillip B Gibbons and Srikanta Tirthapura. 2001. Estimating simple functions on the union of data streams. InProceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures. 281–291

    2001

  17. [25]

    Joachim Gudmundsson and Rasmus Pagh. 2017. Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons. In28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand (LIPIcs), Yoshio Okamoto and Takeshi Toku...

    2017

  18. [26]

    Woodruff

    Piotr Indyk and David P. Woodruff. 2005. Optimal approximations of the fre- quency moments of data streams. InProc. of STOC. ACM, 202–208

    2005

  19. [27]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. An optimal algorithm for the distinct elements problem. InProc. of PODS. ACM, 41–52

    2010

  20. [28]

    David R Karger. 2001. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem.SIAM review43, 3 (2001), 499– 522

    2001

  21. [29]

    Karp and M

    R.M. Karp and M. Luby. 1983. Monte-Carlo algorithms for enumeration and reliability problems.Proc. of FOCS(1983)

    1983

  22. [30]

    Richard M Karp, Michael Luby, and Neal Madras. 1989. Monte-Carlo approxima- tion algorithms for enumeration problems.Journal of Algorithms10, 3 (1989), 429 – 448. https://doi.org/10.1016/0196-6774(89)90038-2

    1989 doi

  23. [31]

    Victor Klee. 1977. Can the Measure of be Computed in Less than O (n log n) Steps?The American Mathematical Monthly84, 4 (1977), 284–285

    1977

  24. [32]

    2013.Introduction to combinatorial testing

    D Richard Kuhn, Raghu N Kacker, and Yu Lei. 2013.Introduction to combinatorial testing. CRC press

    2013

  25. [33]

    Iosif Lazaridis and Sharad Mehrotra. 2001. Progressive approximate aggregate queries with a multi-resolution tree structure.Acm sigmod record30, 2 (2001), 401–412

    2001

  26. [34]

    Robert Mandl. 1985. Orthogonal Latin squares: an application of experiment design to compiler testing.Commun. ACM28, 10 (1985), 1054–1058

    1985

  27. [35]

    Joao Marques-Silva, Inês Lynce, and Sharad Malik. 2009. Conflict-driven clause learning SAT solvers. InHandbook of satisfiability. ios Press, 131–153

    2009

  28. [36]

    Flávio Medeiros, Christian Kästner, Márcio Ribeiro, Rohit Gheyi, and Sven Apel

  29. [37]

    Meel and S

    Kuldeep S. Meel and S. Akshay. 2020. Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice. InProc. of LICS

    2020

  30. [38]

    Kuldeep S Meel, Aditya A Shrotri, and Moshe Y Vardi. 2017. On Hashing-Based Approaches to Approximate DNF-Counting. InIn Proc. of FSTTCS

    2017

  31. [39]

    Meel, Aditya A

    Kuldeep S. Meel, Aditya A. Shrotri, and Moshe Y. Vardi. 2018. Not All FPRASs are Equal: Demystifying FPRASs for DNF-Counting.Constraints An Int. J.(12 2018)

    2018

  32. [40]

    Meel, Aditya A

    Kuldeep S. Meel, Aditya A. Shrotri, and Moshe Y. Vardi. 2019. Not All FPRASs are Equal: Demystifying FPRASs for DNF-Counting (Extended Abstract). InProc. of IJCAI

    2019

  33. [41]

    Changhai Nie and Hareton Leung. 2011. A survey of combinatorial testing.ACM Computing Surveys (CSUR)43, 2 (2011), 1–29

    2011

  34. [42]

    Mark H Overmars and Chee-Keng Yap. 1991. New upper bounds in Klee’s measure problem.SIAM J. Comput.20, 6 (1991), 1034–1045

    1991

  35. [43]

    Dimitris Papadias, Panos Kalnis, Jun Zhang, and Yufei Tao. 2001. Efficient OLAP operations in spatial data warehouses. InInternational Symposium on Spatial and Temporal Databases. Springer, 443–459

    2001

  36. [44]

    Pavan and Srikanta Tirthapura

    A. Pavan and Srikanta Tirthapura. 2007. Range-Efficient Counting of Distinct Elements in a Massive Data Stream.SIAM J. Comput.37, 2 (2007), 359–379

    2007

  37. [45]

    Tobias Pett, Thomas Thüm, Tobias Runge, Sebastian Krieter, Malte Lochau, and Ina Schaefer. 2019. Product sampling for product lines: the scalability challenge. In Proceedings of the 23rd International Systems and Software Product Line Conference, SPLC 2019, Volume A, Paris, Fr...

    2019

  38. [46]

    Gokarna Sharma, Costas Busch, Ramachandran Vaidyanathan, Suresh Rai, and Jerry L. Trahan. 2015. Efficient transformations for Klee’s measure problem in the streaming model.Computational Geometry48, 9 (2015), 688 – 702. https: //doi.org/10.1016/j.comgeo.2015.06.007

    2015 doi

  39. [47]

    Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S Meel, and Maciej Obremski. 2023. Engineering an efficient approximate DNF-counter. InProceed- ings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2031–2038

    2023

  40. [48]

    Mate Soos, Stephan Gocht, and Kuldeep S. Meel. 2020. Tinted, Detached, and Lazy CNF-XOR solving and its Applications to Counting and Sampling. InProceedings of International Conference on Computer-Aided Verification (CA V)

    2020

  41. [49]

    Mate Soos and Kuldeep S Meel. 2019. BIRD: Engineering an Efficient CNF-XOR SAT Solver and its Applications to Approximate Model Counting. InProceedings of AAAI Conference on Artificial Intelligence (AAAI)(1 2019)

    2019

  42. [50]

    Stockmeyer

    L. Stockmeyer. 1983. The complexity of approximate counting. InProc. of STOC. 118–126

    1983

  43. [51]

    He Sun and Chung Keung Poon. 2009. Two improved range-efficient algorithms for F0 estimation.Theor. Comput. Sci.410, 11 (2009), 1073–1080

    2009

  44. [52]

    Yufei Tao and Dimitris Papadias. 2004. Range aggregate processing in spatial databases.IEEE Transactions on Knowledge and Data Engineering16, 12 (2004), 1555–1570

    2004

  45. [53]

    Keizo Tatsumi. 1987. Test case design support system. InProc. International Conference on Quality Control (ICQC’87). 615–620

    1987

  46. [54]

    Thomas Thüm, Sven Apel, Christian Kästner, Ina Schaefer, and Gunter Saake

  47. [55]

    Woodruff

    Srikanta Tirthapura and David P. Woodruff. 2012. Rectangle-efficient aggregation in spatial data streams. InProc. of PODS. ACM, 283–294

    2012

  48. [56]

    Jan Vahrenhold. 2007. An in-place algorithm for Klee’s measure problem in two dimensions.Information processing letters102, 4 (2007), 169–174

    2007

  49. [57]

    David Woodruff. 2020. personal communication

    2020

  50. [58]

    Donghui Zhang, Alexander Markowetz, Vassilis J Tsotras, Dimitrios Gunopulos, and Bernhard Seeger. 2008. On computing temporal aggregates with range predicates.ACM Transactions on Database Systems (TODS)33, 2 (2008), 1–39. APPENDIX We provide a Proof of Lemma 4.6. We first rest...

    2008

  51. [1997]

    IEEE Transactions on Software Engineering23, 7 (1997), 437–444

    The AETG system: An approach to testing based on combinatorial design. IEEE Transactions on Software Engineering23, 7 (1997), 437–444

    1997

  52. [2014]

    ACM Computing Surveys (CSUR)47, 1 (2014), 1–45

    A classification and survey of analysis strategies for software product lines. ACM Computing Surveys (CSUR)47, 1 (2014), 1–45

    2014

  53. [2016]

    In2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE)

    A comparison of 10 sampling algorithms for configurable systems. In2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE). IEEE, 643–654

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.