Pith. sign in

REVIEW 3 major objections 5 minor 56 references

GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons

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

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

Pith's one-line read GeoBlocks pre-aggregates geospatial points into grid cells so aggregate queries over arbitrary polygons run up to three orders of magnitude faster while keeping a user-controlled spatial error bound.

desk verdict A solid systems paper whose 'bounded error' guarantee is geometric, not aggregate-level; the performance work is real, but the abstract overstates the precision guarantee. read the letter →

arxiv 1908.07753 v3 pith:CBG3YYGB submitted 2019-08-21 cs.DB

Christian Winter (1) , Andreas Kipf (2) , Christoph Anneser (1) , Eleni Tzirita Zacharatou (3) , Thomas Neumann (1) , Alfons Kemper (1) ((1) Technische Universität München , (2) MIT CSAIL , (3) Technische Universität Berlin) This is my paper · ORCID
classification cs.DB
keywords geospatialdatamanagementspatialaggregationpolygonqueriespre-aggregationerror-boundedapproximationquadtreedecompositionquerycachingexploratoryanalytics
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

GeoBlocks is a pre-aggregating data structure for geospatial point data that answers aggregate queries over arbitrarily shaped polygons without scanning raw points. Instead of storing aggregates over rectangles like earlier pre-aggregation methods, it subdivides space into fine-grained grid cells, keeps per-cell aggregates, and approximates each query polygon by a set of grid cells whose size the user controls. The paper argues this is the first such structure that can bound the approximation error for arbitrary polygons, and that query time depends on the number of cells touched rather than the number of points. The authors claim speedups of up to three orders of magnitude over on-the-fly aggregation, putting interactive sub-second exploratory analysis within reach for datasets with hundreds of millions of points.

What carries the argument

The load-bearing object is the cell covering of a query polygon in a hierarchical quadtree space decomposition, implemented with the S2 geometry library. A polygon is approximated by the set of grid cells it intersects; the maximum distance between any point on the covering and the polygon outline is bounded by the cell diagonal, so shrinking the cell size gives a user-defined spatial error bound. Around that covering sit the GeoBlock's sorted per-cell aggregates (count, min, max, sum per column), a global header for fast containment tests, and the AggregateTrie, a compact in-place trie whose nodes are two 32-bit offsets pointing to child nodes and cached aggregates. The covering is what lets GeoBlocks answer arbitrary-polygon queries, whereas prior pre-aggregation over rectangles could not offer a controllable error.

What would settle it

Take a polygon whose boundary passes through a very dense point cluster and compare GeoBlocks' count at several block levels against the exact count from the raw data; if the relative count error stays large and does not shrink as the cell size decreases, the bounded-error guarantee for aggregates fails.

Watch

Extended reading notes

Core claim

GeoBlocks replaces an arbitrary query polygon, on the fly, by a cell covering in a hierarchical quadtree decomposition, and answers the aggregation by combining pre-computed aggregates of the covering cells. The paper's central claim is that this makes polygonal aggregation practical for exploratory analysis: the user picks a cell level, the cell diagonal bounds the spatial distance between the covering and the true polygon, and because point data are sorted by spatial key with cell aggregates stored contiguously in that order, a SELECT query touches only the covering cells while a COUNT query uses offset/count arithmetic on the first and last contained cell. A trie-like AggregateTrie caches aggregates of frequently queried cells, so workloads with spatial skew speed up further. The experimental claim is that GeoBlocks outperforms on-the-fly aggregation by up to three orders of magnitude and reaches sub-second latencies on datasets with hundreds of millions of points.

Load-bearing premise

The argument assumes that a small cell size, which bounds how far the cell covering can stray from the polygon outline, also keeps the aggregate result close to the exact answer; but the number of extra points caught in the boundary strip depends on where the data are concentrated, not just on cell size.

Editorial extensions

If this is right

  • Analysts can set a geometric precision dial and get aggregate results in sub-second time on static point sets of hundreds of millions of points.
  • Repeated queries over the same or overlapping regions get faster over time as the AggregateTrie fills, adapting to workload skew without prior assumptions about which regions will be queried.
  • Building many GeoBlocks for different filter predicates from one pass over sorted base data amortizes the sorting cost within a small number of filter changes.
  • Query latency stays nearly constant as the dataset grows for a fixed spatial distribution, because it depends on the number of maintained cell aggregates rather than the number of points.
  • The structure provides the first pre-aggregating way to handle arbitrary polygons with a bounded, user-controllable spatial error, extending pre-aggregation beyond rectangle-only queries.

Reading between the lines

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

  • For applications that need exact counts, the cell covering would need to be paired with a refinement pass over points in the boundary strip, since the spatial bound alone does not control how many points fall in the strip.
  • The same cell-covering and sorted-aggregate layout could serve approximate point-in-polygon membership and spatial join workloads, not only aggregation queries.
  • Cache scoring by hit counts plus parent hits is a simple heuristic; weighting by polygon area or supporting sibling-subtraction aggregates could extend its reach on skewed workloads.
  • For insert workloads, updates to existing cells are cheap, but inserts into previously empty regions require rebuilding the sorted aggregate layout; batching such inserts would keep the rebuild cost tolerable.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. GeoBlocks proposes a pre-aggregated, grid-cell-based data structure for spatial aggregation over arbitrary polygons. Point data is mapped to an S2-style hierarchical cell decomposition, and each grid cell stores precomputed aggregates (count, sum, min, max). A query polygon is approximated by an S2 cell covering, and the user chooses the block level, which controls the spatial distance between the covering and the polygon outline. A second contribution is a trie-like query cache, the AggregateTrie, that stores aggregates for frequently queried cells. The paper evaluates GeoBlocks against binary-search, B-tree, PH-tree, and aR-tree baselines on NYC taxi, Twitter, and OSM data, reporting speedups of up to three orders of magnitude over on-the-fly aggregation and competitive performance with the aR-tree.

Significance. If the central claims hold after revision, the paper describes a practically attractive accelerator for interactive exploratory spatial analytics: a small, fast pre-aggregated index that supports arbitrary polygonal queries, admits a user-set geometric precision dial, and adapts to query skew through a cache. The experimental evaluation is broad and internally consistent, covering build time, space overhead, selectivity, dataset scale, and workloads with different skew. The authors clearly describe the storage layout, the query algorithms, and the caching heuristic, and they explicitly acknowledge some limitations of the cache-scoring rule. The main weakness is that the advertised 'bounded error' guarantee is not actually a bound on the error of the reported aggregate; this gap affects the paper's central novelty claim and must be addressed before the contribution can be assessed as stated.

major comments (3)
  1. [Abstract, Section 1, Section 3.2] The bounded-error guarantee is a geometric statement, not an aggregate-error statement. Section 3.2 proves that every point on a covering cell lies within sqrt(eps1^2+eps2^2) of the polygon outline, where eps1 and eps2 are the cell side lengths. This does not bound the error in the reported aggregate: for a COUNT query, the error is the number of data points that lie in the covering cells but outside the true polygon, and that number is controlled by the point distribution, not by the cell size. For any fixed block level, one can place arbitrarily many points in the boundary strip just outside a polygon edge, making the reported count arbitrarily larger than the true count; the same construction affects SUM, AVG, MIN, and MAX when the false-positive points carry extreme values. The paper's own Figure 16 observes a 'gap between the relative error and the configurable spatial error' caused by non-uniform point distribution, which is exactly this phenomenon. The abstract's claim that GeoBlocks 'allow to bound the approximation error by adjusting the cell size' and Section 1's claim of 'guarantees error-bounded results' therefore overstate what follows. Please either restate the guarantee as a spatial approximation bound (and add an explicit discussion of the distribution-dependent aggregate error), or supply a real bound on aggregate error, e.g., in terms of the number of points in boundary cells or a density-based estimate.
  2. [Section 4.2, Figures 14 and 15] The precision comparison is not controlled across approaches. The text states that Block, BinarySearch, and BTree 'use the same covering' and therefore have identical error, while PHTree and aRTree use a different rectangular representation. Consequently, the relative-error differences in Figures 14 and 15 mainly reflect the choice of query-region approximation (S2 covering vs. interior rectangle), not the effect of the pre-aggregation data structure itself. This does not support the claim in Section 4.2 that GeoBlocks deliver 'far more precise results' than the aR-tree. To make the precision claim meaningful, the experiments should compare all approaches against the same reference, for example by using the same covering for all methods or by reporting error with respect to the exact polygon result for every method.
  3. [Section 1 and Section 6 (related work)] The novelty claim that GeoBlocks are 'the first ... data structure that supports spatial aggregation over arbitrary polygons, while guaranteeing a bounded error' should be qualified. The cell-covering machinery, including the distance bound, comes from S2 and from prior approximate join work by the same group [16, 17, 52]; the genuinely new elements appear to be the block-level aggregate layout and the query-cache. Please position the 'first' claim with respect to this prior work, or restrict the novelty statement to the specific combination of pre-aggregation, arbitrary polygons, and the cache.
