Efficient Non-intersection Queries on Aggregated Geometric Data
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.
Prosenjit Gupta Ravi Janardan Michiel Smid
International Institute of Information Technology, Gachibowli Hyderabad 500 019, India Department of Computer Science & Engineering, University of Minnesota Minneapolis, MN 55455, USA Department of Computer Science, Carleton University, Ottawa, Canada K1S 5B6
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
544-553
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）