Novel Class Discovery (NCD) involves identifying new categories within unlabeled data by utilizing knowledge acquired from previously established categories. However, existing NCD methods often struggle to maintain a balance between the performance of old and new categories. Discovering unlabeled new categories in a class-incremental way is more practical but also more challenging, as it is frequently hindered by either catastrophic forgetting of old categories or an inability to learn new ones. Furthermore, the implementation of NCD on continuously scalable graph-structured data remains an under-explored area. In response to these challenges, we introduce for the first time a more practical NCD scenario for node classification (i.e., NC-NCD), and propose a novel self-training framework with prototype replay and distillation called SWORD, adopted to our NC-NCD setting. Our approach enables the model to cluster unlabeled new category nodes after learning labeled nodes while preserving performance on old categories without reliance on old category nodes. SWORD achieves this by employing a self-training strategy to learn new categories and preventing the forgetting of old categories through the joint use of feature prototypes and knowledge distillation. Extensive experiments on four common benchmarks demonstrate the superiority of SWORD over other state-of-the-art methods.

Public opinion plays a pivotal role in politics, influencing political leaders' decisions, shaping election outcomes, and impacting policy-making processes. In today's digital age, the abundance of political discourse available on social media platforms has become an invaluable resource for analyzing public opinion. This paper focuses on the task of detecting political stances in the context of the 2020 US presidential election. To facilitate this research, we curate a substantial dataset sourced from Twitter, annotated using hashtags as indicators of political polarity. In our approach, we construct a bipartite graph that explicitly models user-tweet interactions, which provides a comprehensive contextual understanding of the election. To effectively leverage the wealth of user behavioral information encoded in this graph, we adopt graph convolution and introduce a novel skip aggregation mechanism. This mechanism enables tweet nodes to aggregate information from their second-order neighbors, which are also tweet nodes due to the graph's bipartite nature. Our experimental results demonstrate that our proposed model outperforms a range of competitive baseline models. Furthermore, our in-depth analyses highlight the importance of user behavioral information and the effectiveness of skip aggregation.

Given the development and abundance of social media, studying the stance of social media users is a challenging and pressing issue. Social media users express their stance by posting tweets and retweeting. Therefore, the homogeneous relationship between users and the heterogeneous relationship between users and tweets are relevant for the stance detection task. Recently, graph neural networks (GNNs) have developed rapidly and have been applied to social media research. In this paper, we crawl a large-scale dataset of the 2020 US presidential election and automatically label all users by manually tagged hashtags. Subsequently, we propose a bipartite graph neural network model, DoubleH, which aims to better utilize homogeneous and heterogeneous information in user stance detection tasks. Specifically, we first construct a bipartite graph based on posting and retweeting relations for two kinds of nodes, including users and tweets. We then iteratively update the node's representation by extracting and separately processing heterogeneous and homogeneous information in the node's neighbors. Finally, the representations of user nodes are used for user stance classification. Experimental results show that DoubleH outperforms the state-of-the-art methods on popular benchmarks. Further analysis illustrates the model's utilization of information and demonstrates stability and efficiency at different numbers of layers.

Spatiotemporal applications such as taxi order dispatching and warehouse task scheduling depend critically on the algorithms for operational efficiency. However, the inherent dynamic nature of these applications presents challenges in algorithm design. The growth of mobility services has facilitated the collection of extensive spatiotemporal data, which in turn prompted algorithm designers to use data-driven methods. Reinforcement learning (RL), recognized for its strong performance and suitability for spatiotemporal contexts, has garnered considerable research interest. Despite their potential, RL algorithms necessitate the use of a simulator for both training and validation purposes. However, no specific simulation system has been developed for spatiotemporal algorithm design. This vacancy hinders the progress of spatiotemporal algorithm designers. In this demo, we build a system called Data-driven Spatiotemporal Simulator (DSS), hoping to bring convenience for spatiotemporal algorithm designers. DSS is adept at handling problems related to taxi order dispatching and warehouse task scheduling and possesses the versatility to be expanded for other user-defined scenarios. The system includes visualization modules that offer insightful panels, alongside developer tools designed to streamline the development process. This enables designers to efficiently craft, evaluate, and refine their algorithms, potentially accelerating innovation in spatiotemporal application development.

