Time series data from monitoring applications reflect the physical or logical states of the objects, which may produce time series of distinguishable characteristics in different states. Thus, time series data can usually be split into different segments, each reflecting a state of the objects. These states carry rich high-level semantic information, e.g., run, walk, or jump, which helps people better understand the behaviour of the monitored objects. Nevertheless, these states are latent and hard to discover, because the characteristic of time series is complicated and the computational cost is high. This paper develops an efficient and effective unsupervised approach for inferring the latent states of massive multivariate time data. To reduce the computational cost, we present Time2State, a scalable framework that utilizes a sliding window and an encoder to greatly reduce the length of raw time series. To train the encoder, we propose a novel unsupervised loss function, LSE-Loss. Extensive experiments show that compared to the state-of-the-art time series representation learning methods of the same kind, LSE-Loss brings a performance improvement of up to 15% in accuracy.

This paper addresses the problem of anomaly detection for high-dimensional sensing data. The one-class support vector machine (OCSVM) is one of the most popular unsupervised methods for anomaly detection. When data are high dimensional and large scale, however, the efficiency of OCSVM-based methods in anomaly detection suffers. Although dimensionality-reduction tools, such as deep belief networks, can be applied to compress the high-dimensional data to alleviate the problem, the accuracy and timely detection are still hard to improve due to the inherent features of OCSVM. In this paper, we propose a new form of OCSVM model based on the structure of the compressed data and the characteristics of OCSVM. Based on the new model, we design both optimal and approximate methods for model training and testing. We evaluate the performance of our methods with extensive experiments on four real-world datasets. The experimental results demonstrate that our new methods, both optimal and approximate ones, not only significantly outperform the state-of-the-art in accuracy and efficiency, but also achieve the good performance without the need of manual parameter tuning. In addition, our approximate training and testing mechanism can reduce the computing time by three orders of magnitude with a negligible loss in accuracy.

Finding dense components in graphs is of great importance in analysing the structure of networks. Popular frameworks for discovering dense subgraphs are core and truss decompositions. Recently, Sarıyüce et al. introduced nucleus decomposition, which uses$r$-cliques contained in$s$-eliques, where$s > r$, as the basis for defining dense subgraphs. Nucleus decomposition can reveal interesting subgraphs that can be missed by core and truss decompositions. In this paper, we present nucleus decomposition in probabilistic graphs. The major questions we address are: How to define meaningfully nucleus decomposition in probabilistic graphs? How hard is computing nucleus decomposition in probabilistic graphs? Can we devise efficient algorithms for exact or approximate nucleus decomposition in large graphs? We present three natural definitions of nucleus decomposition in probabilistic graphs: local, global, and weakly-global. We show that the local version is in PTIME, whereas global and weakly-global are #P-hard and NP-hard, respectively. We present an efficient and exact dynamic programming approach for the local case. Further, we present statistical approximations that can scale to bigger datasets without much loss of accuracy. For global and weakly-global decompositions we complement our intractability results by proposing efficient algorithms that give approximate solutions based on search space pruning and Monte-Carlo sampling. Extensive experiments show the scalability and efficiency of our algorithms. Compared to probabilistic core and truss decompositions, nucleus decomposition significantly outperforms in terms of density and clustering metrics.

Smart cameras, as typical IoT devices, are widely adopted to provide surveillance on individuals, homes, and the environment. The unavoidably captured sensitive visuals via these cameras may raise significant security concerns, while the prevalent software defects and authentication misconfiguration issues aggravate the vulnerability of such devices. However, traditional cryptography techniques are inadequate to provide full protection of these devices due to the large computation overhead. In this context, realizing accountability for these surveillance systems shall be the last line of defense in the presence of fast-evolving and high-influential threats. We propose EviChain, a scalable blockchain-based solution to trace the operations on intelligent surveillance cameras and reserve the evidence for any misuse in tamper-proofing manipulation records. Building a blockchain over the distributed cameras is challenging due to the limited capacity of on-board memory. To tackle this challenge, we design a cooperative mechanism that enables cameras to adaptively join in groups and share storage for recording blocks. In addition, we present a computation efficiency and delay-aware block generation strategy to reduce the cost of the consensus process. We perform extensive simulations to validate the superior performance of EviChain over other baselines, for example, Practical Byzantine Fault Tolerance (PBFT).

