TY - JOUR

T1 - Data structures for range-aggregate extent queries

AU - Gupta, Prosenjit

AU - Janardan, Ravi

AU - Kumar, Yokesh

AU - Smid, Michiel

PY - 2014

Y1 - 2014

N2 - A fundamental and well-studied problem in computational geometry is range searching, where the goal is to preprocess a set, S, of geometric objects (e.g., points in the plane) so that the subset S′âŠ†S that is contained in a query range (e.g., an axes-parallel rectangle) can be reported efficiently. However, in many situations, what is of interest is to generate a more informative "summary" of the output, obtained by applying a suitable aggregation function on S′. Examples of such aggregation functions include count, sum, min, max, mean, median, mode, and top-k that are usually computed on a set of weights defined suitably on the objects. Such range-aggregate query problems have been the subject of much recent research in both the database and the computational geometry communities. In this paper, we further generalize this line of work by considering aggregation functions on point-sets that measure the extent or "spread" of the objects in the retrieved set S′. The functions considered here include closest pair, diameter, and width. The challenge here is that these aggregation functions (unlike, say, count) are not efficiently decomposable in the sense that the answer to S′ cannot be inferred easily from answers to subsets that induce a partition of S′. Nevertheless, we have been able to obtain space- and query-time-efficient solutions to several such problems including: closest pair queries with axes-parallel rectangles on point sets in the plane and on random point-sets in Rd (d≥2), closest pair queries with disks on random point-sets in the plane, diameter queries on point-sets in the plane, and guaranteed-quality approximations for diameter and width queries in the plane. Our results are based on a combination of geometric techniques, including multilevel range trees, Voronoi Diagrams, Euclidean Minimum Spanning Trees, sparse representations of candidate outputs, and proofs of (expected) upper bounds on the sizes of such representations.

AB - A fundamental and well-studied problem in computational geometry is range searching, where the goal is to preprocess a set, S, of geometric objects (e.g., points in the plane) so that the subset S′âŠ†S that is contained in a query range (e.g., an axes-parallel rectangle) can be reported efficiently. However, in many situations, what is of interest is to generate a more informative "summary" of the output, obtained by applying a suitable aggregation function on S′. Examples of such aggregation functions include count, sum, min, max, mean, median, mode, and top-k that are usually computed on a set of weights defined suitably on the objects. Such range-aggregate query problems have been the subject of much recent research in both the database and the computational geometry communities. In this paper, we further generalize this line of work by considering aggregation functions on point-sets that measure the extent or "spread" of the objects in the retrieved set S′. The functions considered here include closest pair, diameter, and width. The challenge here is that these aggregation functions (unlike, say, count) are not efficiently decomposable in the sense that the answer to S′ cannot be inferred easily from answers to subsets that induce a partition of S′. Nevertheless, we have been able to obtain space- and query-time-efficient solutions to several such problems including: closest pair queries with axes-parallel rectangles on point sets in the plane and on random point-sets in Rd (d≥2), closest pair queries with disks on random point-sets in the plane, diameter queries on point-sets in the plane, and guaranteed-quality approximations for diameter and width queries in the plane. Our results are based on a combination of geometric techniques, including multilevel range trees, Voronoi Diagrams, Euclidean Minimum Spanning Trees, sparse representations of candidate outputs, and proofs of (expected) upper bounds on the sizes of such representations.

KW - Closest pair

KW - Computational geometry

KW - Data structures

KW - Diameter

KW - Width

UR - http://www.scopus.com/inward/record.url?scp=84888303012&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84888303012&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2009.08.001

DO - 10.1016/j.comgeo.2009.08.001

M3 - Article

AN - SCOPUS:84888303012

SN - 0925-7721

VL - 47

SP - 329

EP - 347

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 2 PART C

ER -