Shared mobility leverages under-utilized vehicles to offer on-demand transport services by sharing vehicles among users. It strives to match supply with demand via a series of data-intensive operations such as supply prediction and task assignment. However, its full potential is often compromised in practice as most shared mobility platforms operate in isolation, leading to sub-optimal resource utilization. In this demonstration, we advocate a federated approach to shared mobility, which enhances its effectiveness by enabling optimizations across platforms while retaining their autonomy. We develop privacy-preserving operators and incentive mechanisms dedicated to supply prediction and task assignment in shared mobility and implement generic interfaces that support diverse prediction and assignment algorithms. We showcase the shared mobility system with real-world ride-hailing applications.

Forecasting financial data plays a crucial role in financial market. Relying solely on prices or price trends as prediction targets often leads to a vast of invalid transactions. As a result, researchers have increasingly turned their attention to turning points as the prediction target. Surprisingly, existing methods have largely overlooked the role of technical charts, despite turning points being closely related to the technical charts. Recently, several researchers have attempted to utilize chart information via converting price sequences into images for turning point forecasting, but robustness and convergence problems arise. To address these challenges and enhance the turning point predictions, this article introduces a new method known as MPCNet. Specifically, we first transform the price series into a graph structure using chart similarity to robustly extract valuable information from technical charts. Additionally, we introduce the multipersistence topology tool to accurately predict stock turning points and provide convergence guarantee. Experimental results demonstrate the significant superiority of our proposed model over existing methods. Furthermore, based on additional performance evaluations using real stock data, MPCNet consistently achieves the highest average return during the transaction backtesting period. Meanwhile, we provide empirical validation of robustness and theoretical analysis to confirm its convergence, establishing it as a superior tool for financial forecasting.

Multi-robot systems are deployed in modern warehouses to reduce operational cost. The robots are tasked to deliver items stored on racks to pickers for fast distribution. A central algorithmic problem is collision-aware route planning, which aims to plan shortest routes for robots to deliver racks while avoiding collision with racks, pickers, and other robots. Prior solutions are inefficient in real-world warehouses, where route planning requests emerge online and at large scale. In this paper, we identify collision judgement in grid-based warehouse representation as the primary efficiency bottleneck, and propose a novel Strip-based Route Planning framework (SRP). Specifically, we exploit the regularity in warehouse layouts, and aggregate grids into strips. The strip-based representation also converts collisions of 3-dimensional (2-dimensional space and 1-dimensional time) routes into 2-dimensional (1-dimensional space and 1-dimensional time) segment intersections, which can be fast checked via computational geometry. We further accelerate the collision judgement via indexing on segments within strips. Theoretical analysis shows a reduction of time complexity from square to linear-logarithmic. Experimental results on datasets collected from real-world robotized warehouses show that our SRP is up to 227× faster than existing methods.

Skyline is a primitive operation in multi-objective decision applications and there is a growing demand to support such operations over a data federation, where the entire dataset is separately held by multiple data providers (a.k.a., silos). Data federations notably increase the amount of data available for data-intensive applications such as commercial recommendation and location based services. Yet they also challenge the conventional implementation of skyline queries because the raw data cannot be shared within the federation and the secure computation cross silos can be two or three orders of magnitude slower than plaintext computation. These constraints render existing solutions inefficient on data federation. In this work, we propose a novel local dominance based framework for efficient skyline queries over a vertical data federation. We decompose the skyline query into plaintext local dominance computations and secure result aggregations, which can perform as many computations in plaintext as possible without compromising security. We further propose a dedicate private set intersection based algorithm to accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with general-purpose secure multi-party computation techniques, our solutions reduce the time cost by up to 35.4× and communication cost by two orders of magnitude respectively.

