title: An efficient algorithm for maximizing range sum queries in a road network.
abstract: Given a set of positive-weighted points and a query rectangle r (specified by a client) of given extents, the goal of a maximizing range sum (MaxRS) query is to find the optimal location of r such that the total weights of all the points covered by r are maximized. All existing methods for processing MaxRS queries assume the Euclidean distance metric. In many location-based applications, however, the motion of a client may be constrained by an underlying (spatial) road network; that is, the client cannot move freely in space. This paper addresses the problem of processing MaxRS queries in a road network. We propose the external-memory algorithm that is suited for a large road network database. In addition, in contrast to the existing methods, which retrieve only one optimal location, our proposed algorithm retrieves all the possible optimal locations. Through simulations, we evaluate the performance of the proposed algorithm.
authors.affiliation: School of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of Korea.
authors.forename: Tien-Khoi
authors.identifier: 0000-0001-5187-7409
authors.initials: TK
authors.lastname: Phan
authors.affiliation: School of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of Korea.
authors.forename: HaRim
authors.initials: H
authors.lastname: Jung
authors.affiliation: School of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of Korea ; Department of Computer Engineering, Sungkyunkwan University, Republic of Korea.
authors.forename: Ung-Mo
authors.initials: UM
authors.lastname: Kim
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D008962:Models, Theoretical