Search

In this paper, we investigate a very challenging task of automatically generating presentation slides for academic papers. The generated presentation slides can be used as drafts to help the presenters prepare their formal slides in a quicker way. A novel system called PPSGen is proposed to address this task. It first employs the regression method to learn the importance scores of the sentences in an academic paper, and then exploits the integer linear programming (ILP) method to generate well-structured slides by selecting and aligning key phrases and sentences. Evaluation results on a test set of 200 pairs of papers and slides collected on the web demonstrate that our proposed PPSGen system can generate slides with better quality. A user study is also illustrated to show that PPSGen has a few evident advantages over baseline methods. [ABSTRACT FROM PUBLISHER]

Wireless data broadcast allows a large number of users to retrieve data simultaneously in mobile databases, resulting in an efficient way of using the scarce wireless bandwidth. However, the efficiency of data access methods is limited by an inherent property that data can only be accessed strictly sequentially by users. To properly cope with the inherent property, this paper presents three predaclaration-based transaction processing methods that yield a significant performance improvement in wireless data broadcast. [ABSTRACT FROM AUTHOR]

Focuses on the importance of finding subjects of photographic image on the concise papers. Development of digital image on the multimedia caption; Determination of visual focus on the segmented image; Identification of ranking on the photograph.

Many applications need to read an entire database in a consistent way. This global-reading of an entire database formulated as a global-read transaction (GRT) is not a trivial issue since it will cause a high degree of interference to other concurrent transactions. Conventional concurrency control protocols are obviously inadequate in handling the long-lived GRT. Previous studies [1], [3], [4] proposed additional tests, namely, the Color Test and the Shade Test, to handle conflicts between the GRT and update transactions. However, we discovered that both algorithms can bring about nonserializable schedules of transactions. We propose an enhanced algorithm directly built on the two algorithms to guarantee the serializability of transactions. [ABSTRACT FROM AUTHOR]

In recommendation tasks, we model user preferences by learning node representations (i.e., user and item embeddings) based on the observed user-item interaction data, which is a bipartite graph. Graph Neural Networks (GNNs) are widely used to refine the representations by exploring the topology of the graph: embeddings of neighbors are propagated to each node to reconstruct its embeddings. However, the propagation strategy in existing GNNs is empirical and defective: (1) a substantial proportion of links are missed in the sparse observed graph, which causes ineffective and biased propagation; and (2) the propagation weights are determined by a coarse pre-defined rule, which only takes the degree of nodes into consideration. In this paper, we propose a dense and data-driven propagation mechanism for GNNs. Considering the graph we use to propagate embeddings in recommendation tasks is extremely sparse, we complement it and use the predicted graph as the new propagation tool. We learn the propagation matrix from the data, and propose a Self-propagation Graph Neural Network (SGNN). Since it is very space- and time-consuming to maintain a large and dense propagation matrix, we factorize it for storing and updating. In this paper, we propose three methods to complete the sparse graph and construct the propagation matrix: (1) we complete the graph based on a recommendation model; (2) we measure the node distance based on spectral clustering; (3) we predict missing links of the graph based on predictive embeddings. In SGNN, the embeddings can be propagated to not only the observed neighbors, but also the potential yet unobserved neighbors, and the propagation weights are learned based on the connection strength. Comprehensive experiments on three real-world datasets demonstrate the effectiveness and efficiency of our proposed model: SGNN outperforms recent state-of-the-art GNNs significantly. Codes are available on https://github.com/Wenhui-Yu/LCFN. [ABSTRACT FROM AUTHOR]

Multi-Task Learning (MTL) is a learning paradigm in machine learning and its aim is to leverage useful information contained in multiple related tasks to help improve the generalization performance of all the tasks. In this paper, we give a survey for MTL from the perspective of algorithmic modeling, applications and theoretical analyses. For algorithmic modeling, we give a definition of MTL and then classify different MTL algorithms into five categories, including feature learning approach, low-rank approach, task clustering approach, task relation learning approach and decomposition approach as well as discussing the characteristics of each approach. In order to improve the performance of learning tasks further, MTL can be combined with other learning paradigms including semi-supervised learning, active learning, unsupervised learning, reinforcement learning, multi-view learning and graphical models. When the number of tasks is large or the data dimensionality is high, we review online, parallel and distributed MTL models as well as dimensionality reduction and feature hashing to reveal their computational and storage advantages. Many real-world applications use MTL to boost their performance and we review representative works in this paper. Finally, we present theoretical analyses and discuss several future directions for MTL. [ABSTRACT FROM AUTHOR]

Event logs that are recorded by information systems provide a valuable starting point for the analysis of processes in various domains, reaching from healthcare, through logistics, to e-commerce. Specifically, behavioral patterns discovered from an event log enable operational insights, even in scenarios where process execution is rather unstructured and shows a large degree of variability. While such behavioral patterns capture frequently recurring episodes of a process’ behavior, they are not limited to sequential behavior but include notions of concurrency and exclusive choices. Existing algorithms to discover behavioral patterns are context-agnostic, though. They neglect the context in which patterns are observed, which severely limits the granularity at which behavioral regularities are identified. In this paper, we therefore present an approach to discover contextual behavioral patterns. Contextual patterns may be frequent solely in a certain partition of the event log, which enables fine-granular insights into the aspects that influence the conduct of a process. Moreover, we show how to analyze the discovered contextual behavioral patterns in terms of causal relations between context information and the patterns, as well as correlations between the patterns themselves. A complete analysis methodology leveraging all the tools presented in the paper and supplemented by interpretations guidelines is also provided. Finally, experiments with real-world event logs demonstrate the effectiveness of our techniques in obtaining fine-granular process insights. [ABSTRACT FROM AUTHOR]

Entity resolution (ER) identifies data instances referring to the same real-world entity and has received enormous research attention. In this paper, we examine the task of ER from a broader perspective, with its input extended from textual records, which are conventionally studied in the literature, to other modalities such as check-in sequences, GPS trajectories and surveillance video frames to generate new applications. Our goal in this paper is to design an effective model to uniformly support all these ER applications with different input formats. Technically, we fully exploit the semantic contexts of embedding vectors for the pair of input instances. In particular, we propose an integrated multi-context attention framework that takes into account self-attention, pair-attention and global-attention from three types of context. The idea can be further extended to incorporate attribute attention in order to support structured datasets. We conduct extensive experiments on a diverse class of entity resolutions tasks, including tasks on unstructured, structured and dirty textual records, check-in sequences, GPS trajectories and surveillance video frames. The experimental results verified the effectiveness and generality of our model. When compared with strong baselines in these applications, our model can achieve superior or comparative performance. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

To obtain reliable results from conflicting data in mobile crowdsensing, numerous truth discovery protocols have been proposed in the past decade. However, most of them do not consider the data privacy of entities involved (e.g., workers and servers), and several existing privacy-preserving truth discovery protocols either provide limited privacy protection or have heavy computation and communication overheads due to iterative computation and transmission over large ciphertexts. In this paper, we aim to propose privacy-preserving and lightweight truth discovery protocols to tackle the above problems. Specifically, we carefully design an anonymization protocol named AnonymTD to delink workers from their data, where workers’ data are computed and transmitted without complicated encryption. To further reduce each worker's overheads in the scenarios where workers are willing to share their weights, we resort to the perturbation technology to propose a more lightweight truth discovery protocol named PerturbTD. Based on workers’ perturbed data, two cloud servers in PerturbTD complete most of the workload of truth discovery together, which avoids the frequent involvement of workers. The theoretical analysis and the comparative experiments in this paper demonstrate that our two protocols can achieve our security goals with low computation and communication overheads. [ABSTRACT FROM AUTHOR]

So-called spatial web queries retrieve web content representing points of interest, such that the points of interest have descriptions that are relevant to query keywords and are located close to a query location. Two broad categories of such queries exist. The first encompasses queries that retrieve single spatial web objects that each satisfy the query arguments. Most proposals belong to this category. The second category, to which this paper's proposal belongs, encompasses queries that support exploratory user behavior and retrieve sets of objects that represent regions of space that may be of interest to the user. Specifically, the paper proposes a new type of query, the top- $k$ k spatial textual cluster retrieval ($k$ k -STC) query that returns the top- $k$ k clusters that (i) are located close to a query location, (ii) contain objects that are relevant with regard to given query keywords, and (iii) have an object density that exceeds a given threshold. To compute this query, we propose a DBSCAN-based approach and an OPTICS-based approach that rely on on-line density-based clustering and that exploit early stop conditions. Empirical studies on real data sets offer evidence that the paper's proposals can find good quality clusters and are capable of excellent performance. [ABSTRACT FROM AUTHOR]

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions. [ABSTRACT FROM AUTHOR]

With the proliferation of online social networks, the identification or classification of real-life relationship between users has been very useful for many applications such as financial fraud detection. In real life, usually people with different relationships would present gifts with special meanings to each other on different dates. In many Asian cultures, especially in Chinese culture, the red packet is a traditional form of monetary gift. With the rapid development of the Internet, people gradually began to give electronic red packets instead of paper ones as the means of money gifting on social network platforms. As motivated, in this paper we advocate a novel approach that exploits users’ red packet interactions for users relationship identification on WeChat, one of the largest social platforms in China. Specifically, we analyze the WeChat red packets network, identify the real-life relationship types between users through mining the semantic information of the amount and sending time of each red packet. In order to better capture the red packet gifting behaviors between users for relationship identification, on one hand, we construct an Amount-Date Graph and apply the graph embedding method to learn embeddings of the amount and sending date of each red packet. On the other hand, we propose a novel sequential model, Cross & Attention Sequence Model (CASM), which explicitly learns the interactions between the latent semantic information of each red packet’s amount and sending date in the red packets sequence between two users. To validate our approach, we conduct comprehensive experiments on a real-world WeChat Users Red Packets dataset that involves 8 kinds of real-life relationships. The experiments show that our proposed approach performs significantly better than baselines and achieves 81.70 percent prediction accuracy. [ABSTRACT FROM AUTHOR]

To solve the information explosion problem and enhance user experience in various online applications, recommender systems have been developed to model users’ preferences. Although numerous efforts have been made toward more personalized recommendations, recommender systems still suffer from several challenges, such as data sparsity and cold-start problems. In recent years, generating recommendations with the knowledge graph as side information has attracted considerable interest. Such an approach can not only alleviate the above mentioned issues for a more accurate recommendation, but also provide explanations for recommended items. In this paper, we conduct a systematical survey of knowledge graph-based recommender systems. We collect recently published papers in this field, and group them into three categories, i.e., embedding-based methods, connection-based methods, and propagation-based methods. Also, we further subdivide each category according to the characteristics of these approaches. Moreover, we investigate the proposed algorithms by focusing on how the papers utilize the knowledge graph for accurate and explainable recommendation. Finally, we propose several potential research directions in this field. [ABSTRACT FROM AUTHOR]

