pith. machine review for the scientific record. sign in

arxiv: 2511.15000 · v2 · submitted 2025-11-19 · 💻 cs.PL · cs.DB

Bonsai: Compiling Queries to Pruned Tree Traversals

Alexander J Root , Christophe Gyurgyik , Purvi Goel , Kayvon Fatahalian , Jonathan Ragan-Kelley , Andrew Adams , Fredrik Kjolstad This is my paper

Pith reviewed 2026-05-17 21:24 UTC · model grok-4.3

classification 💻 cs.PL cs.DB
keywords query compilationtree traversalpruning optimizationsymbolic interval analysisgeometric predicatesdatabase queriesindex joinscompiler optimization
0
0 comments X

The pith

A compiler derives pruning conditions for tree queries via symbolic interval analysis to generate traversals matching expert code and outperforming linear scans for complex predicates.

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

The paper shows how to automatically turn high-level queries over tree-structured data into efficient single-pass traversals. It does this by extending symbolic interval analysis with rules that handle geometric predicates such as intersection and containment, allowing the system to figure out from node metadata when entire subtrees can be skipped or accepted wholesale. The compiler also fuses compound operations like filters followed by reductions and supports generalized joins beyond simple equality or range checks. A sympathetic reader would care because this removes the need for programmers to hand-write query-specific pruning logic, which existing systems require when standard optimizations do not apply. If correct, the approach makes tree indexes practical for a much wider range of queries without sacrificing performance.

Core claim

The central claim is that symbolic interval analysis, extended with new rules for geometric predicates, can derive correct pruning and inclusion conditions expressed in terms of node metadata. These conditions are then used to compile queries into fused tree traversals. The resulting code matches the behavior of expert-written query-specific implementations and asymptotically outperforms the linear scans and nested-loop joins that systems fall back to when no hand-written case applies.

What carries the argument

Symbolic interval analysis extended with rules for geometric predicates such as intersection and containment, which computes the conditions for pruning or including subtrees from the query and the metadata stored at each tree node.

Load-bearing premise

The extended symbolic interval analysis must derive correct and complete pruning conditions for the supported queries without missing valid cases or introducing incorrect simplifications.

What would settle it

A concrete geometric query predicate for which the generated traversal either visits a subtree that a correct expert implementation would prune or skips a subtree that must be visited, producing either wrong results or worse performance than the hand-written baseline.

Figures

Figures reproduced from arXiv: 2511.15000 by Alexander J Root, Andrew Adams, Christophe Gyurgyik, Fredrik Kjolstad, Jonathan Ragan-Kelley, Kayvon Fatahalian, Purvi Goel.