kNN is a fundamental query in various location based services such as POI recommendation and ride planning. There is an increasing demand to scale such services by querying over a data federation, where the entire dataset is distributedly held by multiple data providers (a.k.a., silos), and each silo keeps its data partition private. However, it is challenging to provide secure kNN queries over a large-scale data federation. Prior secure kNN queries can be are highly inefficient if performed cross silos because they involve excessive secure distance operations, which can be two or three orders of magnitude slower than the corresponding plaintext operations. In this work, we propose a novel threshold based framework for efficient kNN queries over a spatial data federation. The key idea is to rewrite excessive secure distance computations as light-weight secure operations. We further propose an adaptive threshold algorithm to reduce the secure communication rounds and accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with the state-of-the-art secure kNN querying methods, our solutions reduce the time cost by up to 104.1 times and communication cost by three orders of magnitude.

Robotized warehouses are deployed to automatically distribute millions of items brought by the massive logistic orders from e-commerce. A key to automated item distribution is to plan paths for robots, also known as task planning, where each task is to deliver racks with items to pickers for processing and then return the rack back. Prior solutions are unfit for large-scale robotized warehouses due to the inflexibility to time-varying item arrivals and the low efficiency for high throughput. In this paper, we propose a new task planning problem called TPRW, which aims to minimize the end-to-end makespan that incorporates the entire item distribution pipeline, known as a fulfilment cycle. Direct extensions from state-of-the-art path finding methods are ineffective to solve the TPRW problem because they fail to adapt to the bottleneck variations of fulfillment cycles. In response, we propose Efficient Adaptive Task Planning, a framework for large-scale robotized warehouses with time-varying item arrivals. It adaptively selects racks to fulfill at each timestamp via rein-forcement learning, accounting for the time-varying bottleneck of the fulfillment cycles. Then it finds paths for robots to transport the selected racks. The framework adopts a series of efficient optimizations on both time and memory to handle large-scale item throughput. Evaluations on both synthesized and real data show an improvement of 37.1% in effectiveness and 75.5% in efficiency over the state-of-the-arts.

The increasing concerns on data security limit the sharing of data distributedly stored at multiple data owners and impede the scale of spatial queries over big urban data. In response, data federation systems have emerged to perform secure queries across multiple data owners leveraging secure multi-party computation. However, existing systems are designed for relational data. They are highly inefficient on spatial queries and limited in usability. In this demonstration, we introduce Hu-Fu, the first data federation system for secure spatial queries with high efficiency and usability. Hu-Fu is designed from the perspectives of the query user and the data owner for high usability and decomposes a spatial query into as many plaintext operators and as few secure operators as possible for high efficiency. We demonstrate the deployment and usage of Hu-Fu via cross-company taxi-calling, a popular smart city application.

Data isolation has become an obstacle to scale up query processing over big data, since sharing raw data among data owners is often prohibitive due to security concerns. A promising solution is to perform secure queries over a federation of multiple data owners leveraging secure multi-party computation (SMC) techniques, as evidenced by recent federation work over relational data. However, existing solutions are highly inefficient on spatial queries due to excessive secure distance operations for query processing and their usage of general-purpose SMC libraries for secure operation implementation. In this paper, we propose Hu-Fu, the first system for efficient and secure spatial query processing on a data federation. The idea is to decompose the secure processing of a spatial query into as many plaintext operations and as few secure operations as possible, where fewer secure operators are involved and all secure operators are implemented dedicatedly. As a working system, Hu-Fu supports not only query input in native SQL, but also heterogeneous spatial databases ( e.g. , PostGIS, Simba, GeoMesa, and SpatialHadoop) at the backend. Extensive experiments show that Hu-Fu usually outperforms the state-of-the-arts in running time and communication cost while guaranteeing security.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the “insertion operator”. Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum/sum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of$O(n^3)$, where$n$is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of$O(n^2)$. We further improve the time efficiency of the insertion operator to$O(n)$harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