minor comments (5)
  1. [Section 3.2] The statement that 'the diagonal reduces by a factor of 2' per level assumes cells are squares; S2 cells are not exactly square, so the relationship between level and diagonal should be stated as approximate or taken from the S2 cell statistics table.
  2. [Section 3.5, Listing 1] The pseudocode uses s2.childrenAtLvl(qcell, BLOCK_LVL) and a later textual check 'until we reach a grid cell not contained in the query cell' that does not appear explicitly in the listing. Please make the termination condition and the handling of the AggregateTrie probe explicit, and define the notation consistently.
  3. [Section 3.5] The text says the cell covering 'cannot contain any cells smaller than the cells of the GeoBlock.' This is an invariant that must be enforced during cover generation; please state how it is guaranteed, since S2's default covering may return cells finer than the block level.
  4. [Section 4.2, Figure 14] The relative-error metric divides by the number of tuples in the polygon, which is undefined when a query polygon contains zero points. Please specify the handling of this degenerate case.
  5. [General] The notation 'aRTree' and 'aR-tree' is used inconsistently; please choose one form and use it throughout. Also, the phrase 'aRtree and PHTree use an identical rectangular representation' is imprecise, since the aR-tree uses a hierarchy of node MBRs rather than a single rectangle.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the geometric error bound and query-cache scoring are not fitted inputs or self-citation reductions.

full rationale

GeoBlocks' derivation chain is self-contained against external benchmarks. The cell-covering error bound in Section 3.2 is a geometric property of the S2 decomposition: any point on the covering lies within sqrt(eps1^2+eps2^2) of the polygon outline, and the user controls this spatial error by choosing the cell level. This is not a fitted parameter and is not defined in terms of the reported aggregate; it is computed directly from the covering geometry. The query-cache scoring rule in Section 3.6 is explicitly a stated heuristic ('We chose the above metric as it is sufficient to properly and repeatably represent the skew in the experiments') and is evaluated experimentally, not tuned against the reported results as a prediction. The self-citations [16,17,52] are used for optional encoding/indexing mechanisms and for the observation that an MBR cannot give a distance bound; none of these citations entails the new block layout, the COUNT range-sum trick, or the AggregateTrie cache. The MBR claim is independently derivable and is not load-bearing via self-citation. One genuine weakness exists, but it is a correctness issue rather than circularity: Section 3.2 proves a spatial error bound, while the abstract and Section 1 phrase it as a bound on the approximation error of the aggregation, and false-positive points in boundary cells can make count error data-dependent, as the paper itself acknowledges in Figure 16 ('a gap between the relative error and the configurable spatial error'). That mismatch does not reduce the derivation to its inputs; it is an overstatement of what the geometric guarantee implies. Overall, no step in the paper's claimed derivation is equivalent to its inputs by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central method contains no fitted constants. The one true dial is grid resolution, chosen by the user and set to 17 in most experiments. The cache-size threshold and workload skew are experiment settings, not hidden fits. The unstated burden is a data-distribution assumption: the geometric error bound only translates into useful aggregate accuracy if points are not pathologically concentrated at polygon boundaries. No invented entities are introduced.

free parameters (2)
  • Block level (grid cell size) = Default 17 in most experiments (~100 m diagonal); range 13-21 explored
    User-specified resolution controls the spatial error bound and the number of cell aggregates; it is the central accuracy/performance trade-off, not a hidden fitted constant.
  • AggregateTrie size threshold = 5% of cell aggregate storage in default experiments; 1-100% explored
    Sets the memory budget for the query cache and influences BlockQC speedup, especially under skewed workloads.
