閱讀全文 | |
篇名 |
Exact and Heuristic Algorithms for Some Spatial-aware Interest Group Query Problems
|
---|---|
並列篇名 | Exact and Heuristic Algorithms for Some Spatial-aware Interest Group Query Problems |
作者 | Chih-Yang Huang、Po-Chuan Chien、Yen Hung Chen |
英文摘要 | Location-based social networks are important issues in the recent decade. In modern social networks, such as Twitter, Facebook, and Plurk, attempt to get the accurate address positions from their users, and try to reduce the gap between virtuality and reality. This paper mainly aims at both the interests of Internet users and their real positions. This issue is called the spatial-aware interest group query problem (SIGQP). Given a user set U with n users, a keyword set W with m words, and a spatial object set S with s items, each of which contains one or multiple keywords. If a user checks in a certain spatial object, it means the user could be interested in that part of keywords, which is countable to clarify the interests of the user. The SIGQP then tries to find a k-user set Uk, k ≤ n, such that the union of keywords of these k users will equal to W, and additionally, the diameter (longest Euclidean distance of two arbitrary users in Uk) should be as small as possible. The SIGQP has been proved as NP-Complete, and two heuristic algorithms have been proposed. Extended from SIGQP, another problem is in finding the smallest k for Uk to cover all the keywords, with the users’ distance as the secondary criterion, called as “minimum user spatial-aware interest group query problem” (MUSIGQP). This paper designs a branch & bound method and a measure & conquer method to solve SIGQP and MUSIGQP respectively, and a performance analysis is given. |
起訖頁 | 1199-1206 |
關鍵詞 | Spatial-aware interest group query problem、Exact algorithms、Branch & bound、Measure & conquer、Location-based service |
刊名 | 網際網路技術學刊 |
期數 | 202007 (21:4期) |
出版單位 | 台灣學術網路管理委員會 |
DOI |
|
QR Code | |
該期刊 上一篇
| On Phalanx Graph Search Number |
該期刊 下一篇
| A Combined Time Series Model for the Prediction of Social Network Popularity and Content Evolution |