The problem of session-aware recommendation aims to predict users’ next click based on their current session and historical sessions. Existing session-aware recommendation methods have defects in capturing complex item transition relationships. Other than that, most of them fail to explicitly distinguish the effects of different historical sessions on the current session. To this end, we propose a novel method, named Personalized Graph Neural Networks with Attention Mechanism (A-PGNN) for brevity. A-PGNN mainly consists of two components: one is Personalized Graph Neural Network (PGNN), which is used to extract the personalized structural information in each user behavior graph, compared with the traditional Graph Neural Network (GNN) model, which considers the role of the user when the node embedding is updated. The other is Dot-Product Attention mechanism, which draws on the Transformer net to explicitly model the effect of historical sessions on the current session. Extensive experiments conducted on two real-world data sets show that A-PGNN evidently outperforms the state-of-the-art personalized session-aware recommendation methods.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery, and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e., a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In addition, previous route planning solutions fail to exploit the appearance patterns of future requests hidden in historical data for optimization. In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We propose two insertion-based frameworks to solve the URPSM problem. The first is built upon the plain-insertion widely used in prior studies, which processes online requests only, whereas the second relies on a new insertion operator called prophet-insertion that handles both online and predicted requests. Novel dynamic programming algorithms are designed to accelerate both insertions to only linear time. Theoretical analysis shows that no online algorithm can have a constant competitive ratio for the URPSM problem under the competitive analysis model, yet our prophet-insertion-based framework can achieve a constant optimality ratio under the instance-optimality model. Extensive experimental results on real datasets show that our insertion-based solutions outperform the state-of-the-art algorithms in both effectiveness and efficiency by a large margin (e.g., up to 30 \( \times \) more effective in the objective and up to 20 \( \times \) faster).

Traditional learning-to-rank (LTR) models are usually trained in a centralized approach based upon a large amount of data. However, with the increasing awareness of data privacy, it is harder to collect data from multiple owners as before, and the resultant data isolation problem makes the performance of learned LTR models severely compromised. Inspired by the recent progress in federated learning, we propose a novel framework named Cross-Silo Federated Learning-to-Rank (CS-F-LTR), where the efficiency issue becomes the major bottleneck. To deal with the challenge, we first devise a privacy-preserving cross-party term frequency querying scheme based on sketching algorithms and differential privacy. To further improve the overall efficiency, we propose a new structure named reverse top-K sketch (RTK-Sketch) which significantly accelerates the feature generation process while holding theoretical guarantees on accuracy loss. Extensive experiments conducted on public datasets verify the effectiveness and efficiency of the proposed approach.

Spatial crowdsourcing has stimulated various new applications such as taxi calling and food delivery. A key enabler for these spatial crowdsourcing based applications is to plan routes for crowd workers to execute tasks given diverse requirements of workers and the spatial crowdsourcing platform. Despite extensive studies on task planning in spatial crowdsourcing, few have accounted for the location privacy of tasks, which may be misused by an untrustworthy platform. In this paper, we explore efficient task planning for workers while protecting the locations of tasks. Specifically, we define the Privacy-Preserving Task Planning (PPTP) problem, which aims at both total revenue maximization of the platform and differential privacy of task locations. We first apply the Laplacian mechanism to protect location privacy, and analyze its impact on the total revenue. Then we propose an effective and efficient task planning algorithm for the PPTP problem. Extensive experiments on both synthetic and real datasets validate the advantages of our algorithm in terms of total revenue and time cost.

