Please use this identifier to cite or link to this item:
Title: MaxFirst: an Efficient Method for Finding Optimal Regions
Keywords: MaxFirst, MaxBRKNN, Optimal Region, NLCs, Moving Objects, Quad Tree
Issue Date: 28-Jun-2010
Citation: ZHOU ZENAN (2010-06-28). MaxFirst: an Efficient Method for Finding Optimal Regions. ScholarBank@NUS Repository.
Abstract: The MaxBRNN problem finds a region such that setting up a new service site within this region would guarantee the maximum number of customers by proximity. This problem assumes that each customer only goes to his/her nearest service site. However, in reality, a customer tends to go to his/her k nearest service sites. To handle this, MaxBRNN can be extended to the MaxBRkNN problem which finds an optimal region such that setting up a service site in this region guarantees the maximum number of customers who would consider the site as one of their k nearest service locations. We further generalize the MaxBRkNN problem to reflect the real world scenario where customers may have different preferences for different service sites, and at the same time, service sites may have preferred targeted customers. In this thesis, we present an efficient solution called MaxFirst to solve this generalized MaxBRkNN problem. The algorithm works by partitioning the space into quadrants and searches only in those quadrants that potentially contain an optimal region. During the space partitioning, we compute the upper and lower bounds of the size of a quadrant?s BRkNN, and use these bounds to prune the unpromising quadrants. Experiment results show that MaxFirst can be two to three orders of magnitude faster than the state-of-the-art algorithm.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
ZhouZN.pdf387.14 kBAdobe PDF



Page view(s)

checked on Apr 19, 2019


checked on Apr 19, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.