Data structures for range-aggregate extent queries

Prosenjit Gupta; Ravi Janardan; Yokesh Kumar; Michiel Smid

Data structures for range-aggregate extent queries

Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, Michiel Smid

Computer Science and Engineering

Research output: Contribution to conference › Paper › peer-review

9 Scopus citations

Abstract

We consider a generalization of geometric range searching, with the goal of generating an informative "summary" of the objects contained in a query range via the application of a suitable aggregation function on these objects. We provide some of the first results for functions such as closest pair, diameter, and width that measure the extent (or "spread") of the retrieved set. We discuss a subset of our results, including closest pair queries on point-sets in the plane and on random pointsets in ℝ^d (d ≥ 2) and guaranteed-quality approximations for diameter and width queries in the plane, all for axes-parallel query rectangles.

Original language	English (US)
Pages	7-10
Number of pages	4
State	Published - 2008
Event	20th Annual Canadian Conference on Computational Geometry, CCCG 2008 - Montreal, QC, Canada Duration: Aug 13 2008 → Aug 15 2008

Other

Other	20th Annual Canadian Conference on Computational Geometry, CCCG 2008
Country/Territory	Canada
City	Montreal, QC
Period	8/13/08 → 8/15/08

Find It

Find It at U of M Libraries

Cite this

@conference{eb0ea0b7b33c4341b902b931b7d2ce5e,

title = "Data structures for range-aggregate extent queries",

abstract = "We consider a generalization of geometric range searching, with the goal of generating an informative {"}summary{"} of the objects contained in a query range via the application of a suitable aggregation function on these objects. We provide some of the first results for functions such as closest pair, diameter, and width that measure the extent (or {"}spread{"}) of the retrieved set. We discuss a subset of our results, including closest pair queries on point-sets in the plane and on random pointsets in ℝd (d ≥ 2) and guaranteed-quality approximations for diameter and width queries in the plane, all for axes-parallel query rectangles.",

author = "Prosenjit Gupta and Ravi Janardan and Yokesh Kumar and Michiel Smid",

year = "2008",

language = "English (US)",

pages = "7--10",

}

TY - CONF

T1 - Data structures for range-aggregate extent queries

AU - Gupta, Prosenjit

AU - Janardan, Ravi

AU - Kumar, Yokesh

AU - Smid, Michiel

PY - 2008

Y1 - 2008

N2 - We consider a generalization of geometric range searching, with the goal of generating an informative "summary" of the objects contained in a query range via the application of a suitable aggregation function on these objects. We provide some of the first results for functions such as closest pair, diameter, and width that measure the extent (or "spread") of the retrieved set. We discuss a subset of our results, including closest pair queries on point-sets in the plane and on random pointsets in ℝd (d ≥ 2) and guaranteed-quality approximations for diameter and width queries in the plane, all for axes-parallel query rectangles.

AB - We consider a generalization of geometric range searching, with the goal of generating an informative "summary" of the objects contained in a query range via the application of a suitable aggregation function on these objects. We provide some of the first results for functions such as closest pair, diameter, and width that measure the extent (or "spread") of the retrieved set. We discuss a subset of our results, including closest pair queries on point-sets in the plane and on random pointsets in ℝd (d ≥ 2) and guaranteed-quality approximations for diameter and width queries in the plane, all for axes-parallel query rectangles.

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

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

M3 - Paper

AN - SCOPUS:84860788605

SP - 7

EP - 10

T2 - 20th Annual Canadian Conference on Computational Geometry, CCCG 2008

Y2 - 13 August 2008 through 15 August 2008

ER -

Data structures for range-aggregate extent queries

Abstract

Other

Find It

Other files and links

Fingerprint

Cite this