With spatial crowdsourcing applications such as Uber and Waze deeply penetrated into everyday life, there is a growing concern to protect user privacy in spatial crowdsourcing. Particularly, locations of workers and tasks should be properly processed via certain privacy mechanism before reporting to the untrusted spatial crowdsourcing server for task assignment. Privacy mechanisms typically permute the location information, which tends to make task assignment ineffective. Prior studies only provide guarantees on privacy protection without assuring the effectiveness of task assignment. In this paper, we investigate privacy protection for online task assignment with the objective of minimizing the total distance, an important task assignment formulation in spatial crowdsourcing. We design a novel privacy mechanism based on Hierarchically Well-Separated Trees (HSTs). We prove that the mechanism is ε-Geo-Indistinguishable and show that there is a task assignment algorithm with a competitive ratio of O(ε1/4log N log2k), where ε is the privacy budget, N is the number of predefined points on the HST, and k is the matching size. Extensive experiments on synthetic and real datasets show that online task assignment under our privacy mechanism is notably more effective in terms of total distance than under prior differentially private mechanisms.

There is a growing trend to deploy deep neural networks at the edge for high-accuracy, real-time data mining and user interaction. Applications such as speech recognition and language understanding often apply a deep neural network to encode an input sequence and then use a decoder to generate the output sequence. A promising technique to accelerate these applications on resource-constrained devices is network pruning, which compresses the size of the deep neural network without severe drop in inference accuracy. However, we observe that although existing network pruning algorithms prove effective to speed up the prior deep neural network, they lead to dramatic slowdown of the subsequent decoding and may not always reduce the overall latency of the entire application. To rectify such drawbacks, we propose entropy-based pruning, a new regularizer that can be seamlessly integrated into existing network pruning algorithms. Our key theoretical insight is that reducing the information entropy of the deep neural network outputs decreases the upper bound of the subsequent decoding search space. We validate our solution with two state-of-the-art network pruning algorithms on two model architectures. Experimental results show that compared with existing network pruning algorithms, our entropy-based pruning method notably suppresses and even eliminates the increase of decoding time, and achieves shorter overall latency with only negligible extra accuracy loss in the applications.

Online bipartite graph matching is attracting growing research attention due to the development of dynamic task assignment in sharing economy applications, where tasks need be assigned dynamically to workers. Past studies lack practicability in terms of both problem formulation and solution framework. On the one hand, some problem settings in prior online bipartite graph matching research are impractical for real-world applications. On the other hand, existing solutions to online bipartite graph matching are inefficient due to the unnecessary real-time decision making. In this paper, we propose the dynamic bipartite graph matching (DBGM) problem to be better aligned with real-world applications and devise a novel adaptive batch-based solution framework with a constant competitive ratio. As an effective and efficient implementation of the solution framework, we design a reinforcement learning based algorithm, called Restricted Q-learning (RQL), which makes near-optimal decisions on batch splitting. Extensive experimental results on both real and synthetic datasets show that our methods outperform the state-of-the-arts in terms of both effectiveness and efficiency.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the "insertion operator". Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of O(n^3), where n is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of O(n^2). We further improve the time efficiency of the insertion operator to O(n) harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e. , a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the URPSM problem and its variants. In response, we devise an effective and efficient solution to address the URPSM problem approximately. We design a novel dynamic programming (DP) algorithm to accelerate the insertion operation from cubic or quadric time in previous work to only linear time. On basis of the DP algorithm, we propose a greedy based solution to the URPSM problem. Experimental results on real datasets show that our solution outperforms the state-of-the-arts by 1.2 to 12.8 times in effectiveness, and also runs 2.6 to 20.7 times faster.

Aspect-based opinion mining is finding elaborate opinions towards a subject such as a product or an event. With explosive growth of opinionated texts on the Web, mining aspect-level opinions has become a promising means for online public opinion analysis. In particular, the boom of various types of online media provides diverse yet complementary information, bringing unprecedented opportunities for cross media aspect-opinion mining. Along this line, we propose CAMEL, a novel topic model for complementary aspect-based opinion mining across asymmetric collections. CAMEL gains information complementarity by modeling both common and specific aspects across collections, while keeping all the corresponding opinions for contrastive study. An auto-labeling scheme called AME is also proposed to help discriminate between aspect and opinion words without elaborative human labeling, which is further enhanced by adding word embedding-based similarity as a new feature. Moreover, CAMEL-DP, a nonparametric alternative to CAMEL is also proposed based on coupled Dirichlet Processes. Extensive experiments on real-world multi-collection reviews data demonstrate the superiority of our methods to competitive baselines. This is particularly true when the information shared by different collections becomes seriously fragmented. Finally, a case study on the public event “2014 Shanghai Stampede” demonstrates the practical value of CAMEL for real-world applications.