assumptions (5)
  • domain assumption S2 library correctly computes cell coverings and order-preserving cell ids for arbitrary query polygons.
    Invoked in Section 3.1 and Section 3.5; if the covering is wrong or non-contiguous, the binary-search and range-count logic fails.
  • standard math Aggregates are decomposable (count, sum, min, max; average as sum/count) so partial cell aggregates can be combined into polygon results.
    Problem statement Section 2 restricts to non-holistic aggregates; this is what makes pre-aggregation valid.
  • domain assumption The dataset is static or write-once/read-only, so the sorted cell-aggregate layout does not need online updates.
    Section 5 discusses updates only as a possible extension; the design assumes historical point data.
  • domain assumption Point data is not pathologically concentrated near polygon boundaries, so the spatial distance bound implies practically bounded aggregate error.
    Required by the abstract and Section 1 claim of bounded aggregation error; Section 3.2 and Figure 16 show only the spatial bound and dataset-dependent relative error.
  • standard math Hilbert/space-filling enumeration maps each cell's descendants to a contiguous key interval, making the COUNT range formula correct.
    Needed for Listing 2; follows from S2 cell id ordering.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons." pith.science (2026). https://pith.science/paper/CBG3YYGB

@misc{pith2026190807753,
  author       = {Pith},
  title        = {Pith review of: GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CBG3YYGB}},
  note         = {Machine review of arXiv:1908.07753}
}
read the original abstract

As individual traffic and public transport in cities are changing, city authorities need to analyze urban geospatial data to improve transportation and infrastructure. To that end, they highly rely on spatial aggregation queries that extract summarized information from point data (e.g., Uber rides) contained in a given polygonal region (e.g., a city neighborhood). To support such queries, current analysis tools either allow only predefined aggregates on predefined regions and are thus unsuitable for exploratory analyses, or access the raw data to compute aggregate results on-the-fly, which severely limits the interactivity. At the same time, existing pre-aggregation techniques are inadequate since they maintain aggregates over rectangular regions. As a result, when applied over arbitrary polygonal regions, they induce an approximation error that cannot be bounded. In this paper, we introduce GeoBlocks, a novel pre-aggregating data structure that supports spatial aggregation over arbitrary polygons. GeoBlocks closely approximate polygons using a set of fine-grained grid cells and, in contrast to prior work, allow to bound the approximation error by adjusting the cell size. Furthermore, GeoBlocks employ a trie-like cache that caches aggregate results of frequently queried regions, thereby dynamically adapting to the skew inherently present in query workloads and improving performance over time. In summary, GeoBlocks outperform on-the-fly aggregation by up to three orders of magnitude, achieving the sub-second query latencies required for interactive exploratory analytics.

Figures

Figures reproduced from arXiv: 1908.07753 by the authors.

