Share Email Print
cover

Proceedings Paper

Efficiently querying spatial histograms
Author(s): Yujun Wang; Simone Santini; Amarnath Gupta
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

In this paper, we examine the problem of efficiently computing a class of aggregate functions on regions of space. We first formalize region-based aggregations for a large class of efficient geometric aggregations. The idea is to represent the query object with pre-defined objects with set operations, and compute the aggregation using the pre-computed aggregation values. We first show that it applies to existing results about points and rectangular objects. Since it is defined using set theory instead of object shapes, it can be applied to polygons. Given a database D of polygonal regions, a tessellation T of the plane, and a query polygon q constructed from T, we prove that the aggregation of q can be calculated by the aggregation over triangles and lines constructed from segments and vertices in q, which can be pre-computed. The query time complexity is O(klogn), where k is the size of query polygon and n is the size of T.

Paper Details

Date Published: 17 January 2005
PDF: 12 pages
Proc. SPIE 5682, Storage and Retrieval Methods and Applications for Multimedia 2005, (17 January 2005); doi: 10.1117/12.592044
Show Author Affiliations
Yujun Wang, Univ. of California/San Diego (United States)
Simone Santini, Univ. of California/San Diego (United States)
Amarnath Gupta, Univ. of California/San Diego (United States)


Published in SPIE Proceedings Vol. 5682:
Storage and Retrieval Methods and Applications for Multimedia 2005
Rainer W. Lienhart; Noboru Babaguchi; Edward Y. Chang, Editor(s)

© SPIE. Terms of Use
Back to Top