The prevalence of mobile Internet techniques and Online-To-Offline (O2O) business models has led the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC is to assign real-time tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, or assume the static offline scenarios, where the spatio-temporal information of all the tasks and workers is known in advance. Recently, some new emerging O2O applications incur new challenges: SC platforms need to assign three types of objects, tasks, workers and workplaces, and support dynamic real-time online scenarios, where the existing solutions cannot handle. In this paper, based on the aforementioned challenges, we formally define a novel dynamic online task assignment problem, called the trichromatic online matching in real-time spatial crowdsourcing (TOM) problem, which is proven to be NP-hard. Thus, we first devise an efficient greedy online algorithm. However, the greedy algorithm can be trapped into local optimal solutions easily. We then present a threshold-based randomized algorithm that not only guarantees a tighter competitive ratio but also includes an adaptive optimization technique, which can quickly learn the optimal threshold for the randomized algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

With the rapid development of mobile internet and online to offline marketing model, various spatial crowdsourcing platforms, such as Gigwalk and Gmission, are getting popular. Most existing studies assume that spatial crowdsourced tasks are simple and trivial. However, many real crowdsourced tasks are complex and need to be collaboratively finished by a team of crowd workers with different skills. Therefore, an important issue of spatial crowdsourcing platforms is to recommend some suitable teams of crowd workers to satisfy the requirements of skills in a task. In this paper, to address the issue, we first propose a more practical problem, called Top-k team recommendation in spatial crowdsourcing (Top k TR) problem. We prove that the Top k TR problem is NP-hard and designs a two-level-based framework, which includes an approximation algorithm with provable approximation ratio and an exact algorithm with pruning techniques to address it. In addition, we study a variant of the Top k TR problem, called Top k TRL, where a team leader is appointed among each recommended team of crowd workers in order to coordinate different crowd workers conveniently, and the aforementioned framework can be extended to address this variant. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem Flexible Two-sided Online task Assignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, Prediction-oriented Online task Assignment in Real-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.

Recent years have witnessed the unprecedented growth of online social media, which empower short texts as the prevalent format for information of Internet. Given the nature of sparsity, however, short text topic modeling remains a critical yet much-watched challenge in both academy and industry. Rich research efforts have been put on building different types of probabilistic topic models for short texts, among which the self aggregation methods without using auxiliary information become an emerging solution for providing informative cross-text word co-occurrences. However, models along this line are still rarely seen, and the representative one Self-Aggregation Topic Model (SATM) is prone to overfitting and computationally expensive. In light of this, in this paper, we propose a novel probabilistic model called Pseudo-document-based Topic Model (PTM) for short text topic modeling. PTM introduces the concept of pseudo document to implicitly aggregate short texts against data sparsity. By modeling the topic distributions of latent pseudo documents rather than short texts, PTM is expected to gain excellent performance in both accuracy and efficiency. A Sparsity-enhanced PTM (SPTM for short) is also proposed by applying Spike and Slab prior, with the purpose of eliminating undesired correlations between pseudo documents and latent topics. Extensive experiments on various real-world data sets with state-of-the-art baselines demonstrate the high quality of topics learned by PTM and its robustness with reduced training samples. It is also interesting to show that i) SPTM gains a clear edge over PTM when the number of pseudo documents is relatively small, and ii) the constraint that a short text belongs to only one pseudo document is critically important for the success of PTM. We finally take an in-depth semantic analysis to unveil directly the fabulous function of pseudo documents in finding cross-text word co-occurrences for topic modeling.