Figure 1
Figure 1. Cell covering (blue) of the Lower East Side (bor￾der in orange) with bounded error (red), a cell aggregate (green), and a cached commonly queried region (purple). On the bright side, interactive analyses are often repetitive in nature. Analysts, for example, typically run multiple aggre￾gate queries for the same area (e.g., the city center) in a sequence, changing only the aggregate function (e.g., count, sum) or th… view at source ↗
Figure 2
Figure 2. Problem overview: Calculating unknown aggre [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Hierarchical cell decomposition [16]. In exploratory interactive analyses, users can dynamically and unpredictably change not only the filtering conditions and the requested aggregates but also the polygonal query region. The data points, on the other hand, are known a priori [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: MBR (left) and two cell coverings with increas [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 5
Figure 5. Figure 5: Creation of a GeoBlock in two phases. The ex [PITH_FULL_IMAGE:figures/full_fig_p003_5.png]
Figure 6
Figure 6. Figure 6: Query overview: Query polygon (a), cell covering [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]
Figure 7
Figure 7. Figure 7: AggregateTrie with 40 byte aggregates and in [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]
Figure 8
Figure 8. Figure 8: Overview of adapted query algorithm. Nodes occupy 8 bytes, while the size of the aggregates depends on the schema. Since we store only the offset to the first child, we need to always allocate space for all children in a node, even for children that do not exist in the…
Figure 10
Figure 10. Figure 10: Runtime with increasing number of aggregates. [PITH_FULL_IMAGE:figures/full_fig_p007_10.png]
Figure 9
Figure 9. Figure 9: Illustration of aRTree with node size two and off [PITH_FULL_IMAGE:figures/full_fig_p007_9.png]
Figure 11
Figure 11. Figure 11: Index overhead in build time and space. 6× 1667× 102 103 104 105 106 107 0 25 50 75 100 Selectivity in % Runtime in μs [log scale] BinarySearch Block BlockQC BTree PHTree aRTree [PITH_FULL_IMAGE:figures/full_fig_p008_11.png]
Figure 12
Figure 12. Figure 12: Query runtime for varying selectivity. as our goal is to provide approximate results, we wanted to show that storing intermediate results is less space-consuming than one would assume for such fine-grained aggregates. While the aRTree is more space-saving when compare…
Figure 14
Figure 14. Figure 14: We again query the whole area represented by the [PITH_FULL_IMAGE:figures/full_fig_p009_14.png]
Figure 15
Figure 15. Figure 15: Query runtime and relative error for US states [PITH_FULL_IMAGE:figures/full_fig_p009_15.png]
Figure 17
Figure 17. Figure 17: Query runtime with increasing workload skew. [PITH_FULL_IMAGE:figures/full_fig_p010_17.png]
Figure 18
Figure 18. Figure 18: Impact of threshold on workload runtime (solid [PITH_FULL_IMAGE:figures/full_fig_p010_18.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages

  1. [1]

    W. G. Aref and H. Samet. Efficient processing of window queries in the pyramid data structure. In PODS, pages 265–272. ACM Press, 1990

    work page 1990

  2. [2]

    Baralis, S

    E. Baralis, S. Paraboschi, and E. Teniente. Materialized views selection in a multidimensional database. In VLDB, pages 156–165, 1997

    work page 1997

  3. [3]

    R. Bayer. The universal b-tree for multidimensional indexing: general concepts. In WWCA, pages 198–209. Springer, 1997

    work page 1997

  4. [4]

    How to analyse bike data for urban planning? https://www.bikecitizens.net/ analyse-bike-data-urban-planning/

    work page

  5. [5]

    https://www.boost.org/doc/libs/1_69_0/libs/geometry/doc/html/ geometry/reference/spatial_indexes/boost__geometry__index__rtree.html

    Boost R-tree. https://www.boost.org/doc/libs/1_69_0/libs/geometry/doc/html/ geometry/reference/spatial_indexes/boost__geometry__index__rtree.html

    work page

  6. [6]

    F. Braz, S. Orlando, R. Orsini, A. Raffaetà, A. Roncato, and C. Silvestri. Ap- proximate aggregations in trajectory data warehouses. In ICDE Workshops, pages 536–545, 2007

    work page 2007

  7. [7]

    https://code.google.com/archive/p/cpp-btree/

    Google code archive. https://code.google.com/archive/p/cpp-btree/

    work page

  8. [8]

    Ferreira, M

    N. Ferreira, M. Lage, H. Doraiswamy, H. Vo, L. Wilson, H. Werner, M. Park, and C. Silva. Urbane: A 3d framework to support data driven decision making in urban development. In Proc. IEEE V AST, pages 97–104, 2015

    work page 2015

Show all 56 references
  1. [9]

    R. A. Finkel and J. L. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1–9, 1974

    1974

  2. [10]

    Geffner, D

    S. Geffner, D. Agrawal, A. E. Abbadi, and T. R. Smith. Relative prefix sums: An efficient approach for querying dynamic OLAP data cubes. In ICDE, pages 328–335, 1999

    1999

  3. [11]

    J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub totals. Data Min. Knowl. Discov. , 1(1):29–53, 1997

    1997

  4. [12]

    H. Gupta. Selection of views to materialize in a data warehouse. In ICDT, pages 98–112. Springer, 1997

    1997

  5. [13]

    A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, pages 47–57. ACM Press, 1984

    1984

  6. [14]

    J. Han, N. Stefanovic, and K. Koperski. Selective materialization: An efficient method for spatial data cube construction. InPAKDD, pages 144–158. Springer, 1998

    1998

  7. [15]

    Harinarayan, A

    V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. In SIGMOD, pages 205–216. ACM Press, 1996

    1996

  8. [16]

    A. Kipf, H. Lang, V. Pandey, R. A. Persa, C. Anneser, E. Tzirita Zacharatou, H. Doraiswamy, P. A. Boncz, T. Neumann, and A. Kemper. Adaptive main- memory indexing for high-performance point-polygon joins. In EDBT, pages 347–358, 2020

    2020

  9. [17]

    A. Kipf, H. Lang, V. Pandey, R. A. Persa, P. A. Boncz, T. Neumann, and A. Kem- per. Approximate geospatial joins with precision guarantees. In ICDE, pages 1360–1363. IEEE Computer Society, 2018

    2018

  10. [18]

    Kriegel, H

    H. Kriegel, H. Horn, and M. Schiwietz. The performance of object decom- position techniques for spatial query processing. In SSD, volume 525, pages 257–276. Springer, 1991

    1991

  11. [19]

    Lazaridis and S

    I. Lazaridis and S. Mehrotra. Progressive approximate aggregate queries with a multi-resolution tree structure. In SIGMOD, pages 401–412. ACM, 2001

    2001

  12. [20]

    Lazaridis and S

    I. Lazaridis and S. Mehrotra. Multi-resolution aggregate tree. In Encyclopedia of GIS, pages 764–765. Springer, 2008

    2008

  13. [21]

    L. D. Lins, J. T. Klosowski, and C. E. Scheidegger. Nanocubes for real-time exploration of spatiotemporal datasets. IEEE Trans. Vis. Comput. Graph. , 19(12):2456–2465, 2013

    2013

  14. [22]

    Liu and J

    Z. Liu and J. Heer. The Effects of Interactive Latency on Exploratory Visual Analysis. Proc. TVCG, 20(12):2122–2131, 2014

    2014

  15. [23]

    I. F. V. López, R. T. Snodgrass, and B. Moon. Spatiotemporal aggregate compu- tation: a survey. IEEE Trans. Knowl. Data Eng. , 17(2):271–286, 2005

    2005

  16. [24]

    Nagel, P

    F. Nagel, P. A. Boncz, and S. Viglas. Recycling in pipelined query evaluation. In ICDE, pages 338–349, 2013

    2013

  17. [25]

    https://data.cityofnewyork.us/City-Government/ Neighborhood-Tabulation-Areas/cpf4-rkhq

    NYC neighborhoods. https://data.cityofnewyork.us/City-Government/ Neighborhood-Tabulation-Areas/cpf4-rkhq

  18. [26]

    J. A. Orenstein. Spatial query processing in an object-oriented database system. In SIGMOD Conference, pages 326–336. ACM Press, 1986

    1986

  19. [27]

    J. A. Orenstein and T. H. Merrett. A class of data structures for associative searching. In PODS, pages 181–190. ACM, 1984

    1984

  20. [28]

    Pandey, A

    V. Pandey, A. Kipf, T. Neumann, and A. Kemper. How good are modern spatial analytics systems? PVLDB, 11(11):1661–1673, 2018

    2018

  21. [29]

    Pandey, A

    V. Pandey, A. van Renen, A. Kipf, J. Ding, I. Sabek, and A. Kemper. The case for learned spatial indexes. In AIDB@VLDB, 2020

    2020

  22. [30]

    Papadias, P

    D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient OLAP operations in spatial data warehouses. In SSTD, pages 443–459. Springer, 2001

    2001

  23. [31]

    Papadias, Y

    D. Papadias, Y. Tao, P. Kalnis, and J. Zhang. Indexing spatio-temporal data warehouses. In ICDE, pages 166–175, 2002

    2002

  24. [32]

    Papadias, Y

    D. Papadias, Y. Tao, J. Zhang, N. Mamoulis, Q. Shen, and J. Sun. Indexing and retrieval of historical aggregate information about moving objects. IEEE Data Eng. Bull., 25(2):10–17, 2002

    2002

  25. [33]

    Pavlovic, D

    M. Pavlovic, D. Sidlauskas, T. Heinis, and A. Ailamaki. QUASII: query-aware spatial incremental index. In EDBT, pages 325–336, 2018

    2018

  26. [34]

    T. B. Pedersen and N. Tryfona. Pre-aggregation in spatial data warehouses. In SSTD, pages 460–480. Springer, 2001

    2001

  27. [35]

    Phan and W

    T. Phan and W. Li. Dynamic materialization of query views for data warehouse workloads. In ICDE, pages 436–445, 2008

    2008

  28. [36]

    https://github.com/mcxme/phtree

    mcxme/phtree. https://github.com/mcxme/phtree

  29. [37]

    F. Rao, L. Zhang, X. Yu, Y. Li, and Y. Chen. Spatial hierarchy and olap-favored search in spatial data warehouse. In DOLAP, pages 48–55. ACM, 2003

    2003

  30. [38]

    https://s2geometry.io/

    S2 geometry. https://s2geometry.io/

  31. [39]

    H. Samet. The quadtree and related hierarchical data structures.ACM Comput. Surv., 16(2):187–260, 1984

    1984

  32. [40]

    Schneider

    T. Schneider. Analyzing 1.1 Billion NYC Taxi and Uber Trips, with a Vengeance. https://toddwschneider.com/posts/analyzing-1-1-billion-nyc-taxi- and-uber-trips-with-a-vengeance/

  33. [41]

    V. Shah. Citi Bike 2017 Analysis - Towards Data Science . https:// towardsdatascience.com/citi-bike-2017-analysis-efd298e6c22c

    2017

  34. [42]

    J. Shim, P. Scheuermann, and R. Vingralek. Dynamic caching of query results for decision support systems. In SSDBM, pages 254–263, 1999

    1999

  35. [43]

    J. Shin, A. R. Mahmood, and W. G. Aref. An investigation of grid-enabled tree indexes for spatial query processing. In SIGSPATIAL, pages 169–178, 2019

    2019

  36. [44]

    Shmueli and A

    O. Shmueli and A. Itai. Maintenance of views. In SIGMOD, pages 240–255. ACM Press, 1984

    1984

  37. [45]

    Shukla, P

    A. Shukla, P. Deshpande, and J. F. Naughton. Materialized view selection for multidimensional datasets. In VLDB, pages 488–499, 1998

    1998

  38. [46]

    Singla, A

    S. Singla, A. Eldawy, R. Alghamdi, and M. F. Mokbel. Raptor: Large scale analysis of big raster and vector data. PVLDB, 12(12):1950–1953, 2019

    1950

  39. [47]

    Sprenger, P

    S. Sprenger, P. Schäfer, and U. Leser. Bb-tree: A main-memory index structure for multidimensional range queries. In ICDE, pages 1566–1569, 2019

    2019

  40. [48]

    Y. Tao, G. Kollios, J. Considine, F. Li, and D. Papadias. Spatio-temporal aggre- gation using sketches. In ICDE, pages 214–225, 2004

    2004

  41. [49]

    https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

    Nyc tlc data. https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

  42. [50]

    http://tncstoday.sfcta.org/

    TNCs TODAY. http://tncstoday.sfcta.org/

  43. [51]

    Tzirita Zacharatou, H

    E. Tzirita Zacharatou, H. Doraiswamy, A. Ailamaki, C. T. Silva, and J. Freire. GPU rasterization for real-time spatial aggregation over arbitrary polygons. PVLDB, 11(3):352–365, 2017

    2017

  44. [52]

    Tzirita Zacharatou, A

    E. Tzirita Zacharatou, A. Kipf, I. Sabek, V. Pandey, H. Doraiswamy, and V. Markl. The case for distance-bounded spatial approximations. In CIDR. http://cidrdb.org, 2021

    2021

  45. [53]

    https://movement.uber.com/

    Uber Movement. https://movement.uber.com/

  46. [54]

    van Diggelen and P

    F. van Diggelen and P. Enge. The world’s first GPS MOOC and worldwide laboratory using smartphones. In Proc. ION GNSS+, pages 361–369, 2015

    2015

  47. [55]

    Vorona, A

    D. Vorona, A. Kipf, T. Neumann, and A. Kemper. DeepSPACE: Approximate geospatial query processing with deep learning. In SIGSPATIAL/GIS, pages 500–503. ACM, 2019

    2019

  48. [56]

    Zäschke, C

    T. Zäschke, C. Zimmerli, and M. C. Norrie. The ph-tree: a space-efficient storage structure and multi-dimensional index. In SIGMOD, pages 397–408. ACM, 2014

    2014

Pith tools

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