Network data in real-world tends to be error-prone due to incomplete sampling, imperfect measurements, etc.; this in turn results in inaccurate results when performing network analysis or modeling, such as node classification and link prediction, on these flawed networks. In this paper, we aim to reconstruct a reliable network from a flawed, undirected, unweighted network, a process referred to network enhancement. More specifically, network enhancement aims to detect the noisy links that are observed in the network but should not exist in the real world, as well as to predict the missing links that do indeed exist in the real world yet remain unobserved. While some attempts have been made to detect either noisy links or missing links, few of these works have considered unifying these two tasks, even though they are inter-dependent and capable of mutually boosting each others’ performance. In this paper, we therefore propose E-Net, an end-to-end graph neural network model, to leverage the mutual influence of these two tasks in order to achieve both goals more effectively. On one hand, detecting noisy links can benefit the performance of missing link prediction, while on the other hand, predicting missing links can provide indirect supervision for detecting noisy link detection when the labels of these noisy links are unavailable. Moreover, by proposing a subgraph extraction mechanism based on random walk with restart, the model can be scaled up to large networks and is able to preserve the local and global structural characteristics. The experimental results on several types of large networks demonstrate that the proposed model obtains an improvement of 10.7 percent on average in terms of F1 for predicting missing links, along with an average of 3.7 percent improvement in terms of precision for detecting noisy links compared with the state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Name disambiguation is a key and also a very tough problem in many online systems such as social search and academic search. Despite considerable research, a critical issue that has not been systematically studied is disambiguation on the fly — to complete the disambiguation in the real-time. This is very challenging, as the disambiguation algorithm must be accurate, efficient, and error tolerance. In this paper, we propose a novel framework — CONNA — to train a matching component and a decision component jointly via reinforcement learning. The matching component is responsible for finding the top matched candidate for the given paper, and the decision component is responsible for deciding on assigning the top matched person or creating a new person. The two components are intertwined and can be bootstrapped via jointly training. Empirically, we evaluate CONNA on two name disambiguation datasets. Experimental results show that the proposed framework can achieve a 1.21-19.84 percent improvement on F1-score using joint training of the matching and the decision components. The proposed CONNA has been successfully deployed on AMiner — a large online academic search system. [ABSTRACT FROM AUTHOR]

In this paper, we study an automatic hypothesis generation (HG) problem, which refers to the discovery of meaningful implicit connections between scientific terms, including but not limited to diseases, chemicals, drugs, and genes extracted from databases of biomedical publications. Most prior studies of this problem focused on the use of static information of terms and largely ignored the temporal dynamics of scientific term relations. Even when the dynamics were considered in a few recent studies, they learned the representations for the scientific terms, rather than focusing on the term-pair relations. Since the HG problem is to predict term-pair connections, it is not enough to know with whom the terms are connected, it is more important to know how the connections have been formed (in a dynamic process). We formulate this HG problem as a future connectivity prediction in a dynamic attributed graph. The key is to capture the temporal evolution of node-pair (term-pair) relations. We propose an inductive edge (node-pair) embedding method named T-PAIR, utilizing both the graphical structure and node attribute to encode the temporal node-pair relationship. We demonstrate the efficiency of the proposed model on three real-world datasets, which are three graphs constructed from Pubmed papers published until 2019 in Neurology, Immunotherapy, and Virology, respectively. Evaluations were conducted on predicting future term-pair relations between millions of seen terms (in the transductive setting), as well as on the relations involving unseen terms (in the inductive setting). Experiment results and case study analyses show the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]

In this paper, we focus on co-selection of instances and features in the semi-supervised learning scenario. In this context, co-selection becomes a more challenging problem as data contain labeled and unlabeled examples sampled from the same population. To carry out such semi-supervised co-selection, we propose a unified framework, called sCOs, which efficiently integrates labeled and unlabeled parts into the co-selection process. The framework is based on introducing both a sparse regularization term and a similarity preserving approach. It evaluates the usefulness of features and instances in order to select the most relevant ones, simultaneously. We propose two efficient algorithms that work for both convex and nonconvex functions. To the best of our knowledge, this paper offers, for the first time ever, a study utilizing nonconvex penalties for the co-selection of semi-supervised learning tasks. Experimental results on some known benchmark datasets are provided for validating sCOs and comparing it with some representative methods in the state-of-the art. [ABSTRACT FROM AUTHOR]

The online retail market shows a sharp increase in traffic during holiday sales. The ability to distinguish customers who will likely purchase is critical for provisioning traffic and for providing cost-effective promotions. This paper uniquely studies the browsing and purchasing behaviors of online shoppers during a yearly sale event in China, the world’s largest online marketplace. Based on 31 million action logs gathered from wide residential areas, we characterize the steps leading to purchases and determine their precursors. We investigate the effect of time (e.g., date, time of date), environment (e.g., platform, viewed category), and action (e.g., session time, clicks, sequence) on purchases. Action cues from shopping behaviors can be used for early detection. While most shoppers start with strong intentions to purchase, yet the moment of ordering comes rather impulsively within 30 seconds to several minutes of browsing. The predictive accuracy reaches as a high AUC of 0.924. The findings in this paper provide an understanding of traffic during mega sale events that can help online shops plan and provide a better user experience for upcoming shopping festivals. [ABSTRACT FROM AUTHOR]

Recommender systems are popular for personalization in online communities. Users, items, and other affiliated information such as tags, item genres, and user friends of an online community form a heterogenous information network. User profiling is the foundation of personalized recommender systems. It provides the basis to discover knowledge about an individual user’s interests to items. Typically, users are profiled with their direct explicit or implicit ratings, which ignored the inter-connections among users, items, and other entity nodes of the information network. This paper proposes a deep reinforcement user profiling approach for recommender systems. The user profiling process is framed as a sequential decision making problem which can be solved with a Reinforcement Learning (RL) agent. The RL agent interacts with the external heterogenous information network environment and learns a decision making policy network to decide whether there is an interest or preference path between a user and an unobserved item. To effectively train the RL agent, this paper proposes a multi-iteration training process to combine both expert and data-specific knowledge to profile users, generate meta-paths, and make recommendations. The effectiveness of the proposed approaches is demonstrated in experiments conducted on three datasets. [ABSTRACT FROM AUTHOR]

