Search

With the increase of mobile devices, Mobile Crowdsensing (MCS) has become an efficient way to ubiquitously sense and collect environment data. Comparing to traditional sensor networks, MCS has a vital advantage that workers play an active role in collecting and sensing data. However, due to the openness of MCS, workers and sensors are of different qualities. Low quality sensors and workers may yield noisy data or even inaccurate data. Which gives the importance of inferring the quality of workers and sensors and seeking a valid task assignment with enough total qualities for MCS. To solve the problem, we adopt truth inference methods to iteratively infer the truth and qualities. Based on the quality inference, this paper proposes a task assignment problem called quality-bounded task assignment with redundancy constraint (QTAR). Different from traditional task assignment problem, redundancy constraint is added to satisfy the preliminaries of truth inference, which requires that each task should be assigned a certain or more amount of workers. We prove that QTAR is NP-complete and propose a $ (2+\epsilon)$ (2 + ε) - approximation algorithm for QTAR, called QTA. Finally, experiments are conducted on both synthesis data and real dataset. The results of the experiments prove the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

Recently, with the explosive increase in Internet data, the traditional Graph-based Semi-Supervised Learning (GSSL) model is not suitable to deal with large scale data as the high computation complexity. Besides, GSSL models perform classification on a fixed input data graph. The quality of initialized graph has a great effect on the classification result. To solve this problem, in this paper, we propose a novel approach, named optimal bipartite graph-based SSL (OBGSSL). Instead of fixing the input data graph, we learn a new bipartite graph to make the result more robust. Based on the learned bipartite graph, the labels of the original data and anchors can be calculated simultaneously, which solves co-classification problem in SSL. Then, we use the label of anchor to handle out-of-sample problem, which preserves well classification performance and saves much time. The computational complexity of OBGSSL is O(ndmt + nm2), which is a significant improvement compared with traditional GSSL methods that need O(n2d + n3) , where n, d, m and t are the number of samples, features anchors and iterations, respectively. Experimental results demonstrate the effectiveness and efficiency of our OBGSSL model. [ABSTRACT FROM AUTHOR]

Survival analysis aims at predicting the time to event of interest along with its probability on longitudinal data. It is commonly used to make predictions for a single specific event of interest at a given time point. However, predicting the occurrence of multiple events of interest simultaneously and dynamically is needed in many real-world applications. An intuitive way to solve this problem is to simply apply the standard survival analysis method independently to each prediction task at each time point. However, it often leads to a sub-optimal solution since the underlying dependencies between these tasks are ignored. This motivates us to analyze these prediction tasks jointly in order to select the common features shared across all the tasks. In this paper, we formulate a temporal (Multiple Time points) Multi-Task learning framework (MTMT) for survival analysis problems using tensor representation. More specifically, given a survival dataset and a sequence of time points, which are considered as the monitored time points for the events of interest, we reformulate the survival analysis problem to jointly handle each task at each time point and optimize them simultaneously. We demonstrate the performance of the proposed MTMT model on important real-world datasets, including employee attrition and medical records. We show the superior performance of the MTMT model compared to several state-of-the-art models using standard metrics. We also provide the list of important features selected by our MTMT model thus demonstrating the interpretability of the proposed model. [ABSTRACT FROM AUTHOR]

Multi-set membership queries are fundamental operations in data science. In this paper, we propose a new data structure for multi-set membership queries, named coloring embedder, which is fast, accurate, and memory efficient. The idea of coloring embedder is to first map elements to a high-dimensional space, which nearly eliminates hashing collisions, and then use a dimensional reduction representation, similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that the coloring embedder is effective in solving the problem of multi-set membership queries. We also find that web cache sharing is one of the typical application scenarios of the multi-set membership queries and current methods based on Bloom filters always send redundant queries. We apply coloring embedder to web cache sharing by arranging our data structure on the on-chip and off-chip memory and designing query, insertion and deletion operations for this scenario. The experimental results show that compared with the present method, our method can reduce the queries sent by proxies while reaching equal hit rate with the same size of on-chip memory. The source code of coloring embedder has been released on Github. [ABSTRACT FROM AUTHOR]

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases and machine learning. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications. Its two compressed versions, $b$ b -bit MinHash and Odd Sketch, can significantly reduce the memory usage of the MinHash, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion, unfortunately, $b$ b -bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we previously designed a memory-efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared with MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. In this paper, we further develop a faster method, MaxLogOPH++. Compared with MaxLogHash, MaxLogOPH++ reduces the time complexity for updating each coming element from $O(k)$ O (k) to $O(1)$ O (1) with a small additional memory. We conduct experiments on a variety of datasets, and experimental results demonstrate the efficiency and effectiveness of our methods. [ABSTRACT FROM AUTHOR]

