TY - JOUR

T1 - Efficient non-intersection queries on aggregated geometric data

AU - Gupta, Prosenjit

AU - Janardan, Ravi

AU - Smid, Michiel

PY - 2005/10/24

Y1 - 2005/10/24

N2 - Let S be a set of geometric objects that are aggregated into disjoint groups. The problem considered is that of preprocessing S so that for any query object, q, the distinct groups such that no objects from those groups are intersected by q can be reported efficiently. The goal is to devise solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding intersection problem for aggregated data and reporting the complement, or (ii) querying with the complement of q are either expensive or incorrect. Efficient, output-sensitive solutions are given to several non-intersection searching problems on aggregated data, using methods such as geometric duality, sparsification, persistence, filtering search, and pruning.

AB - Let S be a set of geometric objects that are aggregated into disjoint groups. The problem considered is that of preprocessing S so that for any query object, q, the distinct groups such that no objects from those groups are intersected by q can be reported efficiently. The goal is to devise solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding intersection problem for aggregated data and reporting the complement, or (ii) querying with the complement of q are either expensive or incorrect. Efficient, output-sensitive solutions are given to several non-intersection searching problems on aggregated data, using methods such as geometric duality, sparsification, persistence, filtering search, and pruning.

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

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

M3 - Conference article

AN - SCOPUS:26844432770

VL - 3595

SP - 544

EP - 553

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

T2 - 11th Annual International Conference on Computing and Combinatorics, COCOON 2005

Y2 - 16 August 2005 through 29 August 2005

ER -