Recently, with the development of mobile Internet and smartphones, the online minimum bipartite matching in real time spatial data (OMBM) problem becomes popular. Specifically, given a set of service providers with specific locations and a set of users who dynamically appear one by one, the OMBM problem is to find a maximum-cardinality matching with minimum total distance following that once a user appears, s/he must be immediately matched to an unmatched service provider, which cannot be revoked, before subsequent users arrive. To address this problem, existing studies mainly focus on analyzing the worst-case competitive ratios of the proposed online algorithms, but study on the performance of the algorithms in practice is absent. In this paper, we present a comprehensive experimental comparison of the representative algorithms of the OMBM problem. Particularly, we observe a surprising result that the simple and efficient greedy algorithm, which has been considered as the worst due to its exponential worst-case competitive ratio, is significantly more effective than other algorithms. We investigate the results and further show that the competitive ratio of the worst case of the greedy algorithm is actually just a constant, 3.195, in the average-case analysis. We try to clarify a 25-year misunderstanding towards the greedy algorithm and justify that the greedy algorithm is not bad at all. Finally, we provide a uniform implementation for all the algorithms of the OMBM problem and clarify their strengths and weaknesses, which can guide practitioners to select appropriate algorithms for various scenarios.

Aspect-based opinion mining is to find elaborate opinions towards an underlying theme, perspective or viewpoint as to a subject such as a product or an event. Nowadays, with rapid growing of opinionated text on the Web, mining aspect-level opinions has become a promising means for online public opinion analysis. In particular, the booming of various types of online media provide diverse yet complementary information, bringing unprecedented opportunities for public opinion analysis across different populations. Along this line, in this paper, we propose CAMEL, a novel topic model for complementary aspect-based opinion mining across asymmetric collections. CAMEL gains complementarity by modeling both common and specific aspects across different collections, and keeping all the corresponding opinions for contrastive study. To further boost CAMEL, we propose AME, an automatic labeling scheme for maximum entropy model, to help discriminate aspect and opinion words without heavy human labeling. Extensive experiments on synthetic multicollection data sets demonstrate the superiority of CAMEL to baseline methods, in leveraging cross-collection complementarity to find higher-quality aspects and more coherent opinions as well as aspect-opinion relationships. This is particularly true when the collections get seriously imbalanced. Experimental results also show that the AME model indeed outperforms manual labeling in suggesting true opinion words. Finally, case study on two public events further demonstrates the practical value of CAMEL for real-world public opinion analysis.

The tremendous development of online social media have changed people's life fundamentally in recent years. Weibo, a Twitter-like service in China, has attracted more than 500 million users in less than four years and produces more than 100 million Chinese tweets every day. In these massive tweets, different user interests and daily trends are reflected by different topics. While to our best knowledge, a systematic investigation of topic dynamics in Weibo is still missing. Aiming at filling this vital gap, we try to disclose the evolving patterns of topics from the perspective of time, geography, gender, emotion and interaction. First, an incremental learning framework is established to classify more than 200 million tweets into seven topics fast and accurately, whose F-measure arrives as high as 84%. Second, many interesting patterns in topic dynamics are revealed. For instance, happy Entertainment accounts for over half of the tweets and angry Finance possesses the most significant periodic pattern. Besides, the female and male users prefer different topics and Finance shows a surprisingly high correlation between connected users. Finally, our findings could provide insights for the topic-related applications in social media, like event detection or content recommendation.

Study of reciprocity helps to find influential factors for users building relationships, which greatly facilitates the social behavior understanding in trust networks. In the previous literature, the dynamics of both network structure and user generated content are rarely considered. Our investigation of the available timing information from a real-world network demonstrates that time delay has significant impact on reciprocity formation. In particular, we find structural factors possess greater effect on short-term reciprocity while factors based on user generated content become more important for long-term reciprocity. Based on the empirical analysis, we redefine the reciprocity prediction problem as a learning task specific to each pair of users with different reciprocal delays. Evaluations show that our time-aware framework eventually outperforms the conventional classifiers that ignore the temporal information. Meanwhile, we tackle the problem of concept drift through fitting the evolving trend of features for Naive Bayes and performing periodic retraining for Logistic Regression classifiers, respectively.

