Streaming triangle counting is a critical issue in graph stream mining, with applications in dense subgraph discovery, web mining, anomaly detection, and more. Recent efforts have focused on estimating triangle counts in graph streams, primarily through sampling methods. However, because of limited memory resources for handling high speed streams, traditional sampling methods suffer from reduced sampling rate and thereby performance loss. In this paper, we propose a new compact data structure called uHLL to process edge streams by considering the tradeoff between estimation accuracy and memory efficiency. Furthermore, different from conventional triangle counting algorithms, we solve the estimation of union set cardinality for edge-local triangle count under both centralized and distributed framework, so as to efficiently estimate the global triangle count by a one-pass streaming algorithm. To the best of our knowledge, this is the first implementation of a distributed framework using a compact data structure for streaming triangle counting. We provide theoretical proof of unbiasedness and derive the variance of the union set and global triangle count. We compare our scheme with 11 algorithms, showing that under the same experimental setting, uHLL and distributed uHLL are at least$ 2.3$and$ 1.7$times more accurate than the state-of-the-art, respectively.

Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, the problem of counting global and local triangles in a graph stream has been widely studied, and numerous triangle counting steaming algorithms have emerged. To improve the throughput and scalability of streaming algorithms, many researches of distributed streaming algorithms on multiple machines are studied. In this article, we first propose a framework of distributed streaming algorithm based on the Master-Worker-Aggregator architecture. The two core parts of this framework are an edge distribution strategy, which plays a key role to affect the performance, including the communication overhead and workload balance, and aggregation method, which is critical to obtain the unbiased estimations of the global and local triangle counts in a graph stream. Then, we extend the state-of-the-art centralized algorithm TRIÈST into four distributed algorithms under our framework. Compared to their competitors, experimental results show that DVHT-i is excellent in accuracy and speed, performing better than the best existing distributed streaming algorithm. DEHT-b is the fastest algorithm and has the least communication overhead. What’s more, it almost achieves absolute workload balance.

Personalized trip recommendation tries to recommend a sequence of point of interests (POIs) for a user. Most of existing studies search POIs only according to the popularity of POIs themselves. In fact, the routes among the POIs also have attractions to visitors, and some of these routes have high popularity. We term this kind of route as Attractive Route (AR), which brings extra user experience. In this paper, we study the attractive routes to improve personalized trip recommendation. To deal with the challenges of discovery and evaluation of ARs, we propose a personalized Trip Recommender with POIs and Attractive Route (TRAR). It discovers the attractive routes based on the popularity and the Gini coefficient of POIs, then it utilizes a gravity model in a category space to estimate the rating scores and preferences of the attractive routes. Based on that, TRAR recommends a trip with ARs to maximize user experience and leverage the tradeoff between the time cost and the user experience. The experimental results show the superiority of TRAR compared with other state-of-the-art methods.

Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.

Pedestrian flow is an important indicator of public places, since it can provide more potential economic benefits. Pedestrian flow prediction is developed to help the decisionmaking for the operators (such as shopping center owner). Furthermore, the operators aperiodically arrange some events to attract the nearby pedestrians, such as the sales promotions, and we term this kind of events as business event. Moreover, their placement will affect the distributions of the pedestrian flows. In this paper, we investigate the influence of the business events on the pedestrian flows. Then, we propose an Attraction Based Matrix Factorization model, called ABMF, to efficiently predict the pedestrian flow with business events and enable operators to formulate candidate solutions. The experimental results show the superiority of our prediction method compared with other state-of-the-art prediction techniques.

To improve the experience of various network applications, dynamic rate allocation is an essential issue in recent ISP networks. The emergence of software-defined networking (SDN) and the OpenFlow specification makes dynamic rate allocation in ISP networks efficient. The allocation could locally run on a home network gateway (edge switch) under SDN, but such local range of rate allocation reduces the overall fairness and performance in the whole network. However, under a global range, the request of rate allocation from a small number of hosts will cause all switches on the entire network to participate. This is termed as cascading problem, which causes a high cost for re-allocating the rates with the global range of switches. In this paper, we investigate the cascading problem for dynamic rate allocation with SDN, and discuss the tradeoff between the performance and cost for the range of rate allocation. We propose a Rate Allocation algorithm with Limited Range (RALR) in SDN, and discuss it for dynamic rate allocation by the theory of Lyapunov drift. Our intensive simulations verify the performance of the proposed strategy of rate allocation in SDN.