Affordable Access

deepdyve-link
Publisher Website

An efficient algorithm for maximizing range sum queries in a road network.

Authors
  • Phan, Tien-Khoi
  • Jung, HaRim
  • Kim, Ung-Mo
Type
Published Article
Journal
The Scientific World JOURNAL
Publisher
Hindawi (The Scientific World)
Publication Date
Jan 01, 2014
Volume
2014
Pages
541602–541602
Identifiers
DOI: 10.1155/2014/541602
PMID: 25152915
Source
Medline
License
Unknown

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.

Report this publication

Statistics

Seen <100 times