Truss decomposition is a popular approach for discovering cohesive subgraphs. However, truss decomposition on probabilistic graphs is challenging. State-of-the-art either do not scale to large graphs or use approximation techniques to achieve scalability. We present an exact and scalable algorithm for truss decomposition of probabilistic graphs. The algorithm is based on progressive tightening of the estimate of the truss value of each edge based on h-index computation and novel use of dynamic programming. Our proposed algorithm (1) is significantly faster than state-of-the-art and scales to much larger graphs, (2) is progressive by allowing the user to see near-results along the way, (3) does not sacrifice the exactness of final result, and (4) achieves all these while processing only an edge and its immediate neighbors at a time, thus resulting in smaller memory footprint. Our extensive experimental results confirm the scalability and efficiency of our algorithm.

Edge computing emerges as an alternative to cloud computing in the scenarios where the end devices require lower latency and faster access speeds. Edge nodes are deployed at the proximity of the end devices to reduce response time. On the other hand, the edge nodes are usually owned by small organizations that have limited operations and maintenance capabilities. Data on the edge may be easily damaged, due to external attacks or internal hardware failures. Therefore, it is essential to verify data integrity in edge computing. However, edge environment requires a different trust model compared with other computing and storage paradigm. Besides, compared with cloud storage, edge storage is decentralized and storage service participants may pose greater internal and external threats. This paper proposes a blockchain-based intelligent crowdsourcing audit approach (Crowdauditing) to achieve on-chain and off-chain credibility of audit results. The model relies on an untrusted auditor committee from the crowd to audit data integrity and uses smart contracts as the core of the intelligent system to ensure the reliability of result submission, the accuracy of the result judgment, and reasonable punishments and rewards. Specifically, an unbiased selection algorithm is proposed to achieve fairness during the auditor committee construction. An innovative two-stage submission strategy is proposed to ensure that the auditor committee can reach a consensus on the off-chain audit results. An incentive mechanism is carefully designed to force auditors providing audit services honestly to maximize their own rewards. Moreover, we modeled that as a game of n players, which proves the reliability of the result. Finally, we implement a prototype of Crowdauditing based on smart contracts. The extensive experimental results demonstrate the effectiveness of Crowdauditing.

In this article, we introduce a new generalization of WBM, Conflict-Aware Weighted Bipartite b-Matching (CA-WBM), that can address the conflict challenges mentioned above.

The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling.

Portable smart devices have become prevalent and are used for ubiquitous access to the Internet in our daily life. Taking advantage of this trend, brick-and-mortar retailers have been increasingly deploying free Wi-Fi hotspots to provide easy Internet access for their customers. This opens the opportunity for retailers to collect customer information and perform data mining to improve the quality of their service. In this paper, we propose a novel value-added service to Wi-Fi data mining, Rec2PI, which can infer users' preference profiles based on recommendations pushed by third-party apps. Such profiles can be used to improve users' online experience and enable a brick-and-mortar retailer to participate in the global advertising business. Since the goal and technical difficulties of Rec2PI significantly differ from those of traditional recommender systems, we present a general framework of Rec2PI to illustrate its process. To tackle the technical challenges in profile inference, we propose novel algorithms built using copulas, a statistical tool suitable for capturing complex dependence structure beyond the scope of linear dependence. In the context of rating-based recommendations, we evaluate the proposed algorithms using an open dataset and a real-world recommender system. The evaluation results show that Rec2PI creates consistent and accurate inference results.

The weighted bipartite b-matching problem (WBM) plays a significant role in many real-world applications, including resource allocation, scheduling, Internet advertising, and E-commerce. WBM has been widely studied and efficient matching algorithms are well known. In this work, we study a novel variant of WBM, called conflict-aware WBM (CA-WBM), where conflict constraints are present between vertices of the bipartite graph. In CA-WBM, if two vertices (on the same side) are in conflict, they may not be included in the matching result simultaneously. We present a generalized formulation of CA-WBM in the context of E-commerce, where diverse matching results are often desired (e.g., movies of different genres and merchants selling products of different categories). While WBM is efficiently solvable in polynomial-time, we show that CA-WBM is NP-hard. We propose approximate and randomized algorithms to solve CA-WBM and show that they achieve close to optimal solutions via comprehensive experiments using synthetic datasets. We derive a theoretical bound on the approximation ratio of a greedy algorithm for CA-WBM and show that it is scalable on a large-scale real-world dataset.

