Trip planning queries with location privacy in spatial databases

Privacy has become a major concern for the users of location-based services (LBSs) and researchers have focused on protecting user privacy for different location-based queries. In this paper, we propose techniques to protect location privacy of users for trip planning (TP) queries, a novel type of query in spatial databases. A TP query enables a user to plan a trip with the minimum travel distance, where the trip starts from a source location, goes through a sequence of points of interest (POIs) (e.g., restaurant, shopping center), and ends at a destination location. Due to privacy concerns, users may not wish to disclose their exact locations to the location-based service provider (LSP). In this paper, we present the first comprehensive solution for processing TP queries without disclosing a user’s actual source and destination locations to the LSP. Our system protects the user’s privacy by sending either a false location or a cloaked location of the user to the LSP but provides exact results of the TP queries. We develop a novel technique to refine the search space as an elliptical region using geometric properties, which is the key idea behind the efficiency of our algorithms. To further reduce the processing overhead while computing a trip from a large POI database, we present an approximation algorithm for privacy preserving TP queries. Extensive experiments show that the proposed algorithms evaluate TP queries in real time with the desired level of location privacy.     

Reverse direction-based surrounder queries for mobile recommendations

This paper proposes a new spatial query called a reverse direction-based surrounder (RDBS) query, which retrieves a user who is seeing a point of interest (POI) as one of their direction-based surrounders (DBSs). According to a user, one POI can be dominated by a second POI if the POIs are directionally close and the first POI is farther from the user than the second is. Two POIs are directionally close if their included angle with respect to the user is smaller than an angular threshold ??. If a POI cannot be dominated by another POI, it is a DBS of the user. We also propose an extended query called competitor RDBS query. POIs that share the same RDBSs with another POI are defined as competitors of that POI. We design algorithms to answer the RDBS queries and competitor queries. The experimental results show that the proposed algorithms can answer the queries efficiently.     

Assessing the influence of point-of-interest features on the classification of place categories

Points of interest (POIs) digitally represent real-world amenities as point locations. POI categories (e.g. restaurant, hotel, museum etc.) play a prominent role in several location-based applications such as social media, navigation, recommender systems, geographic information retrieval tools, and travel-related services. The majority of user queries in these applications center around POI categories. For instance, people often search for the closest pub or the best value-for-money hotel in an area. To provide valid answers to such queries, accurate and consistent information on POI categories is an essential requirement. Nevertheless, category-based annotations of POIs are often missing. The task of annotating unlabeled POIs in terms of their categories — known as POI classification — is commonly achieved by means of machine learning (ML) models, often referred to as classifiers. Central to this task is the extraction of known features from pre-labeled POIs in order to train the classifiers and, then, use the trained models to categorize unlabeled POIs. However, the set of features used in this process can heavily influence the classification results. Research on defining the influence of different features on the categorization of POIs is currently lacking. This paper contributes a study of feature importance for the classification of unlabeled POIs into categories. We define five feature sets that address operation based, review-based, topic-based, neighborhood-based, and visual attributes of POIs. Contrary to existing studies that predominantly use multi-class classification approaches, and in order to assess and rank the influence of POI features on the categorization task, we propose both a multi-class and a binary classification approach. These, respectively, predict the place category among a specified set of POI categories, or indicate whether a POI belongs to a certain category. Using POI data from Amsterdam and Athens to implement and evaluate our study approach, we show that operation based features, such as opening or visiting hours throughout the day, are the most important place category predictors. Moreover, we demonstrate that the use of feature combinations, as opposed to the use of individual features, improves the classification performance by an average of 15%, in terms of F1-score.     

Metro Transit‐Centric Visualization for City Tour Planning

In general, city trip planning consists of two main steps: knowing Points‐Of‐Interest (POIs), and then planning a tour route from the current point to next preferred POIs. We mainly consider the metro for traveling around touristic cities as the main means of transportation. In this context, existing tools lack a capability to effectively visualize POIs on the metro map for trip planning. To bridge this gap, we propose an interactive framework that holistically combines presentations of POIs and a metro network. Our idea is to identify popular POIs based on visual worth computation, and to introduce POI discovery for effectively identifying POIs within reach of a metro network for users. We use octilinear layouts to highlight the metro network, and show representative POI images in the layout space visualized within a user‐specified viewing window. We have implemented our working prototype showing touristic cities with a metro network. We have factored out various design guidelines that are basis for designing our method, and validated our approach with a user study surveying 70 individuals.     