Recent years have witnessed the explosive growth of online social media. Weibo, a Twitter-like online social network in China, has attracted more than 300 million users in less than three years, with more than 1000 tweets generated in every second. These tweets not only convey the factual information, but also reflect the emotional states of the authors, which are very important for understanding user behaviors. However, a tweet in Weibo is extremely short and the words it contains evolve extraordinarily fast. Moreover, the Chinese corpus of sentiments is still very small, which prevents the conventional keyword-based methods from being used. In light of this, we build a system called MoodLens, which to our best knowledge is the first system for sentiment analysis of Chinese tweets in Weibo. In MoodLens, 95 emoticons are mapped into four categories of sentiments, i.e. angry, disgusting, joyful, and sad, which serve as the class labels of tweets. We then collect over 3.5 million labeled tweets as the corpus and train a fast Naive Bayes classifier, with an empirical precision of 64.3%. MoodLens also implements an incremental learning method to tackle the problem of the sentiment shift and the generation of new words. Using MoodLens for real-time tweets obtained from Weibo, several interesting temporal and spatial patterns are observed. Also, sentiment variations are well captured by MoodLens to effectively detect abnormal events in China. Finally, by using the highly efficient Naive Bayes classifier, MoodLens is capable of online real-time sentiment monitoring. The demo of MoodLens can be found at http://goo.gl/8DQ65.

PageRank has been broadly applied to get credible rank sequences of nodes in many networks such as the web, citation networks, or online social networks. However, in the real world, it is usually hard to ascertain a complete structure of a network, particularly a large-scale one. Some researchers have begun to explore how to get a relatively accurate rank more efficiently. They have proposed some local approximation methods, which are especially designed for quickly estimating the PageRank value of a new node, after it is just added to the network. Yet, these local approximation methods rely on the link server too much, and it is difficult to use them to estimate rank sequences of nodes in a group. So we propose a new method called DIGRank, which uses global Degree to facilitate Ranking in an Incomplete Graph and which takes into account the frequent need for applications to rank users in a community, retrieve pages in a particular area, or mine nodes in a fractional or limited network. Based on experiments in small-world and scale-free networks generated by models, the DIGRank method performs better than other local estimation methods on ranking nodes in a given subgraph. In the models, it tends to perform best in graphs that have low average shortest path length, high average degree, or weak community structure. Besides, compared with an local PageRank and an advanced local approximation method, it significantly reduces the computational cost and error rate.

Page Rank has been widely used in ranking retrieval results on the web, finding the top influential papers in citation networks or detecting valuable users in online social networks. However, in practice, it is usually hard to obtain a complete structure of any above networks to rank nodes. Thus, some researchers have begun to explore how to get estimated ranks efficiently without acquiring the whole network. They have proposed some approximating methods, however, it is difficult to determine which method is the best one or which is suitable to a certain application. In this case, we set experiments in small-world and scale-free generated networks to certify the feasibility and characteristics of four approximating methods. We also use eleven real networks to mention different optimal conditions for these methods. We find the DIG Rank method performs better than other local estimation methods in almost every given sub graph. Besides, Mean field approach method tends to perform well in networks that have low average shortest path length, small amount of nodes with the same low in degree, or weak community structure. Finally, we apply the most versatile method DIG Rank to Sina micro-blog website to precisely classify users in a group as elites, grassroots or mummy users.

This paper describes a kernel based Web Services (abbrevi-ated as service) matching mechanism for service discoveryand integration. The matching mechanism tries to exploitthe latent semantics by the structure of services. Using textual similarity and n-spectrum kernel values as features of low-level and mid-level, we build up a model to estimate thefunctional similarity between services, whose parameters arelearned by a Ranking-SVM. The experiment results showedthat several metrics for the retrieval of services have beenimproved by our approach.