Load curve data in power systems refers to users' electrical energy consumption data periodically collected with meters. It has become one of the most important assets for modern power systems. Many operational decisions are made based on the information discovered in the data. Load curve data, however, usually suffers from corruptions caused by various factors, such as data transmission errors or malfunctioning meters. To solve the problem, tremendous research efforts have been made on load curve data cleansing. Most existing approaches apply outlier detection methods from the supply side (i.e., electricity service providers), which may only have aggregated load data. In this paper, we propose to seek aid from the demand side (i.e., electricity service users). With the help of readily available knowledge on consumers' appliances, we present an appliance-driven approach to load curve data cleansing. This approach utilizes data generation rules and a Sequential Local Optimization Algorithm (SLOA) to solve the Corrupted Data Identification Problem (CDIP). We evaluate the performance of SLOA with real-world trace data and synthetic data. The results indicate that, comparing to existing load data cleansing methods, such as B-spline smoothing, our approach has an overall better performance and can effectively identify consecutive corrupted data. Experimental results also show that our method is robust in various tests.

In an emerging trend, more and more Internet users search for information from Community Question and Answer (CQA) websites, as interactive communication in such websites provides users with a rare feeling of trust. More often than not, end users look for instant help when they browse the CQA websites for the best answers. Hence, it is imperative that they should be warned of any potential commercial campaigns hidden behind the answers. Existing research focuses more on the quality of answers and does not meet the above need. Textual similarities between questions and answers are widely used in previous research. However, this feature will no longer be effective when facing commercial paid posters. More context information, such as writing templates and a user's reputation track need to be combined together to form a new model to detect the potential campaign answers. In this paper, we develop a system that automatically analyzes the hidden patterns of commercial spam and raises alarms instantaneously to end users whenever a potential commercial campaign is detected. Our detection method integrates semantic analysis and posters' track records and utilizes the special features of CQA websites largely different from those in other types of forums such as microblogs or news reports. Our system is adaptive and accommodates new evidence uncovered by the detection algorithms over time. Validated with real-world trace data from a popular Chinese CQA website over a period of three months, our system shows great potential towards adaptive online detection of CQA spams.

We initiate a systematic study to help distinguish a special group of online users, called hidden paid posters, or termed "Internet water army" in China, from the legitimate ones. On the Internet, the paid posters represent a new type of online job opportunities. They get paid for posting comments or articles on different online communities and websites for hidden purposes, e.g., to influence the opinion of other people towards certain social events or business markets. While being an interesting strategy in business marketing, paid posters may create a significant negative effect on the online communities, since the information from paid posters is usually not trustworthy. When two competitive companies hire paid posters to post fake news or negative comments about each other, normal netizens may feel overwhelmed and find it difficult to put any trust in the information they acquire from the Internet. In this paper, we thoroughly investigate the behavioral pattern of online paid posters based on real-world trace data. We design and validate a new detection mechanism, using both non-semantic analysis and semantic analysis, to identify potential online paid posters. Our test results with real-world datasets show a very promising performance.

In this paper, we study an interesting problem: continuously monitoring k-means clustering of sensor readings in a large sensor network. Given a set of sensors whose readings evolve over time, we want to maintain the k-means of the readings continuously. The optimization goal is to reduce the reporting cost in the network, that is, let as few sensors as possible report their current readings to the data center in the course of maintenance. To tackle the problem, we propose the reading reporting tree, a hierarchical data collection, and analysis framework. Moreover, we develop several reporting cost-effective methods using reading reporting trees in continuous k-means monitoring. First, a uniform sampling method using a reading reporting tree can achieve good quality approximation of k-means. Second, we propose a reporting threshold method which can guarantee the approximation quality. Last, we explore a lazy approach which can reduce the intermediate computation substantially. We conduct a systematic simulation evaluation using synthetic data sets to examine the characteristics of the proposed methods.