Ranking paths becomes an increasingly important functionality in many transportation services, where multiple paths connecting a source-destination pair are offered to drivers. We study ranking such paths under specific contexts, e.g., at a departure time and for a specific driver. More specifically, we model ranking as a regression problem where we assign a ranking score to each path with the help of historical trajectories. The intuition is that if a driver’s trajectory used path $P$ P at time $t$ t , we consider this as an evidence that path $P$ P is preferred by the driver at time $t$ t , thus should have a higher ranking score than other paths connecting the same source and destination. To solve the regression problem, we first propose an effective training data enriching method to obtain a compact and diversified set of training paths using historical trajectories, which provides a data foundation for efficient and effective learning. Next, we propose a multi-task learning framework that considers features representing both candidate paths and contexts. Specifically, a road network embedding is proposed to embed paths into feature vectors by considering both road network topology and spatial properties, such as distances and travel times. By modeling different departure times as a temporal graph, graph embedding is used to embed departure times into feature vectors. The objective function not only considers the discrepancies on ranking scores but also the reconstruction errors of the spatial properties of the paths, which in turn improves the final ranking estimation. Empirical studies on a substantial trajectory data set offer insight into the designed properties of the proposed framework, indicating that it is effective and practical in real world settings. [ABSTRACT FROM AUTHOR]

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, called Graph-Repairing Rules (${\sf GRR}$ GRR s). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called $\delta$ δ -GRR). We study three fundamental problems associated with both ${\sf GRR}$ GRR s and $\delta$ δ -GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using ${\sf GRR}$ GRR s or $\delta$ δ -GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data. [ABSTRACT FROM AUTHOR]

Online social media have aroused much research interest in recent years. In contrast to previous work that focused on the detection of emerging topics, this article undertakes the prediction of active users in online social events, which is so far rarely explored. This prediction task is formulated as a binary classification problem that built on real-world tweet streams, taking Ferguson event and New York Chockhold event as examples. Then, a comprehensive user feature system is designed to characterize the events’ online participants, which includes not only basic statistical characteristics and image-pixel-level features, but also some emotional features and personality features. Next, the Weighted Random Forest (Weighted-RF) classifier is adopted to solve the classification problem. Based on the user feature system and the classifier, the experience of a previous event can be archived and applied to the prediction of later similar events. Experimental results show that the Weighted-RF trained by samples of Ferguson event can effectively predict active users in NYC event, with an AUC value around 0.8392. Besides, the image-content based personality model provides a new tool for depicting user portraits, which further contributes to the quantitative analysis of online social events. [ABSTRACT FROM AUTHOR]

A heterogeneous information network (HIN) is one whose nodes model objects of different types and whose links model objects’ relationships. To enrich its information, objects in an HIN are typically associated with additional attributes. We call such an HIN an Attributed HIN or AHIN. We study the problem of clustering objects in an AHIN, taking into account objects’ similarities with respect to both object attribute values and their structural connectedness in the network. We show how supervision signal, expressed in the form of a must-link set and a cannot-link set, can be leveraged to improve clustering results. We put forward the SCHAIN algorithm to solve the clustering problem, and two highly efficient variants, SCHAIN-PI and SCHAIN-IRAM, which employ the power iteration based method and the implicitly restarted Arnoldi method respectively to compute eigenvectors of a matrix. We conduct extensive experiments comparing SCHAIN-based algorithms with other state-of-the-art clustering algorithms. Our results show that SCHAIN-IRAM outperforms other competitors in terms of clustering effectiveness and is highly efficient. [ABSTRACT FROM AUTHOR]

Analyzing short texts infers discriminative and coherent latent topics that is a critical and fundamental task since many real-world applications require semantic understanding of short texts. Traditional long text topic modeling algorithms (e.g., PLSA and LDA) based on word co-occurrences cannot solve this problem very well since only very limited word co-occurrence information is available in short texts. Therefore, short text topic modeling has already attracted much attention from the machine learning research community in recent years, which aims at overcoming the problem of sparseness in short texts. In this survey, we conduct a comprehensive review of various short text topic modeling techniques proposed in the literature. We present three categories of methods based on Dirichlet multinomial mixture, global word co-occurrences, and self-aggregation, with example of representative approaches in each category and analysis of their performance on various tasks. We develop the first comprehensive open-source library, called STTM, for use in Java that integrates all surveyed algorithms within a unified interface, benchmark datasets, to facilitate the expansion of new methods in this research field. Finally, we evaluate these state-of-the-art methods on many real-world datasets and compare their performance against one another and versus long text topic modeling algorithm. [ABSTRACT FROM AUTHOR]

As a key mission of the modern traffic management, crowd flow prediction (CFP) benefits in many tasks of intelligent transportation services. However, most existing techniques focus solely on forecasting entrance and exit flows of metro stations that do not provide enough useful knowledge for traffic management. In practical applications, managers desperately want to solve the problem of getting the potential passenger distributions to help authorities improve transport services, termed as crowd flow distribution (CFD) forecasts. Therefore, to improve the quality of transportation services, we proposed three spatiotemporal models to effectively address the network-wide CFD prediction problem based on the online latent space (OLS) strategy. Our models take into account the various trending patterns and climate influences, as well as the inherent similarities among different stations that are able to predict both CFD and entrance and exit flows precisely. In our online systems, a sequence of CFD snapshots is used as the training data. The latent attribute evolutions of different metro stations can be learned from the previous trend and do the next prediction based on the transition patterns. All the empirical results demonstrate that the three developed models outperform all the other state-of-the-art approaches on three large-scale real-world datasets. [ABSTRACT FROM AUTHOR]

The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is to devise a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. In this work, we propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis, conducted over a wide range of publicly available real-world datasets, reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30–60 percent less space and speeding up query execution by a factor of 2 – 81×. [ABSTRACT FROM AUTHOR]