skip to main content


Title: Semantically Diverse Paths with Range and Origin Constraints
One of the most popular applications of Location Based Services (LBS) is recommending a Point of Interest (POI) based on user's preferences and geo-locations. However, the existing approaches have not tackled the problem of jointly determining: (a) a sequence of POIs that can be traversed within certain budget (i.e., limit on distance) and simultaneously provide a high-enough diversity; and (b) recommend the best origin (i.e., the hotel) for a given user, so that the desired route of POIs can be traversed within the specified constraints. In this work, we take a first step towards identifying this new problem and formalizing it as a novel type of a query. Subsequently, we present naïve solutions and experimental observations over a real-life datasets, illustrating the trade-offs in terms of (dis)associating the initial location from the rest of the POIs.  more » « less
Award ID(s):
1725702
NSF-PAR ID:
10309141
Author(s) / Creator(s):
 ;  ;  
Date Published:
Journal Name:
SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems, Virtual Event
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Recommending a Point of Interest (PoI) or a sequence of PoIs to visit based on user’s preferences and geo-locations has been one of the most popular applications of Location-Based Services (LBS). Variants have also been considered which take other factors into consideration, such as broader (implicit or explicit) semantic constraints as well as the limitations on the length of the trip. In this work, we present an efficient algorithmic solution to a novel query –PaDOC(Paths with Distance, Origin, and Category constraints) – which combines the generation of a path that (a) can be traversed within a user-specified budget (e.g., limit on distance), (b) starts at one of the user-specified origin locations (e.g., a hotel), and (c) contains PoIs from a user-specified list of PoI categories. We show that the problem of deciding whether such a path exists is an NP-hard problem. Based on a novel indexing structure, we propose two efficient algorithms for approximatePaDOCquery processing based on both conservative and progressive distance estimations. We conducted extensive experiments over real, publicly available datasets, demonstrating the benefits of the proposed methodologies over straightforward solutions.

     
    more » « less
  2. null (Ed.)
    Location-Based Services are often used to find proximal Points of Interest PoI - e.g., nearby restaurants and museums, police stations, hospitals, etc. - in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. For instance, rather than picking several close-by attractions with similar features - e.g., restaurants with similar menus; museums with similar art exhibitions - a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure - the Diversity Aggregated R-tree, based on which we devise efficient algorithms to generate the answer-set - i.e., the recommended locations among a set of given PoIs - relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline alternative approaches. 
    more » « less
  3. Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler’s first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance the tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods. 
    more » « less
  4. Social media services and location-based photo-sharing applications, such as Flickr, Twitter, and Instagram, provide a promising opportunity for studying tourist behaviors and activities. Researchers can use public accessible geo-tagged photos to map and analyze hotspots and tourist activities in various tourist attractions. This research studies geo-tagged Flickr photos collected from the Grand Canyon area within 12 months (2014/12/01–2015/11/30) using kernel density estimate (KDE) mapping, Exif (Exchangeable image file format) data, and dynamic time warping (DTW) methods. Different spatiotemporal movement patterns of tourists and popular points of interests (POIs) in the Grand Canyon area are identified and visualized in GIS maps. The frequency of Flickr’s monthly photos is similar (but not identical) to the actual tourist total numbers in the Grand Canyon. We found that winter tourists in the Grand Canyon explore fewer POIs comparing to summer tourists based on their Flickr data. Tourists using high-end cameras are more active and explore more POIs than tourists using smart phones photos. Weekend tourists are more likely to stay around the lodge area comparing to weekday tourists who have visited more remote areas in the park, such as the north of Pima Point. These tourist activities and spatiotemporal patterns can be used for the improvement of national park facility management, regional tourism, and local transportation plans. 
    more » « less
  5. As mobile devices become increasingly prevalent in society, the expected utility of such devices rises; arguably, the most impact comes from location-based services as they provide tremendous benefits to mobile users. These users also value privacy, i.e., keeping their locations and search queries private, but that is not easy to achieve. It has been previously proposed that user location privacy can be secured through the use of space filling curves due to their ability to preserve spatial proximity while hiding the actual physical locations. With a space filling curve, such as the Hilbert curve, an application that provides location-based services can allow the user to take advantage of those services without transmitting a physical location. Earlier research has uncovered vulnerabilities of such systems and proposed remedies. But those countermeasures were clearly aimed at reasonably large metropolitan areas. It was not clear if they were appropriate for small towns, which display sparsity of Points of Interest (POIs) and limited diversity in their categories. This paper studies the issue focusing on a small university town. 
    more » « less