Blockchain technology has transformed financial services sectors by providing security, transparency, and immutability through decentralized ledger systems. However, while blockchain data can support a range of applications-such as user quality analysis, illegal activity detection, and transaction pattern identification-existing systems are restricted to basic queries on blocks and transactions due to their sequential data storage. To support queries more generally, we propose VGQ, the first verifiable graph query (VGQ) framework that enables efficient graph queries on blockchain systems without altering blockchain storage structures. VGQ integrates a query layer with an external graph database system and represents blockchain data as a directed transaction graph to improve the efficiency of graph query execution. To ensure reliable results, VGQ includes result verification with three key performance enhancing optimizations: (i) computing connected components to exclude irrelevant vertices and edges during verification; (ii) merging information from edges to accelerate completeness verification; and (iii) employing a dual pointer algorithm for efficient soundness verification. Experiments offer evidence that VGQ can improve on the state-of-the-art framework in terms of query efficiency by up to one order of magnitude and in terms of verification efficiency by up to two orders of magnitude.

The graph kernel of the functional brain network is an effective method in the field of neuropsychiatric disease diagnosis like Alzheimer's Disease (AD). The traditional static brain networks cannot reflect dynamic changes of brain activities, but evolving brain networks, which are a series of brain networks over time, are able to seize such dynamic changes. As far as we know, the graph kernel method is effective for calculating the differences among networks. Therefore, it has a great potential to understand the dynamic changes of evolving brain networks, which are a series of chronological differences. However, if the conventional graph kernel methods which are built for static networks are applied directly to evolving networks, the evolving information will be lost and accurate diagnostic results will be far from reach. We propose an effective method, called Global Matching based Graph Kernels (GM-GK), which captures dynamic changes of evolving brain networks and significantly improves classification accuracy. At the same time, in order to reflect the natural properties of the brain activity of the evolving brain network neglected by the GM-GK method, we also propose a Local Matching based Graph Kernel (LM-GK), which allows the order of the evolving brain network to be locally fine-tuned. Finally, the experiments are conducted on real data sets and the results show that the proposed methods can significantly improve the neuropsychiatric disease diagnostic accuracy.

Community search on bipartite graphs has been extensively studied in suspicious-group detection and team formation. However, the existing studies focused on the cohesiveness of the community, but ignored the size constraint on bipartite graphs , potentially leading to large community sizes and high costs. In this study, a size-constrained ( α , β )–community (SCC) containing a query vertex on a bipartite graph was investigated, where the upper layer size of the community cannot exceed threshold s and the lower layer size cannot exceed threshold t . For supporting SCC search in different situations, two search methods—peeling and expansion—are proposed by peeling from the ( α , β )-core containing the query vertex and expanding from the query vertex respectively. An efficient lower bound based on degree gap is proposed by terminating unpromising search branches early to increase the efficiency of the community search. The experimental results indicated that the proposed methods can be used to find communities within the size thresholds, with the efficiency of the search increased based on the lower bound.

SimRank is a significant metric to measure the similarity of nodes in graph data analysis. The problem of SimRank computation has been studied extensively, however there is no existing work that can provide one unified algorithm to support the SimRank computation both on static and temporal graphs. In this work, we first propose CrashSim, an index-free algorithm for single-source SimRank computation in static graphs. CrashSim can provide provable approximation guarantees for the computational results in an efficient way. In addition, as the reallife graphs are often represented as temporal graphs, CrashSim enables efficient computation of SimRank in temporal graphs. We formally define two typical SimRank queries in temporal graphs, and then solve them by developing an efficient algorithm based on CrashSim, called CrashSim-T. From the extensive experimental evaluation using five real-life and synthetic datasets, it can be seen that the CrashSim algorithm and CrashSim-T algorithm substantially improve the efficiency of the state-of-the-art SimRank algorithms by about 30%, while achieving the precision of the result set with about 97%.

A representative skylinecontains$k$skyline points that can represent its corresponding full skyline. The existing measuring criteria of$k$representative skylines are specifically designed for static data, and they cannot effectively handle streaming data. In this paper, we focus on the problem of calculating the$k$representative skyline over data streams. First, we propose a new criterion to choose$k$skyline points as the$k$representative skyline for data stream environments, termed the$k$largest dominance skyline ($k$-LDS), which is representative to the entire data set and is highly stable over the streaming data. Second, we propose an efficient exact algorithm, called Prefix-based Algorithm (PBA), to solve the$k$-LDS problem in a 2-dimensional space. The time complexity of PBA is only$\mathcal {O}((M-k)\times k)$where$M$is the size of the full skyline set. Third, the$k$-LDS problem for a$d$-dimensional ($d\ge 3$) space turns out to be very complex. Therefore, a greedy algorithm is designed to answer$k$-LDS queries. To further accelerate the calculation, we propose a$\epsilon$-greedy algorithm which can achieve an approximate factor of$\frac{1}{(1+\epsilon)}(1-\frac{1}{\sqrt{e}})$. Experimental results on both synthetic and real-world data show that our$k$-LDS significantly outperforms its competitors in data stream environments. Furthermore, we demonstrate that the proposed$\epsilon$-greedy algorithm can solve$k$-LDS efficiently and with a competitive accuracy.

Global skyline, as an important variant of skyline, has been widely applied in multiple criteria decision making, business planning and data mining, while there are no previous studies on the global skyline query in the subspace. Hence in this paper we propose subspace global skyline (SGS) query, which is concerned about global skyline in ad hoc subspace. Firstly, we propose an appropriate index structure RB-tree to rapidly find the initial scan positions of query. Secondly, by making analysis of basic properties of SGS, we propose a single SGS algorithm based on RB-tree (SSRB) to compute SGS points. Then an optimized single SGS algorithm based on RB-tree (OSSRB) is proposed, which can reduce the scan space and improve the computation efficiency in contrast to SSRB. Next, by sharing the scan space of different queries, a multiple SGS algorithm based on RB-tree (MSRB) is proposed to compute multiple SGS (MSGS). Finally, the performances of our proposed algorithms are verified through a large number of simulation experiments.

Reverse skyline query plays an important role in many sensing applications, such as environmental monitoring, habitat monitoring, and battlefield monitoring. Due to the limited power supplies of wireless sensor nodes, the existing centralized approaches, which do not consider energy efficiency, cannot be directly applied to the distributed sensor environment. In this paper, we investigate how to process reverse skyline queries energy efficiently in wireless sensor networks. Initially, we theoretically analyzed the properties of reverse skyline query and proposed a skyband-based approach to tackle the problem of reverse skyline query answering over wireless sensor networks. Then, an energy-efficient approach is proposed to minimize the communication cost among sensor nodes of evaluating range reverse skyline query. Moreover, optimization mechanisms to improve the performance of multiple reverse skylines are also discussed. Extensive experiments on both real-world data and synthetic data have demonstrated the efficiency and effectiveness of our proposed approaches with various experimental settings.

A significant number of applications on graph require the key relations among a group of query nodes. Given a relational graph such as social network or biochemical interaction, an informative subgraph is urgent, which can best explain the relationships among a group of given query nodes. Based on Particle Swarm Optimization (PSO), a new framework of SISP (Searching the Informative Subgraph based on PSO) is proposed. SISP contains three key stages. In the initialization stage, a random spreading method is proposed, which can effectively guarantee the connectivity of the nodes in each particle; In the calculating stage of fitness, a fitness function is designed by incorporating a sign function with the goodness score; In the update stage, the intersection-based particle extension method and rule-based particle compression method are proposed. To evaluate the qualities of returned subgraphs, the appropriate calculating of goodness score is studied. Considering the importance and relevance of a node together, we present the PNR method, which makes the definition of informativeness more reliable and the returned subgraph more satisfying. At last, we present experiments on a real dataset and a synthetic dataset separately. The experimental results confirm that the proposed methods achieve increased accuracy and are efficient for any query set.

Traditional databases manage only deterministic information, but now many applications that use databases involve uncertain data. For example, it is infeasible for a sensor database to contain only the exact value of each sensor at all points in time. The uncertainty is inherent in these systems due to measurement and sampling errors, and resource limitations. This paper aims at the query processing algorithm of twig patterns on probabilistic XML documents. The existing algorithms evaluate twig patterns in a traversal way. The main shortcoming of this way is scanning the whole probabilistic XML document to get the final results. In this paper, we first represent a probabilistic XML document in the form of probabilistic tag streams and then match them in a holistic way. Extensive experiments are conducted and show that the proposed holistic way has the higher performance than the traversal way.