Figure 1
Figure 1. Figure 1: Set operations supported by Bonsai. 𝑇 and 𝑆 are primitive types (e.g., integers, floats, or product types). filter, any, and all accept search predicates; min, max, argmin, and argmax accept a metric to optimize over; and reduce accepts a commutative and associative operator. Predicates. A core component of a Bonsai query is a predicate, which maps a set element to a boolean value. For scalars, Bonsai supp… view at source ↗
Figure 2
Figure 2. Figure 2: Geometric operations in Bonsai. distmin and distmax return reals, the rest return booleans. contains(A, B) disjoint(A, B) intersects(A, B) touches(A, B) A ≤x B A <y B A B A B A B A B A A B B [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Examples of lowered filters on the ExampleTree. before yielding or iterating; interior nodes scan when 𝑃 is always true, recurse when 𝑃 may be true, and prune otherwise. Figure 4a shows the lowered filter for 𝑃 on ExampleTree. This rewrite naturally fuses chained filters: each adds local conditions to yield, iter, and scan. Figure 4b shows the fused filter for predicates 𝑃 and𝑄, which scans only when both … view at source ↗
Figure 5
Figure 5. Figure 5: Dual-tree traversal specialization. The generic dual traversal [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Fused, final lowered C++ of a coiterating two trees, and counting collisions over leaf and interior [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of Bonsai versus SotA closest point queries and ray tracing in FCPW [68], and collision detection versus FCL [54]. Lower is better for runtimes (a) and (b), and higher is better for speedups (c) [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Runtime comparisons with state of the art (SotA) database management systems. Lower is better. [PITH_FULL_IMAGE:figures/full_fig_p016_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Speed-up plots over default linear scans for uniformly sampled data in [PITH_FULL_IMAGE:figures/full_fig_p017_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Ablation of count-filter fusion. 9.4.2 Fusion Ablation. Fusion is particularly ben￾eficial when filters are not very selective, as fu￾sion of a reduction on a filter both removes the need for an expensive intermediate data structure, and leverages reduction metadata available in the tree. To highlight these benefits, [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Torus join results, with join predicate √︁ (𝑥0 − 𝑥1) 2 + (𝑦0 − 𝑦1) 2 ∈ [10, 20]. Both tables are uniformly randomly sampled within circles of varying radii, to illustrate the impact of data distribution on join choice [PITH_FULL_IMAGE:figures/full_fig_p018_11.png] view at source ↗
read the original abstract

Trees can accelerate queries that search or aggregate values over large collections. They achieve this by storing metadata that enables quick pruning (or inclusion) of subtrees when predicates on that metadata can prove that none (or all) of the data in a subtree affect the query result. Existing systems implement this pruning logic manually for each query predicate and data structure. We generalize and mechanize this class of optimization. Our method derives conditions for when subtrees can be pruned (or included wholesale), expressed in terms of the metadata available at each node. We efficiently generate these conditions using symbolic interval analysis, extended with new rules to handle geometric predicates (e.g., intersection, containment). Additionally, our compiler fuses compound queries (e.g., reductions on filters) into a single tree traversal. These techniques enable the automatic derivation of generalized single-index and dual-index tree joins that support a wide class of join predicates beyond standard equality and range predicates. The generated traversals match the behavior of expert-written code that implements query-specific traversals, and can asymptotically outperform the linear scans and nested-loop joins that existing systems fall back to when hand-written cases do not apply.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents Bonsai, a compiler that translates queries over tree-structured data into optimized single-pass traversals. It derives subtree pruning (and inclusion) conditions from node metadata via symbolic interval analysis extended with new rules for geometric predicates such as intersection and containment. The system also fuses compound queries (e.g., filters followed by reductions) into a single traversal and generalizes the approach to single-index and dual-index tree joins for predicates beyond equality and range joins. The generated traversals are claimed to match the behavior of expert-written query-specific code while asymptotically outperforming linear scans and nested-loop joins used by existing systems when hand-written cases do not apply.

Significance. If the soundness and completeness claims for the extended interval analysis hold, the work would automate a practically important class of index-specific optimizations that are currently implemented by hand in spatial and tree-based database systems. The ability to derive pruning conditions mechanically and to fuse queries could reduce engineering effort and enable efficient execution for a broader set of predicates than current hand-tuned implementations support.

major comments (2)
  1. [§4.3] §4.3 (Geometric Predicate Rules): The central claim that generated traversals match expert implementations and achieve asymptotic improvements rests on the soundness and completeness of the new rules for intersection and containment predicates. The manuscript provides the rules but does not include a formal soundness argument or an enumeration of edge cases (e.g., degenerate intervals, open vs. closed bounds). Without such an argument, it is impossible to verify that the derived pruning conditions never incorrectly discard a subtree that must be visited.
  2. [§5.2] §5.2 (Experimental Methodology): The abstract asserts that the generated code outperforms linear scans and nested-loop joins. However, the evaluation section does not report how the expert-written baselines were constructed, whether they were allowed the same metadata, or the precise query workloads and data distributions used to demonstrate asymptotic gains. These details are load-bearing for the performance claim.
minor comments (2)
  1. [§3] Notation for interval bounds is introduced in §3 but used inconsistently in later figures; a single table of symbols would improve readability.
  2. The paper cites prior work on symbolic analysis but does not discuss how the new geometric rules differ from existing interval-arithmetic extensions in the literature.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive review and for recognizing the potential of Bonsai to automate index-specific optimizations. We address each major comment below and will incorporate revisions to strengthen the soundness presentation and experimental details.

read point-by-point responses

  1. Referee: [§4.3] §4.3 (Geometric Predicate Rules): The central claim that generated traversals match expert implementations and achieve asymptotic improvements rests on the soundness and completeness of the new rules for intersection and containment predicates. The manuscript provides the rules but does not include a formal soundness argument or an enumeration of edge cases (e.g., degenerate intervals, open vs. closed bounds). Without such an argument, it is impossible to verify that the derived pruning conditions never incorrectly discard a subtree that must be visited.

    Authors: We agree that a formal soundness argument and explicit treatment of edge cases would improve verifiability. The geometric rules extend standard symbolic interval analysis by conservatively over-approximating intersection and containment using interval bounds on node metadata; this design ensures pruning conditions are sound (never discarding a subtree that must be visited) but may be incomplete in some degenerate cases. In the revised manuscript we will add a proof sketch in §4.3 (or an appendix) that establishes soundness via induction on the interval operations, together with a discussion of edge cases including zero-width intervals, open/closed bounds, and empty subtrees. revision: yes

  2. Referee: [§5.2] §5.2 (Experimental Methodology): The abstract asserts that the generated code outperforms linear scans and nested-loop joins. However, the evaluation section does not report how the expert-written baselines were constructed, whether they were allowed the same metadata, or the precise query workloads and data distributions used to demonstrate asymptotic gains. These details are load-bearing for the performance claim.

    Authors: We acknowledge that additional methodological detail is needed for reproducibility. The expert baselines were hand-written by the authors with identical access to the same node metadata used by the compiler, and the workloads were selected to expose asymptotic differences (synthetic uniform and clustered distributions plus real spatial datasets). We will expand §5.2 with explicit descriptions of baseline construction, the exact query sets, data cardinalities and distributions, and the measurement protocol for asymptotic gains versus linear and nested-loop alternatives. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation from query/metadata via symbolic analysis is self-contained

full rationale

The paper presents a mechanized compiler that derives subtree pruning conditions directly from the input query predicates and per-node metadata using symbolic interval analysis extended by new rules for geometric predicates (intersection, containment). The abstract and description frame this as a forward derivation that produces traversals whose behavior matches expert-written code and can outperform linear scans. No equations, fitted parameters, or self-citations are shown reducing the claimed output (pruning conditions or generated traversals) to the inputs by construction. The extension for geometric predicates is introduced as an addition to the analysis rather than a renaming or self-referential fit. The method is therefore independent of the circularity patterns; any questions of soundness or completeness fall under correctness rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on the domain assumption that interval analysis can be soundly extended to geometric predicates and that queries admit a representation suitable for this symbolic treatment; no free parameters or new entities are mentioned.

axioms (1)
  • domain assumption Symbolic interval analysis can be extended with new rules to correctly handle geometric predicates such as intersection and containment for pruning decisions.
    This extension is presented as the key enabler for generalizing beyond standard range and equality predicates.

pith-pipeline@v0.9.0 · 5520 in / 1273 out tokens · 37788 ms · 2026-05-17T21:24:04.700100+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Decoupling Data Layouts from Bounding Volume Hierarchies

    cs.PL 2025-11 unverdicted novelty 7.0

    Scion is a new DSL and compiler that decouples BVH data layouts from traversal algorithms, enabling architecture-agnostic layout optimizations and a novel Pareto-optimal ray tracing layout.

Reference graph

Works this paper leans on

94 extracted references · 94 canonical work pages · cited by 1 Pith paper

  1. [1]

    Timo Aila and Tero Karras. 2010. Architecture considerations for tracing incoherent rays. InProceedings of the Conference on High Performance Graphics(Saarbrucken, Germany)(HPG ’10). Eurographics Association, Goslar, DEU, 113–122

    work page 2010

  2. [2]

    Timo Aila and Samuli Laine. 2009. Understanding the efficiency of ray traversal on GPUs. InProceedings of the Conference on High Performance Graphics 2009(New Orleans, Louisiana)(HPG ’09). Association for Computing Machinery, New York, NY, USA, 145–149. doi:10.1145/1572769.1572792

    work page doi:10.1145/1572769.1572792 2009

  3. [3]

    Ciprian Apetrei. 2014. Fast and simple agglomerative LBVH construction. (2014)

    work page 2014

  4. [4]

    Josh Barnes and Piet Hut. 1986. A hierarchical O(N log N) force-calculation algorithm.Nature324, 6096 (1986), 446–449. doi:10.1038/324446a0

    work page doi:10.1038/324446a0 1986

  5. [5]

    Carsten Benthin, Daniel Meister, Joshua Barczak, Rohan Mehalwal, John Tsakok, and Andrew Kensler. 2024. H-PLOC: Hierarchical Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction.Proceedings of the ACM on Computer Graphics and Interactive Techniques7, 3 (2024), 1–14

    work page 2024

  6. [6]

    Carsten Benthin, Ingo Wald, Sven Woop, and Attila T. Áfra. 2018. Compressed-leaf bounding volume hierarchies. InProceedings of the Conference on High-Performance Graphics(Vancouver, British Columbia, Canada)(HPG ’18). Association for Computing Machinery, New York, NY, USA, Article 6, 4 pages. doi:10.1145/3231578.3231581

    work page doi:10.1145/3231578.3231581 2018

  7. [7]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching.Commun. ACM18, 9 (Sept. 1975), 509–517. doi:10.1145/361002.361007

    work page doi:10.1145/361002.361007 1975

  8. [8]

    2019.Designing Languages for Parallel Portability of Physical Simulations, Using Relational Algebraic Abstractions

    Gilbert Louis Bernstein. 2019.Designing Languages for Parallel Portability of Physical Simulations, Using Relational Algebraic Abstractions. Ph.D. Dissertation. Stanford University

    work page 2019

  9. [9]

    Blumofe and Charles E

    Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling multithreaded computations by work stealing.J. ACM 46, 5 (Sept. 1999), 720–748. doi:10.1145/324133.324234

    work page doi:10.1145/324133.324234 1999

  10. [10]

    Yanju Chen, Junrui Liu, Yu Feng, and Rastislav Bodik. 2022. Tree traversal synthesis using domain-specific symbolic compilation. InProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems(Lausanne, Switzerland)(ASPLOS ’22). Association for Computing Machinery, New York, NY, USA, 1030–104...

    work page doi:10.1145/3503222.3507751 2022

  11. [11]

    Stephen Chou and Saman Amarasinghe. 2022. Compilation of dynamic sparse tensor algebra.Proc. ACM Program. Lang.6, OOPSLA2, Article 175 (Oct. 2022), 30 pages. doi:10.1145/3563338

    work page doi:10.1145/3563338 2022

  12. [12]

    Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers.Proceedings of the ACM on Programming Languages2 (October 2018). Issue OOPSLA

    work page 2018

  13. [13]

    E. F. Codd. 1970. A relational model of data for large shared data banks.Commun. ACM13, 6 (June 1970), 377–387. doi:10.1145/362384.362685

    work page doi:10.1145/362384.362685 1970

  14. [14]

    Douglas Comer. 1979. Ubiquitous B-Tree.ACM Comput. Surv.11, 2 (June 1979), 121–137. doi:10.1145/356770.356776

    work page doi:10.1145/356770.356776 1979

  15. [15]

    Duncan Coutts, Roman Leshchinskiy, and Don Stewart. 2007. Stream fusion: from lists to streams to nothing at all. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming(Freiburg, Germany)(ICFP ’07). Association for Computing Machinery, New York, NY, USA, 315–326. doi:10.1145/1291151.1291199

    work page doi:10.1145/1291151.1291199 2007

  16. [16]

    C. J. Date. 1989.A guide to the SQL standard (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., USA

    work page 1989

  17. [17]

    Isil Dillig, Thomas Dillig, Boyang Li, and Ken McMillan. 2013. Inductive invariant generation via abductive inference. InProceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &amp; Applications(Indianapolis, Indiana, USA)(OOPSLA ’13). Association for Computing Machinery, New York, NY, USA, 443–456. d...

    work page doi:10.1145/2509136.2509511 2013

  18. [18]

    Egenhofer and John Herring

    Max J. Egenhofer and John Herring. 1990. A Mathematical Framework for the Definition of Topological Relationships. In Proceedings of the Fourth International Symposium on Spatial Data Handling. International Geographical Union, Zurich, Switzerland, 803–813. https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH- SDH1990.pdf Ac...

    work page arXiv 1990

  19. [19]

    M. Y. Eltabakh, Mourad Ouzzani, and Walid G. Aref. 2007. Duplicate Elimination in Space-partitioning Tree Indexes. In19th International Conference on Scientific and Statistical Database Management (SSDBM 2007). 18–18. doi:10.1109/ SSDBM.2007.10

    work page 2007

  20. [20]

    Umut Emre, Aryan Kanak, and Shlomi Steinberg. 2025. High-Performance Elliptical Cone Tracing.Computer Graphics Forum44, 7 (Oct 2025). doi:10.1111/cgf.70230

    work page doi:10.1111/cgf.70230 2025

  21. [21]

    2004.Real-Time Collision Detection

    Christer Ericson. 2004.Real-Time Collision Detection. CRC Press, Inc., USA

    work page 2004

  22. [22]

    Peng Fan, Wei Wang, Ruofeng Tong, Hailong Li, and Min Tang. 2024. gDist: Efficient Distance Computation between 3D Meshes on GPU. InSIGGRAPH Asia 2024 Conference Papers(Tokyo, Japan)(SA ’24). Association for Computing Machinery, New York, NY, USA, Article 71, 11 pages. doi:10.1145/3680528.3687619

    work page doi:10.1145/3680528.3687619 2024

  23. [23]

    Leiserson, and Keith H

    Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. 1998. The implementation of the Cilk-5 multithreaded language. InProceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (Montreal, Quebec, Canada)(PLDI ’98). Association for Computing Machinery, New York, NY, USA, 212–223. doi:10. 1145/277650.277725

    work page arXiv 1998

  24. [24]

    Abdullah Gani, Aisha Siddiqa, Shahaboddin Shamshirband, and Fariza Hanum. 2016. A survey on indexing techniques for big data: taxonomy and performance evaluation.Knowledge and Information Systems46, 2 (2016), 241–284. doi:10.1007/s10115-015-0830-y

    work page doi:10.1007/s10115-015-0830-y 2016

  25. [25]

    Goetz Graefe. 1993. Query evaluation techniques for large databases.ACM Comput. Surv.25, 2 (June 1993), 73–169. doi:10.1145/152610.152611

    work page doi:10.1145/152610.152611 1993

  26. [26]

    Goetz Graefe. 2009. Fast Loads and Fast Queries. InData Warehousing and Knowledge Discovery, Torben Bach Pedersen, Mukesh K. Mohania, and A. Min Tjoa (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 111–124

    work page 2009

  27. [27]

    Yan Gu, Yong He, Kayvon Fatahalian, and Guy Blelloch. 2013. Efficient BVH construction via approximate agglomerative clustering. InProceedings of the 5th High-Performance Graphics Conference. 81–88

    work page 2013

  28. [28]

    Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org

    work page 2010

  29. [29]

    Antonin Guttman. 1984. R-trees: a dynamic index structure for spatial searching. InProceedings of the 1984 ACM SIGMOD International Conference on Management of Data(Boston, Massachusetts)(SIGMOD ’84). Association for Computing Machinery, New York, NY, USA, 47–57. doi:10.1145/602259.602266

    work page doi:10.1145/602259.602266 1984

  30. [30]

    Hellerstein, Jeffrey F

    Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. 1998.Generalized search trees for database systems. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 101–112

    work page 1998

  31. [31]

    Rawn Henry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik Kjolstad

    work page

  32. [32]

    Issue OOPSLA

    Compilation of Sparse Array Programming Models.Proceedings of the ACM on Programming Languages5 (November 2021). Issue OOPSLA

    work page 2021

  33. [33]

    Hipp and The SQLite Development Team

    Richard D. Hipp and The SQLite Development Team. 2025. SQLite. Available at https://www.sqlite.org/. Accessed: October 19, 2025

    work page 2025

  34. [34]

    Michael P Howard, Antonia Statt, Felix Madutsa, Thomas M Truskett, and Athanassios Z Panagiotopoulos. 2019. Quantized bounding volume hierarchies for neighbor search in molecular simulations on graphics processing units. Computational Materials Science164 (2019), 139–146

    work page 2019

  35. [35]

    Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Frédo Durand. 2019. Taichi: a language for high-performance computation on spatially sparse data structures.ACM Trans. Graph.38, 6, Article 201 (Nov. 2019), 16 pages. doi:10.1145/3355089.3356506

    work page doi:10.1145/3355089.3356506 2019

  36. [36]

    Mioara Joldes, Jean-Michel Muller, and Valentina Popescu. 2017. Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic.ACM Trans. Math. Softw.44, 2, Article 15res (oct 2017), 27 pages. doi:10.1145/3121432

    work page doi:10.1145/3121432 2017

  37. [37]

    Tero Karras. 2012. Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. InProceedings of the Fourth ACM SIGGRAPH/Eurographics Conference on High-Performance Graphics. 33–37

    work page 2012

  38. [38]

    Kay and James T

    Timothy L. Kay and James T. Kajiya. 1986. Ray tracing complex scenes.SIGGRAPH Comput. Graph.20, 4 (Aug. 1986), 269–278. doi:10.1145/15886.15916

    work page doi:10.1145/15886.15916 1986

  39. [39]

    Matthew J. Keeter. 2020. Massively parallel rendering of complex closed-form implicit surfaces.ACM Trans. Graph.39, 4, Article 141 (Aug. 2020), 10 pages. doi:10.1145/3386569.3392429

    work page doi:10.1145/3386569.3392429 2020

  40. [40]

    Zuhair Khayyat, William Lucia, Meghna Singh, Mourad Ouzzani, Paolo Papotti, Jorge-Arnulfo Quiané-Ruiz, Nan Tang, and Panos Kalnis. 2015. Lightning fast and space efficient inequality joins.Proc. VLDB Endow.8, 13 (Sept. 2015), 2074–2085. doi:10.14778/2831360.2831362

    work page doi:10.14778/2831360.2831362 2015

  41. [41]

    Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler.Proceedings of the ACM on Programming Languages1 (October 2017). Issue OOPSLA. Compiling Set Queries into Work-Efficient Tree Traversals 23

    work page 2017

  42. [42]

    Chaitanya Koparkar, Mike Rainey, Michael Vollmer, Milind Kulkarni, and Ryan R. Newton. 2021. Efficient tree- traversals: reconciling parallelism and dense data representations.Proc. ACM Program. Lang.5, ICFP, Article 91 (Aug. 2021), 29 pages. doi:10.1145/3473596

    work page doi:10.1145/3473596 2021

  43. [43]

    Christian Lauterbach, Michael Garland, Shubhabrata Sengupta, David Luebke, and Dinesh Manocha. 2009. Fast BVH construction on GPUs. InComputer Graphics Forum, Vol. 28. Wiley Online Library, 375–384

    work page 2009

  44. [44]

    Peiming Liu, Alexander J Root, Anlun Xu, Yinying Li, Fredrik Kjolstad, and Aart J.C. Bik. 2024. Compiler Support for Sparse Tensor Convolutions.Proc. ACM Program. Lang.8, OOPSLA2, Article 281 (Oct. 2024), 29 pages. doi:10.1145/ 3689721

    work page 2024

  45. [45]

    Mahmood, Sri Punni, and Walid G

    Ahmed R. Mahmood, Sri Punni, and Walid G. Aref. 2019. Spatio-temporal access methods: a survey (2010 - 2017). Geoinformatica23, 1 (Jan. 2019), 1–36. doi:10.1007/s10707-018-0329-2

    work page doi:10.1007/s10707-018-0329-2 2019

  46. [46]

    Morgan McGuire. 2017. Computer Graphics Archive. https://casual-effects.com/data https://casual-effects.com/data

    work page 2017

  47. [47]

    Daniel Meister and Jiří Bittner. 2017. Parallel locally-ordered clustering for bounding volume hierarchy construction.IEEE transactions on visualization and computer graphics24, 3 (2017), 1345–1353

    work page 2017

  48. [48]

    Doyle, Michael Guthe, and Jiří Bittner

    Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J. Doyle, Michael Guthe, and Jiří Bittner. 2021. A Survey on Bounding Volume Hierarchies for Ray Tracing.Computer Graphics Forum40, 2 (2021), 683–712. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.142662 doi:10.1111/cgf.142662

    work page doi:10.1111/cgf.142662 2021

  49. [49]

    Mitchell

    Don P. Mitchell. 1991. Three Applications of Interval Analysis in Computer Graphics. InFrontiers of Rendering, Course Notes. ACM SIGGRAPH. Course No. 14, SIGGRAPH ’91

    work page 1991

  50. [50]

    Mokbel, Thanaa M

    Mohamed F. Mokbel, Thanaa M. Ghanem, and Walid G. Aref. 2003. Spatio-temporal Access Methods. IEEE Data Engineering Bulletin26, 2 (2003), 40–49

    work page 2003

  51. [51]

    Chandrakana Nandi, Max Willsey, Amy Zhu, Yisu Remy Wang, Brett Saiki, Adam Anderson, Adriana Schulz, Dan Grossman, and Zachary Tatlock. 2021. Rewrite rule inference using equality saturation.Proc. ACM Program. Lang.5, OOPSLA, Article 119 (Oct. 2021), 28 pages. doi:10.1145/3485496

    work page doi:10.1145/3485496 2021

  52. [52]

    Thomas Neumann. 2011. Efficiently compiling efficient query plans for modern hardware.Proc. VLDB Endow.4, 9 (June 2011), 539–550. doi:10.14778/2002938.2002940

    work page doi:10.14778/2002938.2002940 2011

  53. [53]

    Newcomb, Andrew Adams, Steven Johnson, Rastislav Bodik, and Shoaib Kamil

    Julie L. Newcomb, Andrew Adams, Steven Johnson, Rastislav Bodik, and Shoaib Kamil. 2020. Verifying and improving Halide’s term rewriting system with program synthesis.Proc. ACM Program. Lang.4, OOPSLA, Article 166 (Nov. 2020), 28 pages. doi:10.1145/3428234

    work page doi:10.1145/3428234 2020

  54. [54]

    Aref, and Mohamed F

    Long-Van Nguyen-Dinh, Walid G. Aref, and Mohamed F. Mokbel. 2010. Spatio-Temporal Access Methods: Part 2 (2003 - 2010).IEEE Data Eng. Bull.33, 2 (2010), 46–55. http://sites.computer.org/debull/A10june/ Aref.pdf

    work page 2010

  55. [55]

    Jia Pan, Sachin Chitta, and Dinesh Manocha. 2012. FCL: A general purpose library for collision and proximity queries.Proceedings - IEEE International Conference on Robotics and Automation(05 2012), 3859–3866. doi:10.1109/ICRA.2012.6225337

    work page doi:10.1109/icra.2012.6225337 2012

  56. [56]

    Jacopo Pantaleoni and David Luebke. 2010. HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. InProceedings of the Conference on High Performance Graphics. 87–95

    work page 2010

  57. [57]

    Arsène Pérard-Gayot, Richard Membarth, Roland Leißa, Sebastian Hack, and Philipp Slusallek. 2019. Rodent: Generating Renderers without Writing a Generator.ACM Trans. Graph.38, 4, Article 40 (jul 2019), 12 pages. doi:10.1145/3306346.3322955

    work page doi:10.1145/3306346.3322955 2019

  58. [58]

    Arsène Pérard-Gayot, Martin Weier, Richard Membarth, Philipp Slusallek, Roland Leißa, and Sebastian Hack. 2017. RaTrace: Simple and Efficient Abstractions for BVH Ray Traversal Algorithms. InProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (Vancouver, BC, Canada)(GPCE 2017). Association for C...

    work page doi:10.1145/3136040.3136044 2017

  59. [59]

    2023.Physically Based Rendering: From Theory to Implementation(4 ed.)

    Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2023.Physically Based Rendering: From Theory to Implementation(4 ed.). MIT Press. https://mitpress.mit.edu/9780262048026/physically-based-rendering/

    work page arXiv 2023

  60. [60]

    Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: an Embeddable Analytical Database. InProceedings of the 2019 International Conference on Management of Data(Amsterdam, Netherlands)(SIGMOD ’19). Association for Computing Machinery, New York, NY, USA, 1981–1984. doi:10.1145/3299869.3320212

    work page doi:10.1145/3299869.3320212 2019

  61. [61]

    Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand. 2012. Decoupling algorithms from schedules for easy optimization of image processing pipelines. ACM Trans. Graph.31, 4, Article 32 (jul 2012), 12 pages. doi:10.1145/2185520.2185528 24 Root et al

    work page doi:10.1145/2185520.2185528 2012

  62. [62]

    Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Ama- rasinghe. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines.SIGPLAN Not.48, 6 (June 2013), 519–530. doi:10.1145/2499370.2462176

    work page doi:10.1145/2499370.2462176 2013

  63. [63]

    Bin Ren, Shruthi Balakrishna, Youngjoon Jo, Sriram Krishnamoorthy, Kunal Agrawal, and Milind Kulkarni

    work page

  64. [64]

    Parallel Comput

    Extracting SIMD Parallelism from Recursive Task-Parallel Programs.ACM Trans. Parallel Comput. 6, 4, Article 24 (Dec. 2019), 37 pages. doi:10.1145/3365663

    work page doi:10.1145/3365663 2019

  65. [65]

    Andrew Reynolds, Haniel Barbosa, Daniel Larraz, and Cesare Tinelli. 2020. Scalable Algorithms for Abduction via Enumerative Syntax-Guided Synthesis. InAutomated Reasoning: 10th International Joint Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Proceedings, Part I(Paris, France). Springer-Verlag, Berlin, Heidelberg, 141–160. doi:10.1007/978-3-030-51074-9_9

    work page doi:10.1007/978-3-030-51074-9_9 2020

  66. [66]

    Alexander J Root, Maaz Bin Safeer Ahmad, Dillon Sharlet, Andrew Adams, Shoaib Kamil, and Jonathan Ragan-Kelley. 2024. Fast Instruction Selection for Fast Digital Signal Processing. InProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 4(Vancouver, BC, Canada)(ASPLOS ’23). As...

    work page doi:10.1145/3623278.3624768 2024

  67. [67]

    Bik, and Fredrik Kjolstad

    Alexander J Root, Bobby Yan, Peiming Liu, Christophe Gyurgyik, Aart J.C. Bik, and Fredrik Kjolstad

    work page

  68. [68]

    ACM Program

    Compilation of Shape Operators on Sparse Arrays.Proc. ACM Program. Lang.8, OOPSLA2, Article 312 (Oct. 2024), 27 pages. doi:10.1145/3689752

    work page doi:10.1145/3689752 2024

  69. [69]

    Newton, and Milind Kulkarni

    Laith Sakka, Kirshanthan Sundararajah, Ryan R. Newton, and Milind Kulkarni. 2019. Sound, fine- grained traversal fusion for heterogeneous trees. InProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation(Phoenix, AZ, USA)(PLDI 2019). Association for Computing Machinery, New York, NY, USA, 830–844. doi:10.1145/331422...

    work page doi:10.1145/3314221.3314626 2019

  70. [70]

    2005.Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling)

    Hanan Samet. 2005.Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA

    work page 2005

  71. [71]

    2021.FCPW: Fastest Closest Points in the West

    Rohan Sawhney. 2021.FCPW: Fastest Closest Points in the West

    work page 2021

  72. [72]

    Rohan Sawhney and Keenan Crane. 2020. Monte Carlo geometry processing: a grid-free approach to PDE-based methods on volumetric domains.ACM Trans. Graph.39, 4, Article 123 (Aug. 2020), 18 pages. doi:10.1145/3386569.3392374

    work page doi:10.1145/3386569.3392374 2020

  73. [73]

    Schardl, William S

    Tao B. Schardl, William S. Moses, and Charles E. Leiserson. 2019. Tapir: Embedding Recursive Fork-join Parallelism into LLVM’s Intermediate Representation.ACM Trans. Parallel Comput.6, 4, Article 19 (Dec. 2019), 33 pages. doi:10.1145/3365655

    work page doi:10.1145/3365655 2019

  74. [74]

    Griffiths Selinger, M

    P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. InProceedings of the 1979 ACM SIGMOD International Conference on Management of Data(Boston, Massachusetts)(SIGMOD ’79). Association for Computing Machinery, New York, NY, USA, 23–34. doi:10.1145/582...

    work page doi:10.1145/582095.582099 1979

  75. [75]

    Vidush Singhal, Laith Sakka, Kirshanthan Sundararajah, Ryan Newton, and Milind Kulkarni. 2024. Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals.ACM Trans. Archit. Code Optim.21, 2, Article 41 (May 2024), 25 pages. doi:10.1145/3652605

    work page doi:10.1145/3652605 2024

  76. [76]

    John M. Snyder. 1992. Interval analysis for computer graphics.SIGGRAPH Comput. Graph.26, 2 (July 1992), 121–130. doi:10.1145/142920.134024

    work page doi:10.1145/142920.134024 1992

  77. [77]

    Sivaprasad Sudhir, Wenbo Tao, Nikolay Laptev, Cyrille Habis, Michael Cafarella, and Samuel Madden

    work page

  78. [78]

    VLDB Endow.16, 9 (May 2023), 2316–2329

    Pando: Enhanced Data Skipping with Logical Data Partitioning.Proc. VLDB Endow.16, 9 (May 2023), 2316–2329. doi:10.14778/3598581.3598601

    work page doi:10.14778/3598581.3598601 2023

  79. [79]

    Franklin, Sanjay Krishnan, and Reynold S

    Liwen Sun, Michael J. Franklin, Sanjay Krishnan, and Reynold S. Xin. 2014. Fine-grained partitioning for aggressive data skipping. InProceedings of the 2014 ACM SIGMOD International Conference on Management of Data(Snowbird, Utah, USA)(SIGMOD ’14). Association for Computing Machinery, New York, NY, USA, 1115–1126. doi:10.1145/2588555.2610515

    work page doi:10.1145/2588555.2610515 2014

  80. [80]

    Shiv Sundram, Muhammad Usman Tariq, and Fredrik Kjolstad. 2024. Compiling Recurrences over Dense and Sparse Arrays.Proc. ACM Program. Lang.8, OOPSLA1, Article 103 (April 2024), 26 pages. doi:10.1145/3649820 Compiling Set Queries into Work-Efficient Tree Traversals 25

    work page doi:10.1145/3649820 2024

Showing first 80 references.