This paper concerns the fundamental problem of processing conjunctive queries that contain both keyword and range conditions on public clouds in a privacy preserving manner. No prior Searchable Symmetric Encryption (SSE) based privacy preserving conjunctive query processing scheme satisfies the three requirements of adaptive security, efficient query processing, and scalable index size. In this paper, we propose the first privacy preserving conjunctive query processing scheme that satisfies all the above three requirements. To achieve adaptive security, we propose an Indistinguishable Bloom Filter (IBF) data structure for indexing. To achieve efficient query processing and structural indistinguishability, we propose a highly balanced binary tree data structure called Indistinguishable Binary Tree (IBtree). To achieve scalable and compact index size, we propose an IBtree space compression algorithm to remove redundant information in IBFs. To optimize search efficiency, we propose a traversal minimization algorithm. To make our scheme dynamic, we propose update algorithms. We prove that our scheme is adaptive secure under the IND-CKA secure model. The key contribution of this paper is on achieving conjunctive query processing with both strong privacy guarantee and practical efficiency in terms of both speed and space. We implemented our scheme in C++, evaluated and compared its performance with the prior KRB scheme for keyword queries and the prior PBtree scheme for range queries on two real-world data sets. Experimental results show that our scheme is both fast and scalable. For example, processing a query only takes a few milliseconds for millions of records. [ABSTRACT FROM AUTHOR]

Quantitative analysis is a solid, well established mathematical technique that can be used to analyze the result of survey(s) in a specific field. Survey analysis is usually based on the study of the effect of independent variables on a dependent variable. Although quantitative analysis can use an R-Squared value as a method to measure the strength of the relationship between the independent and dependent variables, it does not capture the effect of participants’ ambiguity when answering questionnaires. The source of such ambiguity stems from the process of completing the survey, whereby the respondent may have answered most of the independent questions with ease, but has difficulty in responding to the overall dependent question (or vice versa). The objective of this paper is to demonstrate the use of fuzzy logic as a mechanism to measure the uncertainty faced by participants when filling a questionnaire. Based on the participants’ responses to the independent variables, the proposed technique uses fuzzy logic inference to measure the subjectivity (qualitative aspect) of the participants’ response to the dependent variable. Beyond quantitative analysis, augmentation with such a fuzzy module can provide clearer picture to analysts when analyzing the survey results. In this paper, Cloud acceptance survey will be used as a vehicle to provide step-by-step explanation of the proposed augmentation technique to unleash the hidden knowledge in similar cases to cloud computing long survey questionnaire where participants may change their mind at the end of the survey causing uncertainty represented in discrepancy of the collected data. The proposed technique would only be valid for long surveys like the presented Cloud computing acceptability where uncertainty in the data is inevitable. [ABSTRACT FROM AUTHOR]

With the prevalence of online social platforms, social recommendation has emerged as a promising direction that leverages the social network among users to enhance recommendation performance. However, the available social relations among users are usually extremely sparse and noisy, which may lead to inferior recommendation performance. To alleviate this problem, this paper novelly exploits the implicit higher-order social influence and dependencies among users to enhance social recommendation. In this paper, we propose a novel embedding method for general bipartite graphs, which defines inter-class message passing between explicit relations and intra-class message passing between implicit higher-order relations via a novel sequential modelling paradigm. Inspired by recent advances in self-attention-based sequential modelling, the proposed model features a self-attentive representation learning mechanism for implicit user-user relations. Moreover, this paper also explores the inductive embedding learning for social recommendation problems to improve the recommendation performance in cold-start settings. The proposed inductive learning paradigm for social recommendation enables embedding inference for those cold-start users and items (unseen during training) as long as they are linked to existing nodes in the original network. Extensive experiments on real-world datasets demonstrate the superiority of our method and suggest that higher-order implicit relationship among users is beneficial to improving social recommendation. [ABSTRACT FROM AUTHOR]

Visualization charts are widely utilized for presenting structured data. Under many circumstances, people want to digitalize the data in the charts collected from various sources (e.g., papers and websites), in oder to further analyze the data or create new charts. However, existing automatic and semi-automatic approaches are not always effective due to the variety of charts. In this paper, we introduce a crowdsourcing approach that leverages human ability to extract data from visualization charts. There are several challenges. The first is how to avoid tedious human interaction with charts and design effective crowdsourcing tasks. Second, it is challenging to evaluate worker’s quality for truth inference, because workers may not only provide inaccurate values but also misalign values to wrong data series. Third, to guarantee quality, one may assign a task to many workers, leading to a high crowdsourcing cost. To address these challenges, we design an effective crowdsourcing task scheme that splits a chart into simple micro-tasks. We introduce a novel worker quality model by considering worker’s accuracy and task difficulty. We also devise effective task assignment and early-termination mechanisms to save the cost. We evaluate our approach on real-world datasets on real crowdsourced platforms, and the results demonstrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