Personalized trip recommendation for tourists based on user interests,points of interest visit durations and visit recency

Tour recommendation and itinerary planning are challenging tasks for tourists, due to their need to select points of interest (POI) to visit in unfamiliar cities and to select POIs that align with their interest preferences and trip constraints. We propose an algorithm called PersTour for recommending personalized tours using POI popularity and user interest preferences, which are automatically derived from real-life travel sequences based on geo-tagged photographs. Our tour recommendation problem is modeled using a formulation of the Orienteering problem and considers user trip constraints such as time limits and the need to start and end at specific POIs. In our work, we also reflect levels of user interest based on visit durations and demonstrate how POI visit duration can be personalized using this time-based user interest. Furthermore, we demonstrate how PersTour can be further enhanced by: (i) a weighted updating of user interests based on the recency of their POI visits and (ii) an automatic weighting between POI popularity and user interests based on the tourist’s activity level. Using a Flickr dataset of ten cities, our experiments show the effectiveness of PersTour against various collaborative filtering and greedy-based baselines, in terms of tour popularity, interest, recall, precision and F\(_1\)-score. In particular, our results show the merits of using time-based user interest and personalized POI visit durations, compared to the current practice of using frequency-based user interest and average visit durations.     

Exploring Bikesharing Travel Patterns and Trip Purposes Using Smart Card Data and Online Point of Interests

The primary objective of this study was to investigate the bikesharing travel patterns and trip purposes by combining smart card data and online point of interests (POIs). A large-scale smart card trip data was collected from the bikesharing system in New York City. The POIs surrounding each station were obtained from Google Places API. K-means clustering analysis was first applied to divide bikesharing stations into five types based on their surrounding POIs. The Latent Dirichlet Allocation (LDA) analysis was then conducted to discover the hidden bikesharing travel patterns and trip purposes using the identified station types and smart card data. The performance of the LDA models with and without POI data was compared to identify whether the POI data should be used. Finally, a practical application of the proposed methods in bikesharing planning and operation was discussed. The result of comparative analyses verified the importance of POI data in exploring bikesharing travel patterns and trip purposes. The results of LDA model showed that the most prevalent travel purpose in New York City is taking public bike for eating, followed by shopping and transferring to other public transit systems. In addition, the result also suggested that people living around the bikesharing stations are more likely to transfer to other commuting tools on the morning peak and ride for home after work. The proposed methods can be used to provide useful guidance and suggestions for transportation agency to develop strategies and regulation that aim at improving the operations of bikesharing systems.     

Heuristics for the time dependent team orienteering problem: Application to tourist route planning

The Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) can be used to model several real life problems. Among them, the route planning problem for tourists interested in visiting multiple points of interest (POIs) using public transportation. The main objective of this problem is to select POIs that match tourist preferences, taking into account a multitude of parameters and constraints while respecting the time available for sightseeing in a daily basis and integrating public transportation to travel between POIs (Tourist Trip Design Problem, TTDP). TDTOPTW is NP-hard while almost the whole body of the related literature addresses the non-time dependent version of the problem. The only TDTOPTW heuristic proposed so far is based on the assumption of periodic transit service schedules. Herein, we propose efficient cluster-based heuristics for the TDTOPTW which yield high quality solutions, take into account time dependency in calculating travel times between POIs and make no assumption on periodic service schedules. The validation scenario for our prototyped algorithms involved the transit network and real POI datasets compiled from the metropolitan area of Athens (Greece). Our TTDP algorithms handle arbitrary (i.e. determined at query time) rather than fixed start/end locations for derived tourist itineraries.     

Approximate and exact hybrid algorithms for private nearest-neighbor queries with database protection

