Discovering popular routes from trajectories Zaiben Chen; Heng Tao Shen; Xiaofang Zhou
2011 IEEE 27th International Conference on Data Engineering,
2011-April
Conference Proceeding
The booming industry of location-based services has accumulated a huge collection of users' location trajectories of driving, cycling, hiking, etc. In this work, we investigate the problem of ...discovering the Most Popular Route (MPR) between two locations by observing the traveling behaviors of many previous users. This new query is beneficial to travelers who are asking directions or planning a trip in an unfamiliar city/area, as historical traveling experiences can reveal how people usually choose routes between locations. To achieve this goal, we firstly develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories, for indicating all the possible movements between locations. After that, the Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node in the network, which is subsequently used as the popularity indicator in the search phase. Finally, we propose a Maximum Probability Product algorithm to discover the MPR from a transfer network based on the popularity indicators in a breadth-first manner, and we illustrate the results and performance of the algorithm by extensive experiments.
To explore the benefit of advertising instant and location-aware commercials that can not be effectively promoted by traditional medium like TV program and Internet, we propose in this paper a ...solution for disseminating instant advertisements to users within the area of interest through a mobile peer-to-peer network. This is a new application scenario, and we devise an opportunistic gossiping model for advertisement propagation with spatial and temporal constraints. As bandwidth and computational resources are limited in a wireless environment, two optimization mechanisms utilizing distance and velocity information are provided for reducing redundant advertising messages. User interest is also considered as another critical factor in adjusting the advertisement propagation model, and we adopt the FM algorithm to achieve efficient counting of distinct users' interests. Finally, we study the performance of our solution through simulation in NS-2. Compared with the naive flooding method, our approach achieves high quality delivery rate while reducing the number of messages by nearly an order of magnitude.
Searching trajectories by locations Chen, Zaiben; Shen, Heng Tao; Zhou, Xiaofang ...
Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,
06/2010
Conference Proceeding
Trajectory search has long been an attractive and challenging topic which blooms various interesting applications in spatial-temporal databases. In this work, we study a new problem of searching ...trajectories by locations, in which context the query is only a small set of locations with or without an order specified, while the target is to find the k Best-Connected Trajectories (k-BCT) from a database such that the k-BCT best connect the designated locations geographically. Different from the conventional trajectory search that looks for similar trajectories w.r.t. shape or other criteria by using a sample query trajectory, we focus on the goodness of connection provided by a trajectory to the specified query locations. This new query can benefit users in many novel applications such as trip planning.
In our work, we firstly define a new similarity function for measuring how well a trajectory connects the query locations, with both spatial distance and order constraint being considered. Upon the observation that the number of query locations is normally small (e.g. 10 or less) since it is impractical for a user to input too many locations, we analyze the feasibility of using a general-purpose spatial index to achieve efficient k-BCT search, based on a simple Incremental k-NN based Algorithm (IKNN). The IKNN effectively prunes and refines trajectories by using the devised lower bound and upper bound of similarity. Our contributions mainly lie in adapting the best-first and depth-first k-NN algorithms to the basic IKNN properly, and more importantly ensuring the efficiency in both search effort and memory usage. An in-depth study on the adaption and its efficiency is provided. Further optimization is also presented to accelerate the IKNN algorithm. Finally, we verify the efficiency of the algorithm by extensive experiments.
Monitoring path nearest neighbor in road networks Chen, Zaiben; Shen, Heng Tao; Zhou, Xiaofang ...
Proceedings of the 2009 ACM SIGMOD International Conference on Management of data,
06/2009
Conference Proceeding
This paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN ...with respect to the shortest path connecting the destination and the user's current location, and thus provides a list of nearest candidates for reference by considering the whole coming journey. We name this query the k-Path Nearest Neighbor query (k-PNN). As the user is moving and may not always follow the shortest path, the query path keeps changing. The challenge of monitoring the k-PNN for an arbitrarily moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We propose a three-phase Best-first Network Expansion (BNE) algorithm for monitoring the k-PNN and the corresponding shortest path. In the searching phase, the BNE finds the shortest path to the destination, during which a candidate set that guarantees to include the k-PNN is generated at the same time. Then in the verification phase, a heuristic algorithm runs for examining candidates' exact distances to the query path, and it achieves significant reduction in the number of visited nodes. The monitoring phase deals with computing update locations as well as refreshing the k-PNN in different user movements. Since determining the network distance is a costly process, an expansion tree and the candidate set are carefully maintained by the BNE algorithm, which can provide efficient update on the shortest path and the k-PNN results. Finally, we conduct extensive experiments on real road networks and show that our methods achieve satisfactory performance.
The concept of Peer-to-Peer (P2P) has been introduced into mobile networks, which has led to the emergence of mobile P2P networks, and originated potential applications in many fields. However,mobile ...P2P networks are subject to the limitations of transmission range, and highly dynamic and unpredictable network topology, giving rise to many new challenges for efficient information retrieval. In this paper, we propose an automatic and economical hybrid information retrieval approach based on cooperative cache. In this method, the region covered by a mobile P2P network is partitioned into subregions, each of which is identified by a unique ID and known to all peers. All the subregions then constitute a mobile Kademlia (MKad) network. The proposed hybrid retrieval approach aims to utilize the floodingbased and Distributed Hash Table (DHT)-based schemes in MKad for indexing and searching according to the designed utility functions. To further facilitate information retrieval, we present an effective cache update method by considering all relevant factors. At the same time, the combination of two different methods for cache update is also introduced. One of them is pull based on time stamp including two different pulls: an on-demand pull and a periodical pull, and the other is a push strategy using update records. Furthermore, we provide detailed mathematical analysis on the cache hit ratio of our approach. Simulation experiments in NS-2 showed that the proposed approach is more accurate and efficient than the existing methods.
Mobile P2P networks have potential applications in many fields, making them a focus of current research. However, mobile P2P networks are subject to the limitations of transmission range, wireless ...bandwidth, and highly dynamic network topology, giving rise to many new challenges for efficient search. In this paper, we propose a hybrid search approach, which is automatic and economical in mobile P2P networks. The region covered by a mobile P2P network is partitioned into subregions, each of which can be identified by a unique ID and known to all peers. All the subregions then construct a mobile Kademlia (MKad) network. The proposed hybrid retrieval approach aims to utilize flooding-based and DHT-based schemes in MKad for indexing and searching according to designed utility functions. Our experiments show that the proposed approach is more accurate and efficient than existing methods.
Incentives are often used to promote cooperation in a population of competing agents. Furthermore, it is a common method to combine both punishment and reward. However, how to optimally allocate an ...amount of incentive budget as reward and punishment to enhance cooperation in structured populations is still a challenging task. To address this problem, we here consider evolutionary public goods games on regular networks and assume that a fixed budget of incentives is dynamically allocated to reward cooperators or to punish defectors in a group of players, depending on the actual cooperation level in the population. By means of the pair approximation approach, we derive the dynamical equation for depicting the evolutionary dynamics of cooperation. We then formulate two optimal incentive allocation problems by minimizing the payoff difference between defectors and cooperators and maximizing the gradient of selection, respectively. We theoretically derive the optimal incentive allocation protocols for the two objective functions we considered. We find that the obtained protocols both depend sensitively on the efficiency ratio of reward to punishment. In addition, we provide numerical calculations to verify our theoretical results.
PDF
