An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network
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 processin...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/541602 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850158844041232384 |
|---|---|
| author | Tien-Khoi Phan HaRim Jung Ung-Mo Kim |
| author_facet | Tien-Khoi Phan HaRim Jung Ung-Mo Kim |
| author_sort | Tien-Khoi Phan |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-616744b6ff0f4e70b62fa2801d38072f |
| institution | OA Journals |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-616744b6ff0f4e70b62fa2801d38072f2025-08-20T02:23:45ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/541602541602An Efficient Algorithm for Maximizing Range Sum Queries in a Road NetworkTien-Khoi Phan0HaRim Jung1Ung-Mo Kim2School of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of KoreaSchool of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of KoreaSchool of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon 440-746, Republic of KoreaGiven 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.http://dx.doi.org/10.1155/2014/541602 |
| spellingShingle | Tien-Khoi Phan HaRim Jung Ung-Mo Kim An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network The Scientific World Journal |
| title | An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network |
| title_full | An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network |
| title_fullStr | An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network |
| title_full_unstemmed | An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network |
| title_short | An Efficient Algorithm for Maximizing Range Sum Queries in a Road Network |
| title_sort | efficient algorithm for maximizing range sum queries in a road network |
| url | http://dx.doi.org/10.1155/2014/541602 |
| work_keys_str_mv | AT tienkhoiphan anefficientalgorithmformaximizingrangesumqueriesinaroadnetwork AT harimjung anefficientalgorithmformaximizingrangesumqueriesinaroadnetwork AT ungmokim anefficientalgorithmformaximizingrangesumqueriesinaroadnetwork AT tienkhoiphan efficientalgorithmformaximizingrangesumqueriesinaroadnetwork AT harimjung efficientalgorithmformaximizingrangesumqueriesinaroadnetwork AT ungmokim efficientalgorithmformaximizingrangesumqueriesinaroadnetwork |