Memory-efficient spatial histogram construction

One or more non-transitory computer-readable media carrying one or more sequences of instructions that, when executed by one or more processors, cause the one or more processors to carry out:

• accessing a hierarchical spatial index comprising a plurality of leaf nodes and a plurality of non-leaf nodes, each leaf node of the plurality of leaf nodes representing a bounding region containing a spatial object stored in a spatial database, each non-leaf node of the plurality of non-leaf nodes representing a bounding region at least partially containing one or more spatial objects associated with one or more leaf nodes, wherein any child node descending from any of the plurality of non-leaf nodes is at least partially contained within a bounding region of its ancestor non-leaf nodes;
• determining a plurality of selected nodes selected from the plurality of non-leaf nodes;
• determining a weight for each particular node in the plurality of selected nodes, the weight indicating a number of spatial objects, of the spatial objects stored in the spatial database, that are contained within the bounding region represented by said each particular node;
• determining a spatial partitioning of bounding regions represented by the plurality of selected nodes by applying a partitioning procedure to recursively divide a space containing the bounding regions represented by the plurality of selected nodes to determine a plurality of partitions containing the bounding regions represented by the plurality of selected nodes;
• generating a spatial histogram based on the spatial partitioning of the bounding regions represented by the plurality of selected nodes and the weights of the plurality of selected nodes;
• and
• outputting, in response to a query, a query result for the spatial database based on the spatial histogram.