Mobile devices with global positioning capabilities allow users to retrieve points of interest (POI) in their proximity. To protect user privacy, it is important not to disclose exact user coordinates to un-trusted entities that provide location-based services. Currently, there are two main approaches to protect the location privacy of users: (i) hiding locations inside cloaking regions (CRs) and (ii) encrypting location data using private information retrieval (PIR) protocols. Previous work focused on finding good trade-offs between privacy and performance of user protection techniques, but disregarded the important issue of protecting the POI dataset D. For instance, location cloaking requires large-sized CRs, leading to excessive disclosure of POIs (O(|D|) in the worst case). PIR, on the other hand, reduces this bound to \(O(\sqrt{|D|})\), but at the expense of high processing and communication overhead. We propose hybrid, two-step approaches for private location-based queries which provide protection for both the users and the database. In the first step, user locations are generalized to coarse-grained CRs which provide strong privacy. Next, a PIR protocol is applied with respect to the obtained query CR. To protect against excessive disclosure of POI locations, we devise two cryptographic protocols that privately evaluate whether a point is enclosed inside a rectangular region or a convex polygon. We also introduce algorithms to efficiently support PIR on dynamic POI sub-sets. We provide solutions for both approximate and exact NN queries. In the approximate case, our method discloses O(1) POI, orders of magnitude fewer than CR- or PIR-based techniques. For the exact case, we obtain optimal disclosure of a single POI, although with slightly higher computational overhead. Experimental results show that the hybrid approaches are scalable in practice, and outperform the pure-PIR approach in terms of computational and communication overhead.     

Time and Location Aware Points of Interest Recommendation in Location-Based Social Networks

The wide spread of location-based social networks brings about a huge volume of user check-in data, which facilitates the recommendation of points of interest (POIs). Recent advances on distributed representation shed light on learning low dimensional dense vectors to alleviate the data sparsity problem. Current studies on representation learning for POI recommendation embed both users and POIs in a common latent space, and users’ preference is inferred based on the distance/similarity between a user and a POI. Such an approach is not in accordance with the semantics of users and POIs as they are inherently different objects. In this paper, we present a novel translation-based, time and location aware (TransTL) representation, which models the spatial and temporal information as a relationship connecting users and POIs. Our model generalizes the recent advances in knowledge graph embedding. The basic idea is that the embedding of a <time, location> pair corresponds to a translation from embeddings of users to POIs. Since the POI embedding should be close to the user embedding plus the relationship vector, the recommendation can be performed by selecting the top-k POIs similar to the translated POI, which are all of the same type of objects. We conduct extensive experiments on two real-world datasets. The results demonstrate that our TransTL model achieves the state-of-the-art performance. It is also much more robust to data sparsity than the baselines.     

A Generative Model Approach for Geo-Social Group Recommendation

With the development and prevalence of online social networks, there is an obvious tendency that people are willing to attend and share group activities with friends or acquaintances. This motivates the study on group recommendation, which aims to meet the needs of a group of users, instead of only individual users. However, how to aggregate different preferences of different group members is still a challenging problem: 1) the choice of a member in a group is influenced by various factors, e.g., personal preference, group topic, and social relationship; 2) users have different influences when in different groups. In this paper, we propose a generative geo-social group recommendation model (GSGR) to recommend points of interest (POIs) for groups. Specifically, GSGR well models the personal preference impacted by geographical information, group topics, and social influence for recommendation. Moreover, when making recommendations, GSGR aggregates the preferences of group members with different weights to estimate the preference score of a group to a POI. Experimental results on two datasets show that GSGR is effective in group recommendation and outperforms the state-of-the-art methods.     

Optimal group route query: Finding itinerary for group of users in spatial databases

The increasing popularity of location-based applications creates new opportunities for users to travel together. In this paper, we study a novel spatio-social optimization problem , i.e., Optimal Group Route, for multi-user itinerary planning. With our problem formulation, users can individually specify sources and destinations, preferences on the Point-of-interest (POI) categories, as well as the distance constraints. The goal is to find a itinerary that can be traversed by all the users while maximizing the group’s preference of POI categories in the itinerary. Our work advances existing group trip planning studies by maximizing the group’s social experience. To this end, individual preferences of POI categories are aggregated by considering the agreement and disagreement among group members. Furthermore, planning a multi-user itinerary on large road networks is computationally challenging. We propose two efficient greedy algorithms with bounded approximation ratio, one exact solution which computes the optimal itinerary by exploring a limited number of paths in the road network, and a scaled approximation algorithm to speed up the dynamic programming employed by the exact solution. We conduct extensive empirical evaluations on two real-world road network/POI datasets and our results confirm the effectiveness and efficiency of our solutions.     

融合时空信息和兴趣点重要性的POI推荐算法

针对兴趣点（POI）推荐研究中数据噪声过滤问题和不同POI的重要性问题,提出了一种融合时空信息和兴趣点重要性的POI推荐算法——RecSI。首先,根据POI的地理信息和POI之间相互吸引力过滤噪声数据,缩小候选集的范围;其次,根据用户在一天中不同的时间段对POI类别的偏好程度,结合POI的流行度计算出用户的偏好得分;然后,结合社交信息和加权PageRank算法计算POI重要性;最后,将用户的偏好得分和POI重要性线性结合,以向用户推荐TOP-K的POI。在Foursquare真实的签到数据集上的实验结果表明,RecSI算法的精确率和召回率比最优的GCSR算法分别提高了12.5%和6%,验证了RecSI算法的有效性。     

融合时空信息和兴趣点重要性的POI推荐算法

针对兴趣点（POI）推荐研究中数据噪声过滤问题和不同POI的重要性问题，提出了一种融合时空信息和兴趣点重要性的POI推荐算法——RecSI。首先，根据POI的地理信息和POI之间相互吸引力过滤噪声数据，缩小候选集的范围；其次，根据用户在一天中不同的时间段对POI类别的偏好程度，结合POI的流行度计算出用户的偏好得分；然后，结合社交信息和加权PageRank算法计算POI重要性；最后，将用户的偏好得分和POI重要性线性结合，以向用户推荐TOP-K的POI。在Foursquare真实的签到数据集上的实验结果表明，RecSI算法的精确率和召回率比最优的GCSR算法分别提高了12.5%和6%，验证了RecSI算法的有效性。     

基于时空循环神经网络的下一个兴趣点推荐方法

下一个兴趣点推荐已经成为基于位置的社交网络(location-based social networks,LBSNs)中一个重要任务。现有的模型没有深入考虑相邻签到兴趣点之间的转移时空信息,无法对用户访问下一个兴趣点的长短时间偏好和远近距离偏好进行有效建模。本文通过对循环神经网络(recurrent neural network, RNN)进行扩展,提出一个新的基于会话的时空循环神经网络模型(sesson-based spatial-temporal recurrent neural network, SST-RNN)用于下一个兴趣点推荐。该模型通过设置时间转移矩阵和空间转移矩阵分别对用户的时间和空间偏好信息进行建模,综合考虑连续签到兴趣点的序列信息、时空信息以及用户偏好进行下一个兴趣点推荐。通过在2个真实公开的数据集上进行实验,结果显示本文提出的SST-RNN模型的推荐效果比主流的推荐模型有显著提升。在Foursquare和CA数据集上,ACC@5评价指标分别提升了36.38%和13.81%,MAP评价指标分别提升了30.72%和17.26%。     

The partial sequenced route query with traveling rules in road networks

In modern geographic information systems, route search represents an important class of queries. In route search related applications, users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI) with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP-hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution, the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly longer than the shortest route.     

空间语义增强下的城市交通事故数据可视分析

目的 海量城市交通事故数据可能蕴含有交通事故的空间模式，挖掘出交通事故的空间模式有助于开展交通事故的防治工作。目前交通管理部门虽然记录了交通事故发生地的空间位置信息，但没有对事故发生地进行空间语义描述，从而影响对交通事故空间模式的深入分析。因此，提出一种交通事故数据空间语义增强方法，并设计了一套可视分析系统。方法 基于城市兴趣点来增强交通事故数据的空间语义。以事故发生点为中心获取周围城市兴趣点，使用特征向量刻画兴趣点的数量、类别及其与事故发生点的距离，并称此向量为空间语义特征向量。将空间语义特征向量和相应的交通事故关联，以达到增强其空间语义的目的。然后，基于空间语义特征向量，使用自组织映射聚类算法对交通事故进行聚类分析，根据其空间语义特征将交通事故分为若干类别。最后，通过使用地图视图展示事故点数据、聚类视图和平行坐标视图展示聚类分析的结果及其空间语义特征的可视化方法，对交通事故的空间模式进行分析。结果 针对空间语义增强的交通事故数据以及相关分析任务，有效地使用上述数据分析方法与可视化技术，设计并实现了一套多视图关联的可视分析系统，提供了便捷的交互方式辅助用户分析。通过研发人员和交通警察共同对安徽省合肥市2018年的交通事故数据进行分析，将交通事故发生地划分9类并指出每类地点的空间语义特点，进一步分析出了事故高发区域的空间语义特性。结论 本文提出的交通事故数据空间语义增强方法和可视分析方法可以帮助用户揭示交通事故的空间语义模式，有助于深入分析和认识交通事故的成因，能为交通事故防治相关的城市建设工作提供建议。     

用户-兴趣点耦合关系的兴趣点推荐方法

在基于位置的社交网络(LBSNs)中,如何利用用户和兴趣点的属性(或特征)之间的耦合关系,为用户做出准确的兴趣点推荐是当前的研究热点.现有的矩阵分解推荐方法利用用户对兴趣点的评分进行推荐,但评级矩阵通常非常稀疏,并且没有考虑用户和兴趣点在各自属性方面的耦合关系.本文提出了一种基于深度神经网络的兴趣点推荐框架,首先采用K...     

Beyond Word2vec: An approach for urban functional region extraction and identification by combining Place2vec and POIs

The actual functions of a region may not reflect the intent of the original zoning scheme from planners. To identify the actual urban functional regions, numerous methods have been proposed with computational advancement. Specifically, remote sensing by image recognition, geodemographic classification, social sensing with big data and geo-text mining techniques have been widely applied. Points-of-interest (POIs) are one of the most common open-access data type used to extract information pertaining to functional zones. However, previous works have either lost sight or did not make full use of the spatial interactions that can be extracted from POIs due to model limitations in the context of geographical space. In this research, we introduced an approach that detects functional regions at the scale of a neighborhood area (NA) by combining POI data and a simplified Place2vec model, which is theorized from the first law of geography. First, the POI-based spatial context is constructed by using the nearest neighbor approach. Then, we can increase the number of training tuples (t_center, t_context) based on the weight derived from the distance between the POI t_center and POI t_context. Next, high-dimensional characteristic vectors of the POIs are extracted by using the skip-gram training framework. By summarizing the POI vectors at the NA level, we employ a K-means clustering model to cluster the functional regions. Compared with other probabilistic topic models (PTMs) and Word2vec, the Place2vec-based approach obtained the highest mean reciprocal rank value (MRR-S_WP=0.356, MRR-S_LC=0.401, MRR-S_JC=0.433, and MRR-S_Lin=0.421) in terms of similarity capturing performance and functional region identification accuracy (OA=0.7424). The research has important implications to urban planning and governance.     

融合社交关系和局部地理因素的兴趣点推荐

兴趣点（Point-Of-Interest,POI）推荐是基于位置社交网络（Location-Based Social Network,LBSN）中一项重要的个性化服务,可以帮助用户发现其感兴趣的[POI],提高信息服务质量。针对[POI]推荐中存在的数据稀疏性问题,提出一种融合社交关系和局部地理因素的[POI]推荐算法。根据社交关系中用户间的共同签到和距离关系度量用户相似性,并基于用户的协同过滤方法构建社交影响模型。为每个用户划分一个局部活动区域,通过对区域内[POIs]间的签到相关性分析,建立局部地理因素影响模型。基于加权矩阵分解挖掘用户自身偏好,并融合社交关系和局部地理因素进行[POI]推荐。实验表明,所提出的[POI]推荐算法相比其他方法具有更高的准确率和召回率,能够有效缓解数据稀疏性问题,提高推荐质量。