Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

We wish you a happy and safe holiday season and all the best for 2025


Optimal k-Constraint Coverage Queries on Spatial Objects

Xu, C., Wang, Y., Gu, Y., Lin, S. and Yu, G.

    Given a set of spatial objects, our task is to assign all the objects to the minimum number of service sites and to find the regions for building these service sites. Each service site has a coverage region (i.e., an area of service) and a capacity (i.e., a maximum number of objects it can serve, called k-constraint). The service sites can provide service for objects located within the coverage regions. Aiming at this problem, we propose a novel kind of spatial queries, called Optimal k-Constraint Coverage (OCC) queries. An OCC query returns some feasible regions such that setting up the minimum number of service sites within these regions will guarantee that all the spatial objects can be served. Furthermore, an optimal coverage scheme to assign the objects to these service sites is retrieved by this query as well. Due to the capacity constraints, objects located within the coverage region of a service site may not be assigned to one service site. Therefore, the cost of searching an optimal coverage over all possible coverage schemes becomes prohibitive. To answer OCC queries efficiently, we devise a general query framework, which provides two solutions to cope with OCC query processing. The naive solution only returns a local optimum without insuring the minimum number of service sites. To improve it, the other solution called Optimal Coverage Algorithm (Opt-C) is proposed to retrieve an optimal coverage scheme. During the procedure, we present refinement methods for reducing intermediate results of OCC queries to improve the efficiency. The performance of the proposed methods is demonstrated by the extensive experiments with both synthetic and real datasets.
Cite as: Xu, C., Wang, Y., Gu, Y., Lin, S. and Yu, G. (2012). Optimal k-Constraint Coverage Queries on Spatial Objects. In Proc. Australasian Database Conference (ADC 2012) Melbourne, Australia. CRPIT, 124. Zhang, R. and Zhang, Y. Eds., ACS. 41-50
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS