Clustering signed networks—graphs with positive (trust) and negative (distrust) edges—is fundamental in social computing, yet existing methods remain difficult to scale. Classical spectral formulations can require O ( n 3 ) time and O ( n 2 ) memory, while tested batch graph neural-network baselines exceed available memory at larger scales. We propose SSGC , a relaxed semi-streaming framework that retains a bounded edge reservoir for selective post-stream refinement. SSGC processes edges in one pass using Top- C candidate pruning and a k × k signed sketch, then applies Selective Refinement to conflicted nodes using reservoir-based Sign-Aware Local Vote . The memory usage is O ( n + k 2 + B ) , where B is a tunable retained-edge budget. On synthetic signed stochastic block models (SSBM), SSGC with Selective Refinement achieves Adjusted Rand Index (ARI) 0.980–1.000 for k = 50 –10000, compared with ARI = 0.25 for greedy-only streaming. On Epinions (709K edges), SSGC reaches Louvain-level Disagreement (0.044 vs 0.047, p = 0.018 ) with a 36 × runtime speedup, but lower Signed Modularity ( Q s = 0.51 vs 0.71), reflecting a local-purity/global-modularity trade-off. On the 1.8B-edge Friendster throughput benchmark with synthetic signs, SSGC runs within 14GB memory at approximately 1.0M edges/sec; Birdwatch and Friendster are reported primarily as scalability studies.

Spatio-temporal prediction is fundamental to a wide range of applications, including traffic flow forecasting and air quality monitoring. However, real-world spatio-temporal systems are rarely governed by homogeneous or synchronized interactions. Spatial dependencies often vary across regions, temporal patterns evolve at multiple scales, and the influence of one location on another may emerge with dynamic, region-specific delays rather than in a synchronized manner. These heterogeneous and asynchronous lag characteristics pose substantial challenges to accurate prediction, whereas most existing methods rely on static spatial graphs or synchronized temporal modeling, which limits their ability to capture complex real-world dynamics. To address this, we propose the lag-heterogeneity guided spatio-temporal graph neural network (LH-GSTGNN). Rather than relying on stationary assumptions, LH-GSTGNN treats lag heterogeneity as an explicit modeling target. It characterizes evolving spatial dependencies, captures temporal dynamics across multiple ranges, and highlights delayed responses embedded in intermediate representations. In this way, the proposed framework preserves heterogeneous and asynchronous interactions that are otherwise prone to being smoothed out, yielding a more faithful representation of real-world spatio-temporal dynamics. Extensive experiments on nine real-world datasets covering traffic flow, traffic speed, and air quality prediction show that LH-GSTGNN consistently outperforms strong baselines, achieving up to 4.9% lower MAE and 2.9% lower RMSE than the second-best method. Visualization-based case studies further demonstrate its effectiveness in modeling both spatial heterogeneity and diverse lagged fluctuations.

Abstract Graph partitioning is an NP-hard combinatorial optimization problem, and is a fundamental step in distributing workloads on parallel compute systems, circuit placement, and sparse matrix reordering. The proposed heuristic algorithms such as streaming graph partitioning provide solutions to large-scale graph in a reasonable amount of time. However, the ability of breaking out of local minima in existing these methods is very limited as they are simple in reflecting the connectivity between vertices in real graphs with power-law distribution characteristic. As hill climbing algorithm is a local search method, it can be adopted to improve the result of graph partitioning. However, directly adopting the existing hill climbing algorithm to graph partitioning will result in local minima and poor convergence speed during the iterative process. In this paper, we propose an improved hill climbing graph partitioning algorithm based on clustering. Instead of taking a single vertex as a basic unit, the proposed method considers a cluster consisting of a series of vertices as a hill to move during each iteration. The method uses a new metric that considers both balance and edgecuts to look for the most beneficial cluster as the hill. With these improvements, the method provides a strong power to break out of local minima and achieve an adaptive tradeoff between balance and edgecuts. Experimental results on real-world graphs show that the proposed algorithm substantially reduces edgecuts within a controlled imbalance range.

As various opinions and thoughts of users are shared on social media, various events can be detected through social media data analysis. The graph-based event detection scheme may eliminate event duplication detection by clustering words related to an event. In this paper, we propose a graph-based event detection scheme for detecting various events in the real world through social media analysis. The proposed scheme expresses the simultaneous occurrence of words mentioned with an event in graph form. Therefore, it can convey the information about the detected event and avoid duplicate detection. A keyword graph is constructed and keywords related to an event are clustered by analyzing the collected social data. By considering user interest calculated through changes in social activities of users on social media, the proposed scheme can detect event results that receive more responses from users and improve the reliability of the results by excluding indiscriminate advertisements or malicious posts from the results. We assign a weight to the generated keyword graph by considering user interest and calculate an event detection coefficient to determine the event values of the candidate event graphs. We perform various evaluations to demonstrate the superiority of the proposed scheme.

As the utilization of graph streams in various applications increases, a continuous subgraph matching scheme is required to search for subgraphs that change in real time. In this paper, we present a novel and effective continuous subgraph matching scheme that leverages indexing and employs distributed processing in graph stream environments. To achieve distributed processing, we employ a query graph decomposition policy based on the degree of nodes, allowing us to manage the decomposed subqueries as an index. By reusing indexing information, we significantly reduce the indexing load, which becomes crucial in scenarios where multiple queries are issued simultaneously. To optimize query allocation in the distributed environment, we introduce a cost model that accurately calculates the indexing load for each server. This ensures a balanced distribution of queries, enhancing overall system performance. To perform distributed processing efficiently in stream environments, the proposed scheme is implemented in Storm. We conduct various performance evaluations to demonstrate the superiority of the proposed scheme.

Traffic prediction is the core task of intelligent transportation system (ITS) and accurate traffic prediction can greatly improve the utilization of public resources. Dynamic interaction of multiple spatial relationships will influence the accuracy of traffic prediction. However, many existing methods only consider static spatial relationships, which restricts the accuracy of the prediction. To address the above problem, in this article, we propose the Dynamic Multi-Graph Fusion Network (DMGF-Net) to model the spatial-temporal correlations in traffic network. In the DMGF-Net, the fusion graph is designed to leverage and extract the various spatial correlations between different regions by fusing spatial graph, semantic graph, and spatial-semantic graph. Further, to dynamically learn the importance of different neighbors, we design the Dynamic Spatial-Temporal Unit (DSTU), which can adjust the aggregation weights of different neighbors by combining the convolution operation and the attention mechanism. It can selectively aggregate spatial-temporal features from different neighbors. Extensive experiments on three datasets demonstrate that effectiveness of our model, especially on PEMS08, our model achieves an increase of about 8.55% and 7.55% in terms of MAE and RMSE than the static model STGCN.

Recently, content-based image retrieval has been used for monitoring and tracking criminal behavior in images and videos. In addition, with the development of machine learning techniques, image searches using scene graphs have also been studied. The characteristic of scene graph data is that there are very many dimensions of the data. There is a problem that it is generally difficult to retrieve. In this paper, we propose a distributed in-memory-based high-dimensional indexing scheme. Wet can exploit the proposed scheme for similarity search using large high-dimensional vectors for content-based image retrieval and scene graphs. Furthermore, we propose a multi-level indexing scheme to utilize the master/slave model. In addition, we perform performance evaluations to demonstrate the superiority and validity of the proposed scheme.

Graph partitioning is a mandatory step in distributed graph computing systems. Some existing systems use edge partitioning methods to partition static graphs. However, the structure of the real-world graphs changes dynamically, which leads to unnecessary vertex replicas and load imbalance, reducing the performance of graph computation. In this article, we focus on improving the lower partitioning quality caused by the dynamics of the graph structure. We propose an edge repartitioning algorithm via structure-aware group migration (SAGM-ER). We define a special structure edge group (EG) consisting of multiple edges, which can reduce vertex replicas by migrating to other partitions. In repartitioning, we search for EGs in parallel by a method based on a structure-aware priority and then migrate EGs to reduce vertex replicas. Compared to the state of the art, SAGM-ER can reduce more vertex replicas. We implement SAGM-ER on Powergraph, which reduces the redundant replicas by 63.33%, thus reducing executing time and communication costs in graph computation by 33.72% and 37.51%, respectively.

Traffic spatial-temporal prediction is of great significance to traffic management and urban construction. In this paper, we propose a multi-task graph Synchronous neural network (MTSGNN) to synchronously predict the spatial-temporal data at the regions and transitions between regions. The method of constructing "multitask graph representation" is proposed to retain the information of regions and transitions that existing works can not reflect. Then our model synchronously captures multiple types of dynamic spatial correlations, models dynamic temporal dependencies and re-weights different time steps to solve the problem of long-term time modeling. In three real data sets, we verify the validity of the proposed model.

Detectors with high coverage have direct and far-reaching benefits for road users in route planning and avoiding traffic congestion, but utilizing these data presents unique challenges including: the dynamic temporal correlation, and the dynamic spatial correlation caused by changes in road conditions. Although the existing work considers the significance of modeling with spatial-temporal correlation, what it has learned is still a static road network structure, which cannot reflect the dynamic changes of roads, and eventually loses much valuable potential information. To address these challenges, we propose DetectorNet enhanced by Transformer. Differs from previous studies, our model contains a Multi-view Temporal Attention module and a Dynamic Attention module, which focus on the long-distance and short-distance temporal correlation, and dynamic spatial correlation by dynamically updating the learned knowledge respectively, so as to make accurate prediction. In addition, the experimental results on two public datasets and the comparison results of four ablation experiments proves that the performance of DetectorNet is better than the eleven advanced baselines.

Graph partitioning is a mandatory step in large-scale distributed graph processing. When partitioning real-world power-law graphs, the edge partitioning algorithm performs better than the traditional vertex partitioning algorithm, because it can cut a single vertex into multiple replicas to apportion the computation. Many advanced edge partitioning methods are designed for partitioning a static graph from scratch. However, the real-world graph structure changes continuously, which leads to a decrease in partition quality and affects the performance of the graph applications. Some studies are devoted to offline repartitioning or batch incremental partitioning, but how to deal with dynamics in real-time is still worthy of in-depth study. In this article, we discuss the impact of dynamic change on partition and discover that both insertion and deletion will lead to local suboptimal partitioning, which is the reason for the degradation of partition quality. As a solution, a dynamic edge partitioning algorithm is proposed to partition dynamics in real-time. Specifically, we deal with dynamics by a distributed stream and improve partition quality by reassigning some closely connected edges. Experiments show that it is robust to initial partition quality, dynamic scale and type, and distributed scale. Compared with the state-of-the-art dynamic partitioner, it can reduce vertex-cuts by 29.5 percent. Compared with the repartitioning algorithms, it can save the partitioning time by 91.0 percent. Applied on the graph task, it can reduce the increase of communication cost and the increase of the total time of task by 41.5 and 71.4 percent.

Summary As various social network services have developed, users are creating and sharing a large amount of content. Concurrently, there have been many studies on recommendation schemes for providing users with content that matches their preferences. In this paper, we propose a trust‐based personalized content recommendation scheme using collaborative filtering in online social network services. The user trust is calculated by analyzing social activities, content usages, and social relationships. In addition, the content trust is calculated by analyzing user expertise and reputations. Collaborative filtering is performed on users who are filtered through the user trust, and recommendation priorities are determined according to the content trust. The proposed scheme can improve the performance of collaborative filtering by eliminating untrustworthy users using user trust. It also improves the accuracy of recommendations since it provides recommendations based on content trust. Therefore, the proposed scheme can improve the performance of recommendation services using collaborative filtering in online social network services that share multimedia content. Performance evaluation is performed in terms of MAE and RMSE, which assesses errors in recommended results to demonstrate the superiority of the proposed scheme. Performance evaluations have shown that errors in the proposed scheme are reduced compared to the existing schemes, improving the accuracy of recommendations.

The increasing popularity of social networks improves information sharing among different users. Most existing online social networks involve the client/server architecture where each user needs to access to a server for contents sharing with other users. In this paper, we focus on constructing a mobile peer-to-peer based social network. We propose an efficient mobile social network to facilitate contents sharing over mobile ad hoc networks, in which social communities are built based on the interesting keywords, location histories and the current locations of different users. The users with common interest keywords, similar location histories and nearby current location are recommended as friends and connect directly in the mobile social network. The performance results show that the proposed method outperforms the existing methods in terms of the network management cost and contents search.

With the rapid development of wireless communication technologies and mobile devices, the mobile peer to peer (MP2P) network has been emerged. Since the existing MP2P architectures have high management cost, in this paper, we propose a hierarchical MP2P architecture using clustering mobile peers. The proposed method clusters the mobile peers by considering three aspects like the maximum connection time, the minimum hop count and the number of the connected peers. The connection times between the connected peers can be determined by the location, velocity vector and communication range of the mobile peers. Since the maximum connection time of the connected peers are considered, the network topology is relatively stable. Therefore, the management cost of the network is decreased and the success rate of contents search is increased. Experiments have shown that our proposed method outperforms the existing schemes.

The k-nearest neighbor (k-NN) query is one of the most important query types for location based services (LBS). Various methods have been proposed to efficiently process the k-NN query. However, most of the existing methods suffer from high computation time and larger memory requirement because they unnecessarily access cells to find the nearest cells on a grid index. In this paper, we propose a new efficient method, called Pattern Based k-NN (PB-kNN) to process the k-NN query. The proposed method uses the patterns of the distance relationships among the cells in a grid index. The basic idea is to normalize the distance relationships as certain patterns. Using this approach, PB-kNN significantly improves the overall performance of the query processing. It is shown through various experiments that our proposed method outperforms the existing methods in terms of query processing time and storage overhead.

The skyline queries are often used in several recommendation applications. Most existing related works have focused on skyline computation in many multidimensional data. However, these works do not consider an interesting query generated from non-skyline point. In this paper, we propose a new query, called skyline minimum vector which finds the minimum vector for making a non-skyline point into a skyline. The skyline minimum vector means the minimum cost for becoming a skyline. We use the Manhattan distance between skyline and query point in order to evaluate the cost. Also, we propose basic algorithm and optimized algorithm for getting skyline minimum vector. The proposed query will be very useful in many decision-making applications.

In wireless sensor networks, various schemes have been proposed to efficiently store and process sensed data. Among them, the Data-Centric Storage (DCS) scheme is one of the most well-known. The DCS scheme distributes data regions and stores the data in the sensor that is responsible for the region. In this paper, we propose a new DCS based scheme, called Time-Parameterized Data-Centric Storage (TPDCS), that avoids the problems of storage hot-spots and query hotspots. To decentralize the skewed data and queries, the data regions are assigned by a time dimension as well as data dimensions in our proposed scheme. Therefore, TPDCS extends the lifetime of sensor networks. It is shown through various experiments that our scheme outperforms the existing schemes.

Biological sequences such as DNA and amino acid sequences typically contain a large number of items. They have contiguous sequences that ordinarily consist of more than hundreds of frequent items. In biological sequences analysis (BSA), a frequent contiguous sequence search is one of the most important operations. Many studies have been done for mining sequential patterns efficiently. In recent years, the MacosVSpan algorithm was proposed based on the idea of the prefixSpan algorithm to significantly reduce its recursive process. However, the algorithm is inefficient for mining frequent contiguous sequences from long biological data sequences. In this paper, we propose an efficient method to mine maximal frequent contiguous sequences in large biological data sequences by constructing the spanning tree with a fixed length. To verify the superiority of the proposed method, we perform experiments in various environments. The experiments show that the proposed method is much more efficient than MacosVSpan in terms of retrieval performance.

We propose an algorithm which specifies pattern names for retrieving, exploring the adapted patterns on the stage of design without pattern language that is redundant abstraction. By applying composite design pattern to the design of the object-oriented recursive river and basin data model interface for Total Maximum Daily Load discipline, We have the result showing far better improvement of performance in the category of polymorphism and especially of reusability than conventional basin models. Thus, this study can contribute on the reducing iterations and repetitions of up-dating and committing after the spatial data changes that are frequently occurred in the process of the environmental GIS model developments.

In this paper, we propose a concurrency control algorithm based on link-technique for high-dimensional index structures. In high dimensional index structures, search operations are generally more frequent than insert or delete operations and need to access more nodes than those in other index structures, such as B+-tree, B-tree, hashing techniques, and so on, due to the properties of queries. In the proposed algorithm, we focus on minimizing the delay of search operations in all cases. It also supports concurrency control on reinsert operations for the high-dimensional index structures employing reinsert operations to improve their performance. We apply the algorithm to one of the exiting multi-dimensional index structures and implement it on a storage system. It is shown through various experiments that the proposed algorithm is more suitable for high dimensional index structures than existing ones.

We propose an enhanced concurrency control algorithm that maximizes the concurrency of multidimensional index structures. The factors that deteriorate the concurrency of index structures are node splits and minimum bounding region (MBR) updates in multidimensional index structures. The properties of our concurrency control algorithm are as follows: First, to increase the concurrency by avoiding lock coupling during MBR updates, we propose the PLC (partial lock coupling) technique. Second, a new MBR update method is proposed. It allows searchers to access nodes where MBR updates are being performed. Finally, our algorithm holds exclusive latches not during whole split time but only during physical node split time that occupies the small part of a whole split process. For performance evaluation, we implement the proposed concurrency control algorithm and one of the existing link technique-based algorithms on MIDAS-III that is a storage system of a BADA-IV DBMS. We show through various experiments that our proposed algorithm outperforms the existing algorithm in terms of throughput and response time. Also, we propose a recovery protocol for our proposed concurrency control algorithm. The recovery protocol is designed to assure high concurrency and fast recovery.

Propose an enhanced concurrency control algorithm that minimizes the query delay efficiently. The factors that delay search operations and deteriorate the concurrency of index structures are node splits and minimum bounding region (MBR) updates in multi-dimensional index structures. In our algorithm, in order to reduce the query delay by splitting operations, we optimize the exclusive latching time on a split node. It does not hold exclusive latches throughout the whole split time but only during the physical node split time, which occupies only a small part of the whole split time. Also, to avoid the query delay caused by MBR updates, we introduce the partial lock coupling (PLC) technique. PLC increases concurrency by using lock coupling only in the case of MBR shrinking operations that are less frequent than MBR expansion operations. For performance evaluation, we implement the proposed algorithm and one of the existing link technique-based algorithms on MIDAS-III, which is the storage system of the BADA-III DBMS. We show, through various experiments, that our proposed algorithm outperforms the existing algorithm in terms of throughput and response time.

With rapid increase of information requirements from various application areas, there has been much research on dynamic information storage structures that effectively support insertions, deletions and updates. We evaluate the performance of the existing dynamic signature file methods such as the S-tree, Quid Filter and HS file, and provide guidelines for the most effective usage to a given operational environment. We derive analytic performance evaluation models of the storage structures based on retrieval time, storage overhead and insertion time. We also perform extensive experiments with various data distributions such as uniform, normal and exponential distributions.