Data structures for range-aggregate extent queries
A very important problem in computational geometry is range searching, where the goal is to preprocess a set, \(S\), of geometric objects so that the subset \(S' \subseteq S\) that is contained in a query range can be reported efficiently. However, in general, one is interested in generating 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.NEWLINENEWLINEIn this paper, the authors generalize this line of work by aggregating functions on point-sets that measure the extent or spread of the objects in the retrieved set \(S'\). The functions considered include closest pair, diameter, and width. These aggregation functions 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, the authors 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 \({\mathbb R}^d\), 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.NEWLINENEWLINEThe results in this paper 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 upper bounds on the sizes of such representations.
- Finding pairwise intersections inside a query range
- Applications of range query theory to relational data base join and selection operations
- Efficient external memory structures for range-aggregate queries
- On the power of the semi-separated pair decomposition
- Approximate range closest-pair queries
- Range search on tuples of points
- Closest-pair queries in fat rectangles
- Opportunistic data structures for range queries
- New bounds for range closest-pair problems
- Two-dimensional range diameter queries
- Aggregate-\textsc{Max} top-\(k\) nearest neighbor searching in the \(L_{1}\) plane
- scientific article; zbMATH DE number 2086302 (Why is no real title available?)
- Range-Aggregate Queries Involving Geometric Aggregation Operations
- On the Power of the Semi-Separated Pair Decomposition
- scientific article; zbMATH DE number 1945834 (Why is no real title available?)
- scientific article; zbMATH DE number 2081109 (Why is no real title available?)
- Searching for the closest-pair in a query translate
- Approximate range queries for clustering
- New bounds for range closest-pair problems
- Algorithms and Computation
- On top-\(k\) weighted sum aggregate nearest and farthest neighbors in the \(L_1\) plane
- Point set distance and orthogonal range problems with dependent geometric uncertainties
- scientific article; zbMATH DE number 2226802 (Why is no real title available?)
- Range-aggregate query problems involving geometric aggregation operations
- Algorithms and Computation
- Data structures for extension violations in a query range
- A dimension-reducing Fréchet simplification oracle
- Closest-pair queries and minimum-weight queries are equivalent for squares
This page was built for publication: Data structures for range-aggregate extent queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390147)
