Search

Subgraph queries are routinely used to search for entities in richly attributed graphs e.g., social networks and knowledge graphs. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to clarify missing or unexpected query results. This paper makes a first step to answer Why-questions for entity search in attributed graphs. We consider three common types of Why-questions: Why-not, Why, and Why-rank, which suggest query manipulations that are responsible for user-specified missing, unexpected, and undesirably ranked entities, respectively. (1) We approach a general query rewriting paradigm that suggests to identify desired entities that are specified by Why-questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrites is intractable, we develop feasible algorithms, from approximation to fast heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for Why, Why-not and Why-rank questions. We further show that our results remain intact for Why questions that (1) request a single query rewrite to clarify multiple types of entities, and (2) variants such as Why-empty and Why-so-many, by providing the matching algorithms. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration. [ABSTRACT FROM AUTHOR]

Static and dynamic clustering algorithms are a fundamental tool in any machine learning library. Most of the efforts in developing dynamic machine learning and data mining algorithms have been focusing on the sliding window model or more simplistic models. However, in many real-world applications one might need to deal with arbitrary deletions and insertions. For example, one might need to remove data items that are not necessarily the oldest ones, because they have been flagged as containing inappropriate content or due to privacy concerns. Clustering trajectory data might also require to deal with more general update operations. We develop a $(2+\epsilon)$ (2 + ε) -approximation algorithm for the $k$ k -center clustering problem with “small” amortized cost under the fully dynamic adversarial model. In such a model, points can be added or removed arbitrarily, provided that the adversary does not have access to the random choices of our algorithm. The amortized cost of our algorithm is poly-logarithmic when the ratio between the maximum and minimum distance between any two points in input is bounded by a polynomial, while $k$ k and $\epsilon$ ε are constant. Furthermore, we significantly improve the memory requirement of our fully dynamic algorithm, although at the cost of a worse approximation ratio of $4 +\epsilon$ 4 + ε . Our theoretical results are complemented with an extensive experimental evaluation on dynamic data from Twitter, Flickr, as well as trajectory data, demonstrating the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets: Zigzag that considers the 1-N shared computation; Co-Clustering that considers the source and target's spatial locality; and Search-Space-Aware that further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: R2R that finds a set of approximate shortest paths from one region to another with bounded error; and Local Cache that improves the existing Global Cache with higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms. [ABSTRACT FROM AUTHOR]

