More Like this

1. Distance, Origin and Category Constrained Paths

   https://doi.org/10.1145/3596601  

   Teng, Xu; Trajcevski, Goce; Züfle, Andreas (September 2023, ACM Transactions on Spatial Algorithms and Systems)

   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. Semantically Diverse Path Search

   https://doi.org/10.1109/MDM48529.2020.00028  

   Teng, Xu; Trajcevski, Goce; Kim, Joon-Seok; Zufle, Andreas (June 2020, 21st {IEEE} International Conference on Mobile Data Management, {MDM} 2020, Versailles, France, June 30 - July 3, 2020)

   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. Time-sensitive POI Recommendation by Tensor Completion with Side Information

   Hui, Bo; Yan, Da; Ku, Wei-Shinn (January 2022, Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE))

   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. A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems

   https://doi.org/10.1007/s11590-023-02008-6  

   Liang, Wei; Zhang, Zhao; Du, Ding-Zhu (May 2023, Optimization Letters)

   In a sweep cover problem, mobile sensors move around to collect information from positions of interest (PoIs) periodically and timely. A PoI is sweep-covered if it is visited at least once in every time period t. In this paper, we study approximation algorithms on three types of sweep cover problems. The partial sweep cover problem (PSC) aims to use the minimum number of mobile sensors to sweep-cover at least a given number of PoIs. The prize-collecting sweep cover problem aims to minimize the cost of mobile sensors plus the penalties on those PoIs that are not sweep-covered. The budgeted sweep cover problem (BSC) aims to use a budgeted number N of mobile sensors to sweep-cover as many PoIs as possible. We propose a unified approach which can yield approximation algorithms for PSC and PCSC within approximation ratio at most 8, and a bicriteria (4, 1 2 )-approximation algorithm for BSC (that is, no more than 4N mobile sensors are used to sweep-cover at least 1 2 opt PoIs, where opt is the number of PoIs that can be sweep-covered by an optimal solution). Furthermore, our results for PSC and BSC can be extended to their weighted version, and our algorithm for PCSC answers a question proposed in Liang etal. (Theor Comput Sci, 2022) on PCSC 

   more » « less
5. Exploring Spatial Transformation-Based Privacy in a Small Town

   Jacobs, Aidan; Mazumdar, Subhasish (June 2023, MOBILITY 2023 : The Thirteenth International Conference on Mobile Services, Resources, and Users)

   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