The problem of identifying thek-shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the$(i+1)^{th}$shortest path is generated based on the$i^{th}$shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifyingk-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions in an efficient and compact fashion, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

We study the problem of processing continuous$k$nearest neighbor (C$k$NN) queries over moving objects on road networks, which is an essential operation in a variety of applications. We are particularly concerned with scenarios where the object densities in different parts of the road network evolve over time as the objects move. Existing methods on C$k$NN query processing are ill-suited for such scenarios as they utilize index structures with fixed granularities and are thus unable to keep up with the evolving object densities. In this paper, we directly address this problem and propose an object density aware index structure called ODIN that is an elastic tree built on a hierarchical partitioning of the road network. It is equipped with the unique capability of dynamically folding/unfolding its nodes, thereby adapting to varying object densities. We further present the ODIN-KNN-Init and ODIN-KNN-Inc algorithms for the initial identification of the$k$NNs and the incremental update of query result as objects move. Thorough experiments on both real and synthetic datasets confirm the superiority of our proposal over several baseline methods.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes: user ID, location ID, and time-stamp and an implicit attribute: activity type (akin to "topic" in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. We evaluate HMRM on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

The prevalence of location-based services has generated a deluge of check-ins, enabling the task of human mobility understanding. Among the various types of information associated with the check-in venues, categories (e.g., Bar and Museum ) are vital to the task, as they often serve as excellent semantic characterization of the venues. Despite its significance and importance, a large portion of venues in the check-in services do not have even a single category label, such as up to 30% of venues in the Foursquare system lacking category labels. We, therefore, address the problem of semantic venue annotation, i.e., labeling the venue with a semantic category. Existing methods either fail to fully exploit the contextual information in the check-in sequences, or do not consider the semantic correlations across related categories. As such, we devise a Tree-guided Multi-task Embedding model (TME for short) to learn effective representations of venues and categories for the semantic annotation. TME jointly learns a common feature space by modeling multi-contexts of check-ins and utilizes the predefined category hierarchy to regularize the relatedness among categories. We evaluate TME over the task of semantic venue annotation on two check-in datasets. Experimental results show the superiority of TME over several state-of-the-art baselines.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes:user ID,location ID, andtime-stampand an implicit attribute:activity type(akin to “topic” in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. The merits of HMRM lie in that: (1) it models the latent activity types and learns trajectory attribute embeddings in an integrated manner, and (2) it connects the activity-related distributions and these attributes embeddings by adding a newly designed collaborative learning component, and makes them mutually exchanged to take the best of both worlds. We apply HMRM to both unsupervised and supervised tasks including two activity evaluation tasks and two embedding evaluation tasks, on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

Venue categories used in location-based social networks often exhibit a hierarchical structure, together with the category sequences derived from users’ check-ins. The two data modalities provide a wealth of information for us to capture the semantic relationships between those categories. To understand the venue semantics, existing methods usually embed venue categories into low-dimensional spaces by modeling the linear context (i.e., the positional neighbors of the given category) in check-in sequences. However, the hierarchical structure of venue categories, which inherently encodes the relationships between categories, is largely untapped. In this article, we propose a venue C ategory E mbedding M odel named Hier-CEM , which generates a latent representation for each venue category by embedding the Hier archical structure of categories and utilizing multiple types of context. Specifically, we investigate two kinds of hierarchical context based on any given venue category hierarchy and show how to model them together with the linear context collaboratively. We apply Hier-CEM to three tasks on two real check-in datasets collected from Foursquare. Experimental results show that Hier-CEM is better at capturing both semantic and sequential information inherent in venues than state-of-the-art embedding methods.

Neural attention, an emerging technique used to identify important inputs within neural networks, have become increasingly popular in the area of recommender systems. Not only allowing to better identify what defines users and items, attention-based recommender systems are further able to provide accompanying explanations. However, these representations usually capture only part of users' preferences and items' attributes, resulting in limited reasoning and accuracy. We therefore propose Dual Attention Recommender with Items and Attributes (DARIA), a novel approach able to combine two dependable neural attention mechanisms to better justify its suggestions. Utilizing the personalized history of users, DARIA identifies the most relevant past activities while considering the real-world features that contributed to the similarity. In addition, we adopt the novel approach of self-attention and introduce Self-Attention Recommender based on Attributes and History (SARAH). As a variation to DARIA, SARAH utilizes two self-attention components to describe users by their most characteristic past activities and items by their best depicting attributes. Various experiments establish the significant improvement of SARAH and DARIA over seven key baselines in diverse recommendation settings. By comparing our two proposed frameworks, we demonstrate the potential benefit of applying self-attention in different scenarios.

The problem of identifying the k -shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the (i+1)-th shortest path is generated based on the i-th shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifying k-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

In this paper we aim to solve a problem which many home-cooks encounter when searching for recipes online. Namely, finding recipes which best fit a handy set of ingredients while at the same time follow healthy eating guidelines. This task is especially difficult since the lion's share of online recipes have been shown to be unhealthy. In this paper we propose a novel algorithm which utilizes machine-learning techniques such as neural networks and matrix factorization in order to model the interactions between ingredients and their proportions within recipes for the purpose of offering suitable recommendations. The empirical results support the method's intuition and showcase its ability to retrieve healthier recipes.

Most of the traditional top- k algorithms are based on a single-server setting. They may be highly inefficient and/or cause huge communication overhead when applied to a distributed system environment. Therefore, the problem of top- k monitoring in distributed environments has been intensively investigated recently. This paper studies how to monitor the top- k data objects with the largest aggregate numeric values from distributed data streams within a fixed-size monitoring window W , while minimizing communication cost across the network. We propose a novel algorithm, which adaptively reallocates numeric values of data objects among distributed nodes by assigning revision factors when local constraints are violated and keeps the local top- k result at distributed nodes in line with the global top- k result. We also develop a framework that combines a distributed data stream monitoring architecture with a sliding window model. Based on this framework, extensive experiments are conducted on top of Apache Storm to verify the efficiency and scalability of the proposed algorithm.

This paper studies the problem of mining frequent co-occurrence patterns across multiple data streams, which has not been addressed by existing works. Co-occurrence pattern in this context refers to the case that the same group of objects appear consecutively in mul-tiple streams over a short time span, signaling tight correlations be-tween these objects. The need for mining such patterns in real-time arises in a variety of applications ranging from crime prevention to location-based services to event discovery in social media. Since the data streams are usually fast, continuous, and unbounded, existing methods on mining frequent patterns requiring more than one pass over the data cannot be directly applied. Therefore, we propose DIMine and CooMine, two algorithms to discover fre-quent co-occurrence patterns across multiple data streams. DIMine is an Apriori-style algorithm based on an inverted index, while CooMine uses an in-memory data structure called the Seg-tree to compactly index the data that are already seen but have not expired yet. CooMine employs a one-pass algorithm that uses the filter-and-refine strategy to obtain the co-occurrence patterns from the Seg-tree as updates to the streams arrive. Extensive experiments on two real datasets demonstrate the superiority of the proposed approaches over a baseline method, and show their respective ap-plicability in different senarios. 1.

Central to many applications involving moving objects is the task of processing k-nearest neighbor (k-NN) queries. Most of the existing approaches to this problem are designed for the centralized setting where query processing takes place on a single server; it is difficult, if not impossible, for them to scale to a distributed setting to handle the vast volume of data and concurrent queries that are increasingly common in those applications. To address this problem, we propose a suite of solutions that can support scalable distributed processing of k-NN queries. We first present a new index structure called Dynamic Strip Index (DSI), which can better adapt to different data distributions than exiting grid indexes. Moreover, it can be naturally distributed across the cluster, therefore lending itself well to distributed processing. We further propose a distributed k-NN search (DKNN) algorithm based on DSI. DKNN avoids having an uncertain number of potentially expensive iterations, and is thus more efficient and more predictable than existing approaches. DSI and DKNN are implemented on Apache S4, an open-source platform for distributed stream processing. We perform extensive experiments to study the characteristics of DSI and DKNN, and compare them with three baseline methods. Experimental results show that our proposal scales well and significantly outperforms the alternative methods.

The explosive growth of user-generated contents in social networking websites necessitates the recommendation functionality that can push to the user the content that he/she is most likely to be interested in. Such recommendation should happen in real-time as new contents become available, because "freshness" is an important consideration in people's content-consumption behavior. Representing users and contents as feature vectors in a high-dimensional space, we can essentially cast the problem of real-time recommendations as the problem of computing the list of k nearest neighbors of each user, which we call kNN join. Given the vast volume of contents and users, the biggest challenge is how to continuously update the kNN join results as new contents arrive. Existing methods for incremental kNN join on data streams suffer from the "curse of dimensionality" and high in-memory search cost. In this paper, we present a solution that first identifies the users whose kNN's might be affected by the newly arrived content, and then update their kNN's respectively. We propose a new index structure named HDR-tree in order to support the efficient search of affected users. HDR-tree performs dimensionality reduction through clustering and principle component analysis (PCA) in order to improve the search effectiveness. To further reduce response time, we propose a variant of HDR-tree, called HDR-tree, that supports more efficient but approximate solutions. The results of extensive experiments show that our methods significantly outperform baseline methods.

Existing work on collaborative filtering (CF) is often based on the overall ratings the items have received. However, in many cases, understanding how a user rates each aspect of an item may reveal more detailed information about her preferences and thus may lead to more effective CF. Prior work has studied extracting/quantizing sentiments on different aspects from the reviews, based on which the unknown overall ratings are inferred. However, in that work, all the aspects are treated equally; while in reality, different users tend to place emphases on difference aspects when reaching the overall rating. For example, users may give a high rating to a movie just for its plot despite its mediocre performances. This emphasis on aspects varies for different users and different items. In this paper, we propose a method that uses tensor factorization to automatically infer the weights of different aspects in forming the overall rating. The main idea is to learn, through constrained optimization, a compact representation of a weight tensor indexed by three dimensions for user, item, and aspect, respectively. Overall ratings can then be predicted using the obtained weights. Experiments on a movie dataset show that our method compares favorably with three baseline methods.

As highly centralized storage facilities are gaining popularity, duplicate detection becomes a critical problem. Traditional methods focus on reducing the storage space consumption; however, for network storage system with remote clients, the network overhead cannot be ignored, especially when the system is accessed over WAN. We propose a new duplicate detection method and implement a network file system prototype called DDSN based on this new method. It can reach the same performance in terms of storage space consumption as the state-of-the-art sliding blocking method. Meanwhile, our method overcomes its drawback that the whole file needs to be transmitted over the network, and therefore saves massive bandwidth for duplicate data. Experiments confirm the effectiveness of the proposed method.

Collaborative filtering (CF) aims to produce user specific recommendations based on other users' ratings of items. Most existing CF methods rely only on users' overall ratings of items, ignoring the variety of opinions users may have towards different aspects of the items. Using the movie domain as a case study, we propose a framework that is able to capture users' opinions on different aspects from the textual reviews, and use that information to improve the effectiveness of CF. This framework has two components, an opinion mining component and a rating inference component. The former extracts and summarizes the opinions on multiple aspects from the reviews, generating ratings on the various aspects. The latter component, on the other hand, infers the overall ratings of items based on the aspect ratings, which forms the basis for item recommendation. Our core contribution is in the proposal of a tensor factorization approach for the rating inference. Operating on the tensor composed of the overall and aspect ratings, this approach is able to capture the intrinsic relationships between users, items, and aspects, and provide accurate predictions on unknown ratings. Experiments on a movie dataset show that our proposal significantly improves the prediction accuracy compared with two baseline methods.

Posting reviews online has become an increasingly popular way for people to express opinions and sentiments toward the products bought or services received. Analyzing the large volume of online reviews available would produce useful actionable knowledge that could be of economic values to vendors and other interested parties. In this paper, we conduct a case study in the movie domain, and tackle the problem of mining reviews for predicting product sales performance. Our analysis shows that both the sentiments expressed in the reviews and the quality of the reviews have a significant impact on the future sales performance of products in question. For the sentiment factor, we propose Sentiment PLSA (S-PLSA), in which a review is considered as a document generated by a number of hidden sentiment factors, in order to capture the complex nature of sentiments. Training an S-PLSA model enables us to obtain a succinct summary of the sentiment information embedded in the reviews. Based on S-PLSFA, we propose ARSA, an Autoregressive Sentiment-Aware model for sales prediction. We then seek to further improve the accuracy of prediction by considering the quality factor, with a focus on predicting the quality of a review in the absence of user-supplied indicators, and present ARSQA, an Autoregressive Sentiment and Quality Aware model, to utilize sentiments and quality for predicting product sales performance. Extensive experiments conducted on a large movie data set confirm the effectiveness of the proposed approach.

With an increasingly amount of information in web forums, quick comprehension of threads in web forums has become a challenging research problem. To handle this issue, this paper investigates the task of Web Forum Thread Summarization (WFTS), aiming to give a brief statement of each thread that involving multiple dynamic topics. When applied to the task of WFTS, traditional summarization methods are cramped by topic dependencies, topic drifting and text sparseness. Consequently, we explore an unsupervised topic propagation model in this paper, the Post Propagation Model (PPM), to burst through these problems by simultaneously modeling the semantics and the reply relationship existing in each thread. Each post in PPM is considered as a mixture of topics, and a product of Dirichlet distributions in previous posts is employed to model each topic dependencies during the asynchronous discussion. Based on this model, the task of WFTS is accomplished by extracting most significant sentences in a thread. The experimental results on two different forum data sets show that WFTS based on the PPM outperforms several state-of-the-art summarization methods in terms of ROUGE metrics.

Keyword search over relational databases has recently received significant attention. Many solutions and prototypes have been developed. However, due to large memory consumption requirements and unpredictable running time, most of them cannot be applied directly to situations where memory is limited and quick response is required, such as when performing keyword search over databases in mobile devices as part of the OLAP funtionalities. In this paper, we attack the keyword search problem from a new perspective, and propose a cascading top-k keyword search algorithm, which generates supernodes in each step of search instead of computing the Steiner trees as done in many existing approaches. This new algorithm consumes less memory and significantly reduces the response time. Experiments show that the method can achieve high search efficiency compared with the state-of-the-art approaches.

Analyzing the large volume of online reviews would produce useful knowledge that could be of economic values to vendors and other interested parties. In particular, the sentiments expressed in the online reviews have been shown to be strongly correlated with the sales performance of products. In this paper, we present an adaptive sentiment analysis model called S-PLSA+, which aims to capture the hidden sentiment factors in the reviews with the capability to be incrementally updated as more data become available. We show how S-PLSA+ can be applied to sales performance prediction using an ARSA model developed in previous literature. A case study is conducted in the movie domain, and results from preliminary experiments confirm the effectiveness of the proposed model.

Online reviews, which are getting increasingly prevalent with the rapid growth of Web 2.0, have been shown to be second only to "word-of-mouth" in terms of influencing purchase decisions. It is therefore imperative to analyze them and distill useful knowledge that could be of economic values to vendors and other interested parties. Previous studies have confirmed that the sentiments expressed in the online reviews are strongly correlated with the sales performance of products. In particular, a model called ARSA has been proposed for predicting sales performance using a model called S-PLSA. In this paper, we build upon that work, and present an adaptive sentiment analysis model called S-PLSA+, which not only can capture the hidden sentiment factors in the reviews, but has the capability to be incrementally updated as more data become available. We show how the proposed S-PLSA+model can be applied to sales performance prediction using the ARSA model. A case study is conducted in the movie domain, and results from preliminary experiments confirm the effectiveness of the proposed model.

Writing and publishing reviews online has become an increasingly popular way for people to express opinions and sentiments. Analyzing the large volume of online reviews available can produce useful knowledge that are of interest to vendors and other parties. Prior studies in the literature have shown that online reviews have a significant correlation with the sales of products, and therefore mining the reviews could help predict the sales performance of relevant products. However, those studies fail to consider one important factor that may significantly affect the accuracy of the prediction, i.e., the quality of the reviews. In this paper, we propose a regression model that explicitly takes into account the quality factor, and discusses how this quality information can be predicted when it is not readily available. Experimental results on a movie review dataset confirm the effectiveness of the proposed model.

Online reviews provide a valuable resource for potential customers to make purchase decisions. However, the sheer volume of available reviews as well as the large variations in the review quality present a big impediment to the effective use of the reviews, as the most helpful reviews may be buried in the large amount of low quality reviews. The goal of this paper is to develop models and algorithms for predicting the helpfulness of reviews, which provides the basis for discovering the most helpful reviews for given products. We first show that the helpfulness of a review depends on three important factors: the reviewerpsilas expertise, the writing style of the review, and the timeliness of the review. Based on the analysis of those factors, we present a nonlinear regression model for helpfulness prediction. Our empirical study on the IMDB movie reviews dataset demonstrates that the proposed approach is highly effective.

With the flourish of the Internet, online review mining has attracted a lot of attention from the research community. However, compared to various well-studied sentiment analysis and opinion summarization problems, less effort has been made to analyze the quality of online reviews. The objective of this paper is to fill in this gap by automatically evaluating the "helpfulness" of reviews and consequently developing novel models to identify the most helpful reviews for a particular product. In particular, based on a thorough analysis of various factors that may affect the review quality, we propose HelpMeter, a nonlinear regression model for helpfulness prediction. Some preliminary experiments were conducted on a movie review data set, and the performance results confirm the superiority of the proposed method.

In many text retrieval tasks, it is highly desirable to obtain a "similarity profile" of the document collection for a given query. We propose sampling-based techniques to address this need, using calibration techniques to improve the accuracy. Experimental results confirm the effectiveness of the proposed approaches.

Due to its high popularity, Weblogs (or blogs in short) present a wealth of information that can be very helpful in assessing the general public's sentiments and opinions. In this paper, we study the problem of mining sentiment information from blogs and investigate ways to use such information for predicting product sales performance. Based on an analysis of the complex nature of sentiments, we propose Sentiment PLSA (S-PLSA), in which a blog entry is viewed as a document generated by a number of hidden sentiment factors. Training an S-PLSA model on the blog data enables us to obtain a succinct summary of the sentiment information embedded in the blogs. We then present ARSA, an autoregressive sentiment-aware model, to utilize the sentiment information captured by S-PLSA for predicting product sales performance. Extensive experiments were conducted on a movie data set. We compare ARSA with alternative models that do not take into account the sentiment information, as well as a model with a different feature selection method. Experiments confirm the effectiveness and superiority of the proposed approach.

Abstract With more and more information available on the Internet, the task of making personalized recommendations to assist the user's navigation has become increasingly important. Considering there might be millions of users with different backgrounds accessing a Web site everyday, it is infeasible to build a separate recommendation system for each user. To address this problem, clustering techniques can first be employed to discover user groups. Then, user navigation patterns for each group can be discovered, to allow the adaptation of a Web site to the interest of each individual group. In this paper, we propose to model user access sequences as stochastic processes, and a mixture of Markov models based approach is taken to cluster users and to capture the sequential relationships inherent in user access histories. Several important issues that arise in constructing the Markov models are also addressed. The first issue lies in the complexity of the mixture of Markov models. To improve the efficiency of building/maintaining the mixture of Markov models, we develop a lightweight adapt‐ive algorithm to update the model parameters without recomputing model parameters from scratch. The second issue concerns the proper selection of training data for building the mixture of Markov models. We investigate two different training data selection strategies and perform extensive experiments to compare their effectiveness on a real dataset that is generated by a Web‐based knowledge management system, Livelink.

In this paper, we investigate the use of data mining, in particular the text classification and co-training techniques, to identify more relevant passages based on a small set of labeled passages obtained from the blind feedback of a retrieval system. The data mining results are used to expand query terms and to re-estimate some of the parameters used in a probabilistic weighting function. We evaluate the data mining based feedback method on the TREC HARD data set. The results show that data mining can be successfully applied to improve the text retrieval performance. We report our experimental findings in detail.

The problem of modeling and predicting a Web surfer's browsing patterns has gained increasing attention in recent years. In this paper we present our experience in clustering Web surfers using a mixture of Markov models with a real application of Livelink log data. We propose different techniques to improve the clustering performance, and evaluate the techniques through experiments.