With the increasing of the data size and the development of multi-core computers, asynchronous parallel stochastic optimization algorithms such as KroMagnon have gained significant attention. In this paper, we propose a new Sparse approximation and asynchronous parallel Stochastic Variance Reduced Gradient (SSVRG) method for sparse and high-dimensional machine learning problems. Unlike standard SVRG and its asynchronous parallel variant, KroMagnon, the snapshot point of SSVRG is set to the average of all the iterates in the previous epoch, which allows it to take much larger learning rates and also makes it more robust to the choice of learning rates. In particular, we use the sparse approximation of the popular SVRG estimator to perform completely sparse updates at all iterations. Therefore, SSVRG has a much lower per-iteration computational cost than its dense counterpart, SVRG++, and is very friendly to asynchronous parallel implementation. Moreover, we provide the convergence guarantees of SSVRG for both strongly convex and non-strongly convex problems, while existing asynchronous algorithms (e.g., KroMagnon and ASAGA) only have convergence guarantees for strongly convex problems. Finally, we extend SSVRG to non-smooth and asynchronous parallel settings. Numerical experimental results demonstrate that SSVRG converges significantly faster than the state-of-the-art asynchronous parallel methods, e.g., KroMagnon, and is usually more than three orders of magnitude faster than SVRG++. [ABSTRACT FROM AUTHOR]

Heterogeneous graph embedding aims at learning low-dimensional representations from a graph featuring nodes and edges of diverse natures, and meanwhile preserving the underlying topology. Existing approaches along this line have largely relied on meta-paths, which are by nature hand-crafted and pre-defined transition rules, so as to explore the semantics of a graph. Despite the promising results, defining meta-paths requires domain knowledge, and thus when the test distribution deviates from the priors, such methods are prone to errors. In this paper, we propose a self-learning scheme for heterogeneous graph embedding, termed as self-guided walk (SILK), that bypasses meta-paths and learns adaptive attentions for node walking. SILK assumes no prior knowledge or annotation is provided, and conducts a customized random walk to encode the contexts of the heterogeneous graph of interest. Specifically, this is achieved via maintaining a dynamically-updated guidance matrix that records the node-conditioned transition potentials. Experimental results on four real-world datasets demonstrate that SILK significantly outperforms state-of-the-art methods. [ABSTRACT FROM AUTHOR]

While recent developments of neural network (NN) models have led to a series of record-breaking achievements in many applications, the lack of sufficiently good datasets remains a problem for some applications. For such a problem, we can however exploit a large number of unstructured text corpora as an external knowledge to complement the training data, and most prevailing neural network solutions employ word embedding methods for such purposes. In this paper, we propose LDA-Reg, a novel knowledge driven regularization framework based on Latent Dirichlet Allocation (LDA) as an alternative to the word embedding methods to adaptively utilize abundant external knowledge and to interpret the NN model. For the joint learning of the parameters, we propose EM-SGD, an effective update method which incorporates Expectation Maximization (EM) and Stochastic Gradient Descent (SGD) to update parameters iteratively. Moreover, we also devise a lazy update and sparse update method for the high-dimensional inputs and sparse inputs respectively. We validate the effectiveness of our regularization framework through an extensive experimental study over real world and standard benchmark datasets. The results show that our proposed framework not only achieves significant improvement over state-of-the-art word embedding methods but also learns interpretable and significant topics for various tasks. [ABSTRACT FROM AUTHOR]

Graph learning has emerged as a promising technique for multi-view clustering due to its efficiency of learning a unified graph from multiple views. Previous multi-view graph learning methods mainly try to exploit the multi-view consistency to boost learning performance. However, these methods ignore the prevalent multi-view diversity which may be induced by noise, corruptions, or even view-specific attributes. In this paper, we propose to simultaneously and explicitly leverage the multi-view consistency and the multi-view diversity in a unified framework. The consistent parts are further fused to our target graph with a clear clustering structure, on which the cluster label to each instance can be directly allocated without any postprocessing such as $k$ k -means in classical spectral clustering. In addition, our model can automatically assign suitable weight for each view based on its clustering capacity. By leveraging the subtasks of measuring the diversity of graphs, integrating the consistent parts with automatically learned weights, and allocating cluster label to each instance in a joint framework, each subtask can be alternately boosted by utilizing the results of the others towards an overall optimal solution. Extensive experimental results on several benchmark multi-view datasets demonstrate the effectiveness of our model in comparison to several state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Machine learning research, particularly in genomics, is often based on wide shaped datasets, i.e. datasets having a large number of features, but a small number of samples. Such configurations raise the possibility of chance influence (the increase of measured accuracy due to chance correlations) on the learning process and the evaluation results. Prior research underlined the problem of generalization of models obtained based on such data. In this paper, we investigate the influence of chance on prediction and show its significant effects on wide shaped datasets. First, we empirically demonstrate how significant the influence of chance in such datasets is by showing that prediction models trained on thousands of randomly generated datasets can achieve high accuracy. This is the case even when using cross-validation. We then provide a formal analysis of chance influence and design formal chance influence estimators based on the dataset parameters, namely its sample size, the number of features, the number of classes and the class distribution. Finally, we provide an in-depth discussion of the formal analysis including applications of the findings and recommendations on chance influence mitigation. [ABSTRACT FROM AUTHOR]

Twitter, a microblogging platform, has developed into an increasingly invaluable information source, where millions of users post a great quantity of tweets with various topics per day. Heterogeneous information networks consisting of multi-type objects and relations are becoming more and more prevalent as an organization form of knowledge and information. The task of linking an entity mention in a tweet with its corresponding entity in a heterogeneous information network is of great importance, for the purpose of enriching heterogeneous information networks with the abundant and fresh knowledge embedded in tweets. However, the entity mention is ambiguous. Additionally, tweets are short and informal, making it difficult to mine enough information from a single tweet for entity linking. In this paper, we propose an unsupervised iterative clustering framework TELHIN to link multiple similar tweets with a heterogeneous information network jointly. Our framework takes three dimensions of tweet similarity into consideration: (1) content similarity, (2) temporal similarity, and (3) user similarity. The appropriate weights of different similarity dimensions for each entity mention are learned iteratively based on the metric learning algorithm by leveraging the pairwise constraints generated automatically. Experiments on real data demonstrate the effectiveness of our framework in comparison with the baselines. [ABSTRACT FROM AUTHOR]

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ 2 × 2 bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage. [ABSTRACT FROM AUTHOR]

Competition between Points of Interest (POIs) refers to the situation in which two POIs directly or indirectly provide similar services to secure businesses. A large portion of prior studies on competition analysis focuses on mining textual data, e.g., news articles and social comments. However, the increasing availability of human mobility and mobile query data enables a new paradigm for analyzing the competitive relationships among POIs, which remains largely unexplored. To this end, in this paper, we attempt to mine large-scale online map search query data for better understanding POI competitive relationships. Based on a co-query POI graph built from the map search query data, we develop a novel neural graphlet-based prediction framework to predict the competitive relationships among POIs. A unique perspective of our model is to infer latent POI competitive relationships by integrating multiple distinct factors, e.g., graphlet structure, geographical distance, and regional features, reflected in map search query data and POI data. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness of the proposed framework, and show that our framework outperforms all baselines with a significant margin in all evaluation metrics. [ABSTRACT FROM AUTHOR]

The natural gas tightly correlates with our everyday life. However, driven by gray incomes, some users are prone to stealing gas by refitting the equipment without permission. Especially for the boiler room users in winter, this phenomenon appears more rampant. Traditional gas-theft detection methods highly rely on the on-site inspection, where exists ineffective and randomness. With the rapidly deployed IoT sensors, we can collect real-time gas consumption data to analyze users’ behavior patterns, where the gas-theft suspects could be discovered early and accurately. In this paper, we propose a data-driven approach, named SVOC, to detect gas-theft suspects among boiler room users. Our approach consists of a scenario-based data quality detection algorithm, a deformation-based normality detection algorithm, and an One-Class Support Vector Machine (OCSVM) based anomaly detection algorithm. Specifically, considering the temporal proximity between the gas consumption and the outdoor temperature, the normality detection algorithm adopts a similarity-based deformation correlation to detect normal boiler room users out of abnormal ones. Then, we employ OCSVM as the anomaly detection algorithm to capture various features across multiple data sources, aiming to distinguish gas-theft suspects from the remaining irregular users. Here, the detected normal and abnormal users are fed into the OCSVM for training and prediction, respectively, which can overcome the label scarcity problem. We conduct extensive experiments on a real-world dataset during one heating season. The results demonstrate distinct advantages of our approach over various baselines. We have developed a real-time system on the cloud, providing daily gas-theft suspects for gas companies. [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]

Broad learning system (BLS) is a novel and efficient model, which facilitates representation learning and classification by concatenating feature nodes and enhancement nodes. In spite of the efficient properties, BLS is still suboptimal when facing with imbalance problem. Besides, outliers and noises in imbalanced data remain a challenge for BLS. To address the above issues, in this paper we first propose a weighted BLS, which assigns a weight to each training sample, and adopt a general weighting scheme, which augments the weight of samples from the minority class. To further explore the prior distribution of original data, we design a density based weight generation mechanism to guide the specific weight matrix generation and propose the adaptive weighted broad learning system (AWBLS). This mechanism considers the inter-class and intra-class distance simultaneously in the density calculation. Finally, we propose the incremental weighted ensemble broad learning system (IWEB) by utilizing a progressive mechanism to further improve the stability and robustness of AWBLS. Extensive comparative experiments on 38 real-world data sets verfy that IWEB outperforms most of the imbalance ensemble classification methods. [ABSTRACT FROM AUTHOR]

In plenty of real-life tasks, strongly supervised information is hard to obtain, and thus weakly supervised learning has drawn considerable attention recently. This paper investigates the problem of learning from incomplete and inaccurate supervision, where only a limited subset of training data is labeled but potentially with noise. This setting is challenging and of great importance but rarely studied in the literature. We notice that in many applications, the limited labeled data are with certain structures, which paves us a way to design effective methods. Specifically, we observe that labeled data are usually with one-sided noise such as the bug detection task, where the identified buggy codes are indeed with defects, while codes checked many times or newly fixed may still have other flaws. Furthermore, when there occurs two-sided noise in the labeled data, we exploit the class-prior information of unlabeled data, which is typically available in practical tasks. We propose novel approaches for the incomplete and inaccurate supervision learning tasks and effectively alleviate the negative influence of label noise with the help of a vast number of unlabeled data. Both theoretical analysis and extensive experiments justify and validate the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

Knowledge graph embedding is an effective way to represent knowledge graph, which greatly enhance the performances on knowledge graph completion tasks, e.g., entity or relation prediction. For knowledge graph embedding models, designing a powerful loss framework is crucial to the discrimination between correct and incorrect triplets. Margin-based ranking loss is a commonly used negative sampling framework to make a suitable margin between the scores of positive and negative triples. However, this loss can not ensure ideal low scores for the positive triplets and high scores for the negative triplets, which is not beneficial for knowledge completion tasks. In this paper, we present a double limit scoring loss to separately set upper bound for correct triplets and lower bound for incorrect triplets, which provides more effective and flexible optimization for knowledge graph embedding. Upon the presented loss framework, we present several knowledge graph embedding models including TransE-SS, TransH-SS, TransD-SS, ProjE-SS and ComplEx-SS. The experimental results on link prediction and triplet classification show that our proposed models have the significant improvement compared to state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Currently, electroencephalogram (EEG) is mostly analyzed in a supervised way, which requires EEG labels (e.g., EEG classification). With the ever-increasing amount of unlabeled/mislabeled EEG in neuropsychiatric disorder diagnosis, BCI, and rehabilitation, manually labeling of EEG data is a labor intensive and time-consuming process, and few labs have developed algorithms to analyze EEG in an unsupervised manner (i.e., EEG clustering). In this paper, we propose a cooperative game inspired approach to cluster multi-trial EEG data. The idea is to map multi-trial EEG clustering to the coalition formation in a cooperative game, and then identify cluster center (the EEG trial with highest Shapley value) and assign EEG trials into proper clusters based on their cross correlation-transformed Shapley values. We demonstrate the mapped EEG cooperative game is convex, and it leads to an algorithm for multi-trial EEG clustering named CoGEEGc. The CoGEEGc yields high-quality multi-trial EEG clustering with respect to intra-cluster compactness and inter-cluster scatter. We show that CoGEEGc outperforms 15 state-of-the-art EEG or time series clustering approaches through detailed experimentation on real-world multi-trial EEG datasets. Comparison against 15 methods with four theoretical properties of clustering further illustrates the superiority of CoGEEGc, as it satisfies two properties while other approaches only satisfy one. [ABSTRACT FROM AUTHOR]

It is widely acknowledged that the success of deep learning is built upon large-scale training data and tremendous computing power. However, the data and computing power are not always available for many real-world applications. In this paper, we address the machine learning problem where it lacks training data and limits computing power. Specifically, we investigate domain adaptation which is able to transfer knowledge from one labeled source domain to an unlabeled target domain, so that we do not need much training data from the target domain. At the same time, we consider the situation that the running environment is confined, e.g., in edge computing the end device has very limited running resources. Technically, we present the Faster Domain Adaptation (FDA) protocol and further report two paradigms of FDA: early stopping and amid skipping. The former accelerates domain adaptation by multiple early exit points. The latter speeds up the adaptation by wisely skip several amid neural network blocks. Extensive experiments on standard benchmarks verify that our method is able to achieve the comparable and even better accuracy but employ much less computing resources. To the best of our knowledge, there are very few works which investigated accelerating knowledge adaptation in the community. This work is expected to inspire the topic for more discussion. [ABSTRACT FROM AUTHOR]

Spatial co-location pattern mining (SCPM) aims to discover subsets of spatial features frequently located together in proximate areas. Previous studies of SCPM solely concern the inter-features association of a pattern, but neglect the interesting intra-feature behavior. In this paper, we propose the task of spatial co-location pattern mining with coupling relation consideration (SCPM-CR) to capture complex relations embedded in a co-location. Specifically, InterPCI measure is designed to capture the inter-features coupling by considering the comprehensive interaction of objects for the features in a pattern, and luckily it possesses the anti-monotone property. Another measure, IntraCAI, is proposed to capture the congregating behavior of intra-feature objects under the restriction of a co-location. A general framework is designed for SCPM-CR task and experiments show that a large fraction of computation time is devoted to identifying the participating objects of a candidate pattern. To tackle this calculation bottleneck, a novel candidate-and-search algorithm is suggested, CS-HBS, equipped with heuristic backtracking search. Extensive experiments are conducted on real and synthetic datasets to demonstrate the superiority of SCPM-CR compared with traditional SCPM methods, and also to validate the efficiency and scalability of CS-HBS. Experimental results show that CS-HBS outperforms the baselines by several times or even orders of magnitude. [ABSTRACT FROM AUTHOR]

Domain adaptation aims at extracting knowledge from auxiliary source domains to assist the learning task in a target domain. In classification problems, since the distributions of the source and target domains are different, directly using source data to build a classifier for the target domain may hamper the classification performance on the target data. Fortunately, in many tasks, there can be some features that are transferable, i.e., the source and target domains share similar properties. On the other hand, it is common that the source data contain noisy features which may degrade the learning performance in the target domain. This issue, however, is barely studied in existing works. In this paper, we propose to find a feature subset that is transferable across the source and target domains. As a result, the domain discrepancy measured on the selected features can be reduced. Moreover, we seek to find the most discriminative features for classification. To achieve the above goals, we formulate a new sparse learning model that is able to jointly reduce the domain discrepancy and select informative features for classification. We develop two optimization algorithms to address the derived learning problem. Extensive experiments on real-world data sets demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Although the emergence of the programmable smart contract makes blockchain systems easily embrace a wide range of industrial services, how to execute smart contracts efficiently becomes a big challenge nowadays. Due to the existence of Byzantine nodes, existing mature concurrency control protocols in database cannot be employed directly, since the mechanism of executing smart contracts varies a lot. Furthermore, even though smart contract execution follows a two-phase style, i.e., the primary node executes a batch of smart contracts in the first phase and the validators replay them in the second phase, existing parallel solutions merely focus on the optimization for the first phase, rather than the second phase. In this paper, we propose a novel two-phase concurrency control protocol to optimize both phases for the first time. First, the primary executes transactions in parallel and generates a transaction dependency graph with high parallelism for validators. Then, a graph partition algorithm is devised to divide the original graph into several sub-graphs to preserve parallelism and reduce communication cost remarkably. Finally, we propose a deterministic replay protocol to re-execute the primary’s parallel schedule concurrently. Moreover, this two-phase protocol is further optimized by integrating with PBFT. Theoretical analysis and extensive experimental results illustrate that the proposed scheme outperforms state-of-art solutions significantly. [ABSTRACT FROM AUTHOR]

Many modern navigation systems and map-based services do not only provide the fastest route from a source location $s$ s to a target location $t$ t but also provide a few alternative routes to the users as more options to choose from. Consequently, computing alternative paths has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen that compares the quality (as perceived by the users) of the alternative routes generated by four of the most popular existing approaches including the routes provided by Google Maps. We also present a web-based demo system that can be accessed using any internet-enabled device and allows users to see the alternative routes generated by the four approaches for any pair of selected source and target. We report the average ratings received by the four approaches and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers to interpret these results with caution because certain factors may have affected the participants’ ratings. [ABSTRACT FROM AUTHOR]

The task of point of interest (POI) recommendation aims to recommend unvisited places to users based on their check-in history. A major challenge in POI recommendation is data sparsity, because a user typically visits only a very small number of POIs among all available POIs. In this paper, we propose AUC-MF to address the POI recommendation problem by maximizing Area Under the ROC curve (AUC). AUC has been widely used for measuring classification performance with imbalanced data distributions. To optimize AUC, we transform the recommendation task to a classification problem, where the visited locations are positive examples and the unvisited are negative ones. We define a new lambda for AUC to utilize the LambdaMF model, which combines the lambda-based method and matrix factorization model in collaborative filtering. Many studies have shown that geographic information plays an important role in POI recommendation. In this study, we focus on two levels geographic information: local similarity and global similarity. We further show that AUC-MF can be easily extended to incorporate geographical contextual information for POI recommendation. Specifically, we propose two novel methods to incorporate geographical information in AUC-MF. Different from most existing models where the contextual information are incorporated into the objective function, the incorporation of contextual information in AUC-MF is a refinement of the model and a sampling strategy. The sampling strategy could speedup convergence and the refining of recommendations is independent of training of the model. This mechanism also enables AUC-MF to be able produce recommendations refined towards different contextual information, with minimum computational cost. Experiments on two datasets show that the proposed AUC-MF outperforms state-of-the-art methods significantly in terms of recommendation accuracy. [ABSTRACT FROM AUTHOR]

With the increasing accumulation of spatial-temporal trajectory data, location-based data mining has recently been extensively studied. A fundamental research topic in this field is learning the embedding vectors of locations through self-supervised pre-training. Pre-trained embedding vectors can utilize the highly available unlabeled trajectory data, and benefit downstream tasks in multiple aspects. However, most existing methods ignore the temporal information hidden in the visited time of locations in trajectories. Considering that human activities are highly regulated by specific periods of a day, temporal information can reflect some intrinsic characteristics of locations, so it is necessary to fuse them into location embedding vectors. In this paper, we propose a Time-Aware Location Embedding (TALE) pre-training method based on the CBOW framework, which is able to incorporate temporal information into the learned embedding vectors of locations. A novel temporal tree structure is designed to extract temporal information during the calculation of Hierarchical Softmax. In order to verify the effectiveness of TALE, we apply the learned embedding vectors into three downstream location-based prediction tasks, i.e., location classification, location visitor flow prediction and user next location prediction. Experiments are conducted on four real-world user trajectory datasets, and the experimental results demonstrate that our TALE model can obviously help downstream tasks gain better performance. [ABSTRACT FROM AUTHOR]

Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage. [ABSTRACT FROM AUTHOR]

In this work we study the distance distribution computation problem. It has been widely used in many real-world applications, e.g., human genome clustering, cosmological model analysis, and parameter tuning. The straightforward solution for the exact distance distribution computation problem is unacceptably slow due to (i) massive data size, and (ii) expensive distance computation. In this paper, we propose a novel method to compute approximate distance distributions with error bound guarantees. Furthermore, our method is generic to different distance measures. We conduct extensive experimental studies on three widely used distance measures with real-world datasets. The experimental results demonstrate that our proposed method outperforms the sampling-based solution (without error guarantees) by up to three orders of magnitude. [ABSTRACT FROM AUTHOR]

Accurate traffic forecasting is critical in improving safety, stability, and efficiency of intelligent transportation systems. Despite years of studies, accurate traffic prediction still faces the following challenges, including modeling the dynamics of traffic data along both temporal and spatial dimensions, and capturing the periodicity and the spatial heterogeneity of traffic data, and the problem is more difficult for long-term forecast. In this paper, we propose an Attention based Spatial-Temporal Graph Neural Network (ASTGNN) for traffic forecasting. Specifically, in the temporal dimension, we design a novel self-attention mechanism that is capable of utilizing the local context, which is specialized for numerical sequence representation transformation. It enables our prediction model to capture the temporal dynamics of traffic data and to enjoy global receptive fields that is beneficial for long-term forecast. In the spatial dimension, we develop a dynamic graph convolution module, employing self-attention to capture the spatial correlations in a dynamic manner. Furthermore, we explicitly model the periodicity and capture the spatial heterogeneity through embedding modules. Experiments on five real-world traffic flow datasets demonstrate that ASTGNN outperforms the state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Spatial crowdsourcing (SC) allows requesters to crowdsource tasks to workers based on location proximity. To preserve privacy, the location should not be disclosed to untrustworthy entities (even the SC platform). Previous solutions to preserve workers’ location privacy require an online trusty third party (TTP), which is not practical in reality. In this paper, we design a framework that allows the SC platform to assign tasks to nearest workers in an online manner without knowing their actual locations. We propose an encryption algorithm to encrypt the locations of tasks and workers, and design an indexing method that assigns tasks to workers without losing too much privacy. We prove that there exists a trade-off between efficiency and security theoretically, which can be controlled based on user preference. We verify our method on real-world datasets and experimental results show that our method is efficient, effective and practical. [ABSTRACT FROM AUTHOR]

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called “non-FIFO steams”. This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called $CPiX$ C P i X , for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner per checkpoint. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory. [ABSTRACT FROM AUTHOR]