CALBA: Capacity-aware location-based advertising in temporary social networks

A temporary social network (TSN) is confined to a specific place (e.g., hotel and shopping mall) or activity (e.g., concert and exhibition) in which the TSN service provider allows nearby third party vendors (e.g., restaurants and stores) to advertise their goods or services to its registered users. However, simply broadcasting all the vendors' advertisements to all the users in the TSN may cause the service provider to lose its fans. In this paper, we present Capacity-Aware Location-Based Advertising (CALBA), which is a framework designed for TSNs to select vendors as advertising sources for mobile users. In CALBA we measure the relevance of a vendor to a user by considering their geographical proximity and the user's preferences. Our goal is to maximize the overall relevance of selected vendors for a user with the constraint that the total advertising frequency of the selected vendors should not exceed the user's specified capacity. First, we model the snapshot selection problem as 0-1 knapsack and solve it using an approximation method. Then, CALBA keeps track of the selection result for moving users by employing a safe region technique that can reduce its computational cost. We also propose three pruning rules and a unique access order to effectively prune vendors which could not affect a safe region, in order to improve the efficiency of the client-side computation. We evaluate the performance of CALBA based on a real location-based social network data set crawled from Foursquare. Experimental results show that CALBA outperforms a naïve approach which periodically invokes the snapshot vendor selection. © 2013 ACM.