The maximum clique problem (MCP) has various applications to reveal the structure and function of graphs. Graphs are constantly updated in the real life. However, no algorithm is specifically designed for dynamic graph. Although MCP in dynamic graphs can be solved by simply invoking a state-of-the-art static approach, such as PMC, when the graph is updated, such an approach of simply re-calculating from scratch is inefficient. The key issue with MCP algorithm is to find a large clique, namely a seed, as fast as possible. Thus, search space can be pruned based on the seed. Size of the seed greedily found by PMC cannot be guaranteed, as it fluctuates considerably. Moreover, the time required to find a seed under PMC is up to $O(| E| \cdot \Delta (G))$ O (| E | · Δ (G)) , where $\Delta (G)$ Δ (G) is the highest degree in G. In this article, we intend to find a sizable seed by updating the previous maximum clique with the incident vertices of the inserted/deleted edge. Size of the seed now is guaranteed to be no less than $\omega (G^{\prime})\; - \;1$ ω (G ') - 1 , where $\omega (G^{\prime})$ ω (G ') is the size of the maximum clique on the updated graph. Moreover, the seed can be found in a time complexity of $O(\Delta (G)^{2})$ O (Δ (G) 2) . Two other crucial issues related to the MCP in dynamic graphs are refreshing rate and refreshing overhead. After a tight upper bound is imposed on $\omega (G^{\prime})$ ω (G ') , the necessity of refreshing is evaluated by comparing the seed with its largest challenger, then unnecessary refreshing is wiped out effectively. The size of the largest challenger is judiciously estimated using a lazy growth strategy. Subsequently, the search space in refreshing is confined on a much smaller subgraph using a local refreshing strategy. Extensive experiments indicate that the proposed approach outperforms the baseline algorithm by approximately one order of magnitude. [ABSTRACT FROM AUTHOR]

The $K$ K -means algorithm is one of the most popular clustering methods. However, it is a well-known fact that its performance, in terms of quality of the obtained solution and computational load, highly depends upon its initialization phase. For this reason, different initialization techniques have been developed throughout the years to enable its fast convergence to competitive solutions. In this sense, it is common practice to re-start the $K$ K -means algorithm several times via one of these techniques and keep the solution with the lowest error. Unfortunately, such a choice is still likely to be a poor approximation of the optimal set of centroids. In this article, we introduce a cheap Split-Merge step that can be used to re-start the $K$ K -means algorithm after reaching a fixed point. Under some settings, one can show that this approach reduces the error of the given fixed point without requiring any further iteration of the $K$ K -means algorithm. Moreover, experimental results show that this strategy is able to generate approximations with an associated error that is hard to reach for different multi-start methods, such as multi-start Forgy $K$ K -means, $K$ K -means++ and Hartigan $K$ K -means, while also computing a lower amount of distances than the previous algorithms. [ABSTRACT FROM AUTHOR]

Feature reduction is an important aspect of Big Data analytics on today’s ever-larger datasets. Rough sets are a classical method widely applied in attribute reduction. Most rough set algorithms use the priori domain knowledge of a dataset to process continuous attributes through using a membership function. Neighborhood rough sets (NRS) replace the membership function with the concept of neighborhoods, allowing NRS to handle scenarios where no a priori knowledge is available. However, the neighborhood radius of each object in NRS is fixed, and the optimization of the radius depends on grid searching. This diminishes both the efficiency and effectiveness, leading to a time complexity of not lower than $O(N^2)$ O (N 2) . To resolve these limitations, granular ball neighborhood rough sets (GBNRS), a novel NRS method with time complexity $O(N)$ O (N) , is proposed. GBNRS adaptively generates a different neighborhood for each object, resulting in greater generality and flexibility in comparison to standard NRS methods. GBNRS is compared with the current state-of-the-art NRS method, FARNeMF, and find that GBNRS obtains both higher performance and higher classification accuracy on public benchmark datasets. All code has been released in the open source GBNRS library at http://www.cquptshuyinxia.com/GBNRS.html. [ABSTRACT FROM AUTHOR]

We suggest a new optimization technique for minimizing the sum $\sum _{i=1}^n g_i(x)$ ∑ i = 1 n g i (x) of $n$ n non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in $n$ n for the fundamental problem of Points-to-Lines alignment: Given $n$ n points $p_1,\ldots,p_n$ p 1 ,... , p n and $n$ n lines $\ell _1,\ldots,\ell _n$ ℓ 1 ,... , ℓ n on the plane and $z>0$ z > 0 , compute the matching $\pi :[n]\to [n]$ π : [ n ] → [ n ] and alignment (rotation matrix $R$ R and translation vector $t$ t ) that minimize the sum of euclidean distances $\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$ ∑ i = 1 n dist (R p i - t , ℓ π (i)) z between each point to its corresponding line. This problem is non-trivial even if $z=1$ z = 1 and the matching $\pi$ π is given. If $\pi$ π is given, our algorithms run in $O(n^3)$ O (n 3) time, and even near-linear in $n$ n using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g., outliers or pseudo-distances such as $M$ M -estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems. [ABSTRACT FROM AUTHOR]

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of “semi-connection” that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions. [ABSTRACT FROM AUTHOR]

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizes Ann by introducing an extra flexibility parameter $\phi$ ϕ that ranges in $(0, 1]$ (0 , 1 ] . In this article, we focus on Fann on road networks, denoted as Fann $_\mathcal {R}$ R , and its keyword-aware variant, denoted as KFann $_\mathcal {R}$ R . To solve these problems, we propose a series of universal (i.e., suitable for both max and sum) algorithms, including a Dijkstra-based algorithm that enumerates $P$ P instead of $\phi |Q|$ ϕ | Q | -combinations of $Q$ Q , a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and $k$ k NN. We also propose a specific exact solution to max-Fann $_\mathcal {R}$ R and a constant-factor ratio approximate solution to sum-Fann $_\mathcal {R}$ R . These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top- $k$ k and multiple Fann $_\mathcal {R}$ R (resp., KFann $_\mathcal {R}$ R ) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality. [ABSTRACT FROM AUTHOR]

Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to the unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

This paper revisits the classical problem of multiple query optimization in federated RDF systems. We propose a heuristic query rewriting-based approach to optimize the evaluation of multiple queries. This approach can take advantage of SPARQL 1.1 to share the common computation of multiple queries while considering the cost of both query evaluation and data shipment. Although we prove that finding the optimal rewriting for multiple queries is NP-complete, we propose a heuristic rewriting algorithm with a bounded approximation ratio. Furthermore, we propose an efficient method to use the interconnection topology between RDF sources to filter out irrelevant sources, and utilize some characteristics of SPARQL 1.1 to optimize multiple joins of intermediate matches. The extensive experimental studies show that the proposed techniques are effective, efficient and scalable. [ABSTRACT FROM AUTHOR]

Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to $k$ k th-order Voronoi diagram commonly used to facilitate $k$ k nearest neighbor ($k$ k NN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. In addition, we propose an approximate skyline diagram which can significantly reduce the space cost. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable. [ABSTRACT FROM AUTHOR]

Nearest neighbor searching systems are an integral part of many online applications, including but not limited to pattern recognition, plagiarism detection, and recommender systems. With increasingly larger data sets, scalability has become an important issue. Many of the most space and running time efficient algorithms are based on locality-sensitive hashing. Here, we view the data set as an $n$ n by $|U|$ | U | matrix where each row corresponds to one of $n$ n users and the columns correspond to items drawn from a universe $U$ U . The de-facto standard approach to quickly answer nearest neighbor queries on such a data set is usually a form of min-hashing. Not only is min-hashing very fast, but it is also space efficient and can be implemented in many computational models aimed at dealing with large data sets such as MapReduce and streaming. However, a significant drawback is that minhashing and related methods are only able to handle insertions to user profiles and tend to perform poorly when items may be removed. We initiate the study of scalable locality-sensitive hashing (LSH) for fully dynamic data-streams. Specifically, using the Jaccard index as similarity measure, we design (1) a collaborative filtering mechanism maintainable in dynamic data streams and (2) a sketching algorithm for similarity estimation. Our algorithms have little overhead in terms of running time compared to previous LSH approaches for the insertion only case, and drastically outperform previous algorithms in case of deletions. [ABSTRACT FROM AUTHOR]

Cyber-epidemics, the widespread of fake news or propaganda through social media, can cause devastating economic and political consequences. A common countermeasure against cyber-epidemics is to disable a small subset of suspected social connections or accounts to effectively contain the epidemics. An example is the recent shutdown of 125,000 ISIS-related Twitter accounts. Despite many proposed methods to identify such a subset, none are scalable enough to provide high-quality solutions in nowadays’ billion-size networks. To this end, we investigate the Spread Interdiction problems that seek the most effective links (or nodes) for removal under the well-known Linear Threshold model. We propose novel CPU-GPU methods that scale to networks with billions of edges, yet possess rigorous theoretical guarantee on the solution quality. At the core of our methods is an $O(1)$ O (1) -space out-of-core algorithm to generate a new type of random walks, called Hitting Self-avoiding Walks ($\mathsf{HSAW}$ HSAW s). Such a low memory requirement enables handling of big networks and, more importantly, hiding latency via scheduling of millions of threads on GPUs. Comprehensive experiments on real-world networks show that our algorithms provide much higher quality solutions and are several orders of magnitude faster than the state-of-the art. Comparing to the (single-core) CPU counterpart, our GPU implementations achieve significant speedup factors up to 177x on a single GPU and 338x on a GPU pair. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights regularly vary with timestamps. However, finding dense subgraphs in temporal networks is non-trivial, and its state of the art solution uses a filter-and-verification framework that is not scalable on large temporal networks. In this study, we propose a highly efficient approach to finding dense subgraphs in large temporal networks with $T$ T timestamps. (1) We first develop a statistics-driven approach that employs hidden statistics to identifying $k$ k time intervals, instead of $T(T+1)/2$ T (T + 1) / 2 ones ($k$ k is typically much smaller than $T$ T ), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by connecting finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to verify that our approach is both effective and efficient. [ABSTRACT FROM AUTHOR]

The structural graph clustering algorithm SCAN is a fundamental technique for managing and analyzing graph data. However, its high runtime remains a computational bottleneck, which limits its applicability. In this paper, we propose a novel interactive approach for tackling this problem on multicore CPUs. Our algorithm, called anySCAN, iteratively processes vertices in blocks. The acquired results are merged into an underlying cluster structure consisting of the so-called super-nodes for building clusters. During its runtime, anySCAN can be suspended for examining intermediate results and resumed for finding better results at arbitrary time points, making it an anytime algorithm which is capable of handling very large graphs in an interactive way and under arbitrary time constraints. Moreover, its block processing scheme allows the design of a scalable parallel algorithm on shared memory architectures such as multicore CPUs for speeding up the algorithm further at each iteration. Consequently, anySCAN uniquely is a both interactive and work-efficient parallel algorithm. We further introduce danySCAN an efficient bulk update scheme for anySCAN on dynamic graphs in which the clusters are updated in bulks and in a parallel interactive scheme. Experiments are conducted on very large real graph datasets for demonstrating the performance of anySCAN. They show its ability to acquire very good approximate results early, leading to orders of magnitude speedup compared to SCAN and its variants. Moreover, it scales very well with the number of threads when dealing with both static and dynamic graphs. [ABSTRACT FROM AUTHOR]

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the "diminishing returns" property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general $d$d-knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes the KnapStream algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is $\frac{1-\varepsilon }{1+d}$1-ɛ1+d-approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework (KW$^{+}$+) to improve upon KW. KW$^{+}$+ builds an index SubKnapChk to manage the checkpoints and KS instances. SubKnapChk deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW$^{+}$+ achieves higher efficiency than KW while still guaranteeing a $\frac{1-\varepsilon ^{\prime }}{2+2d}$1-ɛ'2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW$^{+}$+ in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW$^{+}$+ further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities. [ABSTRACT FROM AUTHOR]

The issue of missing values (MVs) has appeared widely in real-world datasets and hindered the use of many statistical or machine learning algorithms for data analytics due to their incompetence in handling incomplete datasets. To address this issue, several MV imputation algorithms have been developed. However, these approaches do not perform well when most of the incomplete tuples are clustered with each other, coined here as theClustered Missing Values Phenomenon, which attributes to the lack of sufficient complete tuples near an MV for imputation. In this paper, we propose theOrder-Sensitive Imputation for Clustered Missing values(OSICM) framework, in which missing values are imputed sequentially such that the values filled earlier in the process are also used for later imputation of other MVs. Obviously, the order of imputations is critical to the effectiveness and efficiency of OSICM framework. We formulate the searching of the optimal imputation order as an optimization problem, and show its NP-hardness. Furthermore, we devise an algorithm to find the exact optimal solution and propose two approximate/heuristic algorithms to trade off effectiveness for efficiency. Finally, we conduct extensive experiments on real and synthetic datasets to demonstrate the superiority of our OSICM framework. [ABSTRACT FROM AUTHOR]

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find for a given query consisting a query location and several query keywords a set of objects which covers the query keywords collectively and has the smallest cost wrt the query location. In the literature, many different functions were proposed for defining the ${cost}$ and correspondingly, many different approaches were developed for the CoSKQ problem. In this paper, we study the CoSKQ problem systematically by proposing a unified cost function and a unified approach for the CoSKQ problem (with the unified cost function). The unified cost function includes all existing cost functions as special cases and the unified approach solves the CoSKQ problem with the unified cost function in a unified way. Experiments were conducted on both real and synthetic datasets which verified our proposed approach. [ABSTRACT FROM AUTHOR]

Crowdsourcing has been shown to be effective in a wide range of applications, and is seeing increasing use. A large-scale crowdsourcing task often consists of thousands or millions of atomic tasks, each of which is usually a simple task such as binary choice or simple voting. To distribute a large-scale crowdsourcing task to limited crowd workers, a common practice is to pack a set of atomic tasks into a task bin and send to a crowd worker in a batch. It is challenging to decompose a large-scale crowdsourcing task and execute batches of atomic tasks, which ensures reliable answers at a minimal total cost. Large batches lead to unreliable answers of atomic tasks, while small batches incur unnecessary cost. In this paper, we investigate a general crowdsourcing task decomposition problem, called the Smart Large-scAle task DE composer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove the NP-hardness of the SLADE problem and propose solutions in both homogeneous and heterogeneous scenarios. For the homogeneous SLADE problem, where all the atomic tasks share the same reliability requirement, we propose a greedy heuristic algorithm and an efficient and effective approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, where the atomic tasks can have different reliability requirements, we extend the OPQ-based framework leveraging a partition strategy, and also prove its approximation guarantee. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments on representative crowdsourcing platforms. [ABSTRACT FROM AUTHOR]

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (\sf CRS ), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures. [ABSTRACT FROM PUBLISHER]

As both social network structure and strength of influence between individuals evolve constantly, it requires tracking the influential nodes under a dynamic setting. To address this problem, we explore the Influential Node Tracking (INT) problem as an extension to the traditional Influence Maximization problem (IM) under dynamic social networks. While the Influence Maximization problem aims at identifying a set of $k$ nodes to maximize the joint influence under one static network, the INT problem focuses on tracking a set of influential nodes that keeps maximizing the influence as the network evolves. Utilizing the smoothness of the evolution of the network structure, we propose an efficient algorithm, Upper Bound Interchange Greedy (UBI) and a variant, UBI+. Instead of constructing the seed set from the ground, we start from the influential seed set we found previously and implement node replacement to improve the influence coverage. Furthermore, by using a fast update method by calculating the marginal gain of nodes, our algorithm can scale to dynamic social networks with millions of nodes. Empirical experiments on three real large-scale dynamic social networks show that our UBI and its variants, UBI+ achieves better performance in terms of both influence coverage and running time. [ABSTRACT FROM AUTHOR]

In this paper, we study a new problem of continuous learning from doubly-streaming data where both data volume and feature space increase over time. We refer to the doubly-streaming data as trapezoidal data streams and the corresponding learning problem as online learning from trapezoidal data streams. The problem is challenging because both data volume and data dimension increase over time, and existing online learning [1] , [2] , online feature selection [3] , and streaming feature selection algorithms [4] , [5] are inapplicable. We propose a new Online Learning with Streaming Features algorithm (OLSF for short) and its two variants, which combine online learning [1] , [2] and streaming feature selection [4] , [5] to enable learning from trapezoidal data streams with infinite training instances and features. When a new training instance carrying new features arrives, a classifier updates the existing features by following the passive-aggressive update rule [2] and updates the new features by following the structural risk minimization principle. Feature sparsity is then introduced by using the projected truncation technique. We derive performance bounds of the OLSF algorithm and its variants. We also conduct experiments on real-world data sets to show the performance of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates. [ABSTRACT FROM AUTHOR]

Graph datasets with billions of edges, such as social and web graphs, are prevalent, and scalability is critical. All-distances sketches (ADS) [Cohen 1997], are a powerful tool for scalable approximation of statistics. The sketch is a small size sample of the distance relation of a node which emphasizes closer nodes. Sketches for all nodes are computed using a nearly linear computation and estimators are applied to sketches of nodes to estimate their properties. We provide, for the first time, a unified exposition of ADS algorithms and applications. We present the historic inverse probability (HIP) estimators which are applied to the ADS of a node to estimate a large natural class of statistics. For the important special cases of neighborhood cardinalities (the number of nodes within some query distance) and closeness centralities, HIP estimators have at most half the variance of previous estimators and we show that this is essentially optimal. Moreover, HIP obtains a polynomial improvement for more general statistics and the estimators are simple, flexible, unbiased, and elegant. For approximate distinct counting on data streams, HIP outperforms the original estimators for the HyperLogLog MinHash sketches (Flajolet et al. 2007), obtaining significantly improved estimation quality for this state-of-the-art practical algorithm. [ABSTRACT FROM AUTHOR]

Rule induction method based on rough set theory (RST) has received much attention recently since it may generate a minimal set of rules from the decision system for real-life applications by using of attribute reduction and approximations. The decision system may vary with time, e.g., the variation of objects, attributes and attribute values. The reduction and approximations of the decision system may alter on Attribute Values’ Coarsening and Refining (AVCR), a kind of variation of attribute values, which results in the alteration of decision rules simultaneously. This paper aims for dynamic maintenance of decision rules $w.r.t.$ AVCR. The definition of minimal discernibility attribute set is proposed firstly, which aims to improve the efficiency of attribute reduction in RST. Then, principles of updating decision rules in case of AVCR are discussed. Furthermore, the rough set-based methods for updating decision rules in the inconsistent decision system are proposed. The complexity analysis and extensive experiments on UCI data sets have verified the effectiveness and efficiency of the proposed methods. [ABSTRACT FROM PUBLISHER]

The multiple longest common subsequence (MLCS) problem, related to the identification of sequence similarity, is an important problem in many fields. As an NP-hard problem, its exact algorithms have difficulty in handling large-scale data and time- and space-efficient algorithms are required in real-world applications. To deal with time constraints, anytime algorithms have been proposed to generate good solutions with a reasonable time. However, there exists little work on space-efficient MLCS algorithms. In this paper, we formulate the MLCS problem into a graph search problem and present two space-efficient anytime MLCS algorithms, SA-MLCS and SLA-MLCS. SA-MLCS uses an iterative beam widening search strategy to reduce space usage during the iterative process of finding better solutions. Based on SA-MLCS, SLA-MLCS, a space-bounded algorithm, is developed to avoid space usage from exceeding available memory. SLA-MLCS uses a replacing strategy when SA-MLCS reaches a given space bound. Experimental results show SA-MLCS and SLA-MLCS use an order of magnitude less space and time than the state-of-the-art approximate algorithm MLCS-APP while finding better solutions. Compared to the state-of-the-art anytime algorithm Pro-MLCS, SA-MLCS and SLA-MLCS can solve an order of magnitude larger size instances. Furthermore, SLA-MLCS can find much better solutions than SA-MLCS on large size instances. [ABSTRACT FROM AUTHOR]

Result diversification has recently attracted considerable attention as a means of increasing user satisfaction in recommender systems, as well as in web and database search. In this paper, we focus on the problem of selecting the $k$ -most diverse items from a result set. Whereas previous research has mainly considered the static version of the problem, in this paper, we exploit the dynamic case in which the result set changes over time, as for example, in the case of notification services. We define the CONTINUOUS $k$ -DIVERSITY PROBLEM along with appropriate constraints that enforce continuity requirements on the diversified results. Our proposed approach is based on cover trees and supports dynamic item insertion and deletion. The diversification problem is in general NP-hard; we provide theoretical bounds that characterize the quality of our cover tree solution with respect to the optimal one. Since results are often associated with a relevance score, we extend our approach to account for relevance. Finally, we report experimental results concerning the efficiency and effectiveness of our approach on a variety of real and synthetic datasets. [ABSTRACT FROM PUBLISHER]

Many real data increase dynamically in size. This phenomenon occurs in several fields including economics, population studies, and medical research. As an effective and efficient mechanism to deal with such data, incremental technique has been proposed in the literature and attracted much attention, which stimulates the result in this paper. When a group of objects are added to a decision table, we first introduce incremental mechanisms for three representative information entropies and then develop a group incremental rough feature selection algorithm based on information entropy. When multiple objects are added to a decision table, the algorithm aims to find the new feature subset in a much shorter time. Experiments have been carried out on eight UCI data sets and the experimental results show that the algorithm is effective and efficient. [ABSTRACT FROM AUTHOR]

A spatial colocation pattern is a group of spatial features whose instances are frequently located together in geographic space. Discovering colocations has many useful applications. For example, colocated plant species discovered from plant distribution data sets can contribute to the analysis of plant geography, phytosociology studies, and plant protection recommendations. In this paper, we study the colocation mining problem in the context of uncertain data, as the data generated from a wide range of data sources are inherently uncertain. One straightforward method to mine the prevalent colocations in a spatially uncertain data set is to simply compute the expected participation index of a candidate and decide if it exceeds a minimum prevalence threshold. Although this definition has been widely adopted, it misses important information about the confidence which can be associated with the participation index of a colocation. We propose another definition, probabilistic prevalent colocations, trying to find all the colocations that are likely to be prevalent in a randomly generated possible world. Finding probabilistic prevalent colocations (PPCs) turn out to be difficult. First, we propose pruning strategies for candidates to reduce the amount of computation of the probabilistic participation index values. Next, we design an improved dynamic programming algorithm for identifying candidates. This algorithm is suitable for parallel computation, and approximate computation. Finally, the effectiveness and efficiency of the methods proposed as well as the pruning strategies and the optimization techniques are verified by extensive experiments with “real $(+)$ synthetic” spatially uncertain data sets. [ABSTRACT FROM AUTHOR]

Attribute reduction is the strongest and most characteristic result in rough set theory to distinguish itself to other theories. In the framework of rough set, an approach of discernibility matrix and function is the theoretical foundation of finding reducts. In this paper, sample pair selection with rough set is proposed in order to compress the discernibility function of a decision table so that only minimal elements in the discernibility matrix are employed to find reducts. First relative discernibility relation of condition attribute is defined, indispensable and dispensable condition attributes are characterized by their relative discernibility relations and key sample pair set is defined for every condition attribute. With the key sample pair sets, all the sample pair selections can be found. Algorithms of computing one sample pair selection and finding reducts are also developed; comparisons with other methods of finding reducts are performed with several experiments which imply sample pair selection is effective as preprocessing step to find reducts. [ABSTRACT FROM PUBLISHER]

We study the problem of assigning subscribers to brokers in a wide-area content-based publish/subscribe system. A good assignment should consider both subscriber interests in the event space and subscriber locations in the network space, and balance multiple performance criteria including bandwidth, delay, and load balance. The resulting optimization problem is NP-complete, so systems have turned to heuristics and/or simpler algorithms that ignore some performance criteria. Evaluating these approaches has been challenging because optimal solutions remain elusive for realistic problem sizes. To enable proper evaluation, we develop a Monte Carlo approximation algorithm with good theoretical properties and robustness to workload variations. To make it computationally feasible, we combine the ideas of linear programming, randomized rounding, coreset, and iterative reweighted sampling. We demonstrate how to use this algorithm as a yardstick to evaluate other algorithms, and why it is better than other choices of yardsticks. With its help, we show that a simple greedy algorithm works well for a number of workloads, including one generated from publicly available statistics on Google Groups. We hope that our algorithms are not only useful in their own right, but our principled approach toward evaluation will also be useful in future evaluation of solutions to similar problems in content-based publish/subscribe. [ABSTRACT FROM AUTHOR]

Reducing the computational complexity of inference in Bayesian Networks (BNs) is a key challenge. Current algorithms for inference convert a BN to a junction tree structure made up of clusters of the BN nodes and the resulting complexity is time exponential in the size of a cluster. The need to reduce the complexity is especially acute where the BN contains continuous nodes. We propose a new method for optimizing the calculation of Conditional Probability Tables (CPTs) involving continuous nodes, approximated in Hybrid Bayesian Networks (HBNs), using an approximation algorithm called dynamic discretization. We present an optimized solution to this problem involving binary factorization of the arithmetical expressions declared to generate the CPTs for continuous nodes for deterministic functions and statistical distributions. The proposed algorithm is implemented and tested in a commercial Hybrid Bayesian Network software package and the results of the empirical evaluation show significant performance improvement over unfactorized models. [ABSTRACT FROM PUBLISHER]