Zhengyi Yang's Publications
• SIGMOD (1) • VLDB (1) • ICDE (2) • WWW (2) • CIKM (1) • DASFAA (2) • WISE (2) • KSEM (1) •
• Sorted by type • 2024 • 2023 • 2022 • 2021 • 2020 • 2019 •
2024
-
Tianming Zhang, Xinwei Cai, Lu Chen, Zhengyi Yang, Yunjun Gao, Bin Cao, Jing Fan,
"Towards efficient simulation-based constrained temporal graph pattern matching",
World Wide Web, vol. 27, no. 3, pp. 22, Apr, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@article{zhang2024towards, author = {Tianming Zhang and Xinwei Cai and Lu Chen and Zhengyi Yang and Yunjun Gao and Bin Cao and Jing Fan}, doi = {10.1007/s11280-024-01259-2}, journal = {World Wide Web}, month = {Apr}, number = {3}, pages = {22}, title = {Towards efficient simulation-based constrained temporal graph pattern matching}, url = {https://doi.org/10.1007/s11280-024-01259-2}, volume = {27}, year = {2024} }Abstract
In the context of searching a single data graph G, graph pattern matching is to find all the occurrences of a pattern graph Q in G, specified by a matching rule. It is of paramount importance in many real applications such as social network analysis and cyber security, among others. A wide spectrum of studies target general graph pattern matching. However, to analyze time-relevant services such as studying the spread of diseases and detecting attack patterns, it is attractive to study inexact temporal graph pattern matching. Hence, in this paper, we propose a relaxed matching rule called constrained temporal dual simulation, and study simulation- based constrained temporal graph pattern matching which guarantees that the matching result (i) preserves the ancestor and descendant temporal connectivities; and (ii) implements edge-to-temporal path mapping. We devise a decomposition-based matching method, which first decomposes the data graph into Source Temporal Connected Components, and then performs matching on decomposed subgraphs. To speed up the matching, we define child/parent dependency relation tables and propose an efficient double hierarchical traverse strategy. Considering that the temporal graphs are naturally dynamic, we further propose update algorithms. An extensive empirical study over real-world and synthetic temporal graphs has demonstrated the effectiveness and efficiency of our approach.
-
Sai Li, Peng Kou, Miao Ma, Haoyu Yang, Shuo Huang, Zhengyi Yang,
"Application of Semi-Supervised Learning in Image Classification: Research on Fusion of Labeled and Unlabeled Data",
IEEE Access, vol. 12, no. , pp. 27331–27343, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@article{li2024application, author = {Sai Li and Peng Kou and Miao Ma and Haoyu Yang and Shuo Huang and Zhengyi Yang}, doi = {10.1109/ACCESS.2024.3367772}, journal = {IEEE Access}, number = {}, pages = {27331–27343}, title = {Application of Semi-Supervised Learning in Image Classification: Research on Fusion of Labeled and Unlabeled Data}, url = {https://dx.doi.org/10.1109/ACCESS.2024.3367772}, volume = {12}, year = {2024} }Abstract
Deep learning has attracted wide attention recently because of its excellent feature representation ability and end-to-end automatic learning method. Especially in clinical medical imaging diagnosis, the semi-supervised deep learning model is favored and widely used because it can make maximum use of a limited number of labeled data and combine it with a large number of unlabeled data to extract more information and knowledge from it. However, the scarcity of medical image data, the vast image size, and the instability of image quality directly affect the model's robustness, generalization, and image classification performance. Therefore, this paper proposes a new semi-supervised learning model, which uses quadratic neurons instead of traditional neurons, aiming to use quadratic convolution instead of the conventional convolution layer to improve the feature extraction ability of the model. In addition, we introduce two Dropout layers and two fully connected layers at the end of the model to enhance the nonlinear fitting ability of the network. Experiments on two large medical public data sets - ISIC 2019 and Retinopathy OCT - show that our method can improve the model's generalization performance and image classification accuracy.
-
Lingbo Li, Zhichun Li, Fusen Guo, Haoyu Yang, Jingtian Wei, Zhengyi Yang,
"Prototype Comparison Convolutional Networks for One-Shot Segmentation",
IEEE Access, vol. 12, no. , pp. 54978–54990, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@article{li2024prototype, author = {Lingbo Li and Zhichun Li and Fusen Guo and Haoyu Yang and Jingtian Wei and Zhengyi Yang}, doi = {10.1109/ACCESS.2024.3387742}, journal = {IEEE Access}, number = {}, pages = {54978–54990}, title = {Prototype Comparison Convolutional Networks for One-Shot Segmentation}, url = {https://dx.doi.org/10.1109/ACCESS.2024.3387742}, volume = {12}, year = {2024} }Abstract
In few-shot semantic segmentation (FSS), the key challenges are efficiently tuning the interaction between the support set and the query set and distinguishing between context, background, and interfering items. To address these challenges, we propose prototype comparison networks for one-shot segmentation (OPCN) to capture the details required for FSS. Specifically, we offer the Fusion Interaction Module (FIM) to improve the segmentation performance by capturing the correlation and semantic information between the support set and query set features. Subsequently, we propose the Feature Enhancement Module (FEM), which aims to enhance the information required in the support set and query set features while increasing the focus on critical details by reducing the weight of the background regions to provide a more targeted feature representation for subsequent query image segmentation. Then, we propose the Feature Refinement Module (FRM) to filter irrelevant background information in the features and specify the target location region. Finally, the Feature Matching Module (FM) generates the final segmentation mask for the query image. Extensive experiments on the PASCAL-5i and COCO-20i datasets show that our approach achieves excellent performance in the case of the one-shot setup.
-
Tianming Zhang, Yunjun Gao, Jie Zhao, Lu Chen, Lu Jin, Zhengyi Yang, Bin Cao, Jing Fan,
"Efficient Exact and Approximate Betweenness Centrality Computation for Temporal Graphs",
Proceedings of The Web Conference 2024 (WWW), 2024.
[bibtex]
Bibtex
@inproceedings{zhang2024efficient, author = {Tianming Zhang and Yunjun Gao and Jie Zhao and Lu Chen and Lu Jin and Zhengyi Yang and Bin Cao and Jing Fan}, booktitle = {Proceedings of The Web Conference 2024 (WWW)}, title = {Efficient Exact and Approximate Betweenness Centrality Computation for Temporal Graphs}, year = {2024} } -
Tianming Zhang, Junkai Fang, Zhengyi Yang, Bin Cao, Jing Fan,
"TATKC: A Temporal Graph Neural Network for Fast Approximate Temporal Katz Centrality Ranking",
Proceedings of The Web Conference 2024 (WWW), 2024.
[bibtex]
Bibtex
@inproceedings{zhang2024tatkc, author = {Tianming Zhang and Junkai Fang and Zhengyi Yang and Bin Cao and Jing Fan}, booktitle = {Proceedings of The Web Conference 2024 (WWW)}, title = {TATKC: A Temporal Graph Neural Network for Fast Approximate Temporal Katz Centrality Ranking}, year = {2024} } -
Kaiyu Chen, Dong Wen, Wentao Li, Zhengyi Yang, Wenjie Zhang,
"On Compressing Historical Cliques in Temporal Graphs",
Proceedings of the 29th International Conference on Database Systems for Advanced Applications (DASFAA), 2024.
[bibtex]
Bibtex
@inproceedings{chen2024compressing, author = {Kaiyu Chen and Dong Wen and Wentao Li and Zhengyi Yang and Wenjie Zhang}, booktitle = {Proceedings of the 29th International Conference on Database Systems for Advanced Applications (DASFAA)}, title = {On Compressing Historical Cliques in Temporal Graphs}, year = {2024} }
2023
-
Nimish Ukey#, Guangjian Zhang#, Zhengyi Yang*, Binghao Li, Wei Li, Wenjie Zhang,
"Efficient continuous kNN join over dynamic high-dimensional data",
World Wide Web, Sep, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@article{ukey2023efficient, author = {Nimish Ukey# and Guangjian Zhang# and Zhengyi Yang* and Binghao Li and Wei Li and Wenjie Zhang}, doi = {10.1007/s11280-023-01204-9}, journal = {World Wide Web}, month = {Sep}, title = {Efficient continuous kNN join over dynamic high-dimensional data}, url = {https://doi.org/10.1007/s11280-023-01204-9}, year = {2023} }Abstract
Given a user dataset U and an object dataset I, a kNN join query in high-dimensional space returns the k nearest neighbors of each object in dataset U from the object dataset I. The kNN join is a basic and necessary operation in many applications, such as databases, data mining, computer vision, multi-media, machine learning, recommendation systems, and many more. In the real world, datasets frequently update dynamically as objects are added or removed. In this paper, we propose novel methods of continuous kNN join over dynamic high-dimensional data. We firstly propose the HDR+ Tree, which supports more efficient insertion, deletion, and batch update. Further observed that the existing methods rely on globally correlated datasets for effective dimensionality reduction, we then propose the HDR Forest. It clusters the dataset and constructs multiple HDR Trees to capture local correlations among the data. As a result, our HDR Forest is able to process non-globally correlated datasets efficiently. Two novel optimisations are applied to the proposed HDR Forest, including the precomputation of the PCA states of data items and pruning-based kNN recomputation during item deletion. For the completeness of the work, we also present the proof of computing distances in reduced dimensions of PCA in HDR Tree. Extensive experiments on real-world datasets show that the proposed methods and optimisations outperform the baseline algorithms of naive RkNN join and HDR Tree.
-
Nimish Ukey, Zhengyi Yang*, Binghao Li, Guangjian Zhang, Yiheng Hu, Wenjie Zhang,
"Survey on Exact kNN Queries over High-Dimensional Data Space",
Sensors, vol. 23, no. 2, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@article{ukey2023survey, author = {Nimish Ukey and Zhengyi Yang* and Binghao Li and Guangjian Zhang and Yiheng Hu and Wenjie Zhang}, doi = {10.3390/s23020629}, journal = {Sensors}, number = {2}, title = {Survey on Exact kNN Queries over High-Dimensional Data Space}, url = {https://www.mdpi.com/1424-8220/23/2/629}, volume = {23}, year = {2023} }Abstract
k nearest neighbours (kNN) queries are fundamental in many applications, ranging from data mining, recommendation system and Internet of Things, to Industry 4.0 framework applications. In mining, specifically, it can be used for the classification of human activities, iterative closest point registration and pattern recognition and has also been helpful for intrusion detection systems and fault detection. Due to the importance of kNN queries, many algorithms have been proposed in the literature, for both static and dynamic data. In this paper, we focus on exact kNN queries and present a comprehensive survey of exact kNN queries. In particular, we study two fundamental types of exact kNN queries: the kNN Search queries and the kNN Join queries. Our survey focuses on exact approaches over high-dimensional data space, which covers 20 kNN Search methods and 9 kNN Join methods. To the best of our knowledge, this is the first work of a comprehensive survey of exact kNN queries over high-dimensional datasets. We specifically categorise the algorithms based on indexing strategies, data and space partitioning strategies, clustering techniques and the computing paradigm. We provide useful insights for the evolution of approaches based on the various categorisation factors, as well as the possibility of further expansion. Lastly, we discuss some open challenges and future research directions.
-
Liuyi Chen, Bocheng Han, Xuesong Wang, Jiazhen Zhao, Wenke Yang, Zhengyi Yang*,
"Machine Learning Methods in Weather and Climate Applications: A Survey",
Applied Sciences, vol. 13, no. 21, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@article{chen2023machine, author = {Liuyi Chen and Bocheng Han and Xuesong Wang and Jiazhen Zhao and Wenke Yang and Zhengyi Yang*}, doi = {10.3390/app132112019}, journal = {Applied Sciences}, number = {21}, title = {Machine Learning Methods in Weather and Climate Applications: A Survey}, url = {https://www.mdpi.com/2076-3417/13/21/12019}, volume = {13}, year = {2023} }Abstract
With the rapid development of artificial intelligence, machine learning is gradually becoming popular for predictions in all walks of life. In meteorology, it is gradually competing with traditional climate predictions dominated by physical models. This survey aims to consolidate the current understanding of Machine Learning (ML) applications in weather and climate prediction—a field of growing importance across multiple sectors, including agriculture and disaster management. Building upon an exhaustive review of more than 20 methods highlighted in existing literature, this survey pinpointed eight techniques that show particular promise for improving the accuracy of both short-term weather and medium-to- long-term climate forecasts. According to the survey, while ML demonstrates significant capabilities in short-term weather prediction, its application in medium-to-long-term climate forecasting remains limited, constrained by factors such as intricate climate variables and data limitations. Current literature tends to focus narrowly on either short-term weather or medium-to- long-term climate forecasting, often neglecting the relationship between the two, as well as general neglect of modeling structure and recent advances. By providing an integrated analysis of models spanning different time scales, this survey aims to bridge these gaps, thereby serving as a meaningful guide for future interdisciplinary research in this rapidly evolving field.
-
Zhengyi Yang, Wenjie Zhang, Xuemin Lin*, Ying Zhang, Shunyang Li,
"HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs",
2023 IEEE 39th International Conference on Data Engineering (ICDE), vol. , no. , pp. 2063–2076, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{yang2023hgmatch, author = {Zhengyi Yang and Wenjie Zhang and Xuemin Lin* and Ying Zhang and Shunyang Li}, booktitle = {2023 IEEE 39th International Conference on Data Engineering (ICDE)}, doi = {10.1109/ICDE55515.2023.00160}, number = {}, pages = {2063–2076}, title = {HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs}, url = {https://dx.doi.org/10.1109/ICDE55515.2023.00160}, volume = {}, year = {2023} }Abstract
Hypergraphs are generalisation of graphs in which a hyperedge can connect any number of vertices. It can describe n-ary relationships and high-order information among entities compared to conventional graphs. In this paper, we study the fundamental problem of subgraph matching on hypergraphs (i.e, subhypergraph matching). Existing methods directly extend subgraph matching algorithms to the case of hypergraphs. However, this approach delays hyperedge verification and underutilises the high-order information in hypergraphs, which leads to large search space and high enumeration cost. Furthermore, with the growing size of hypergraphs, it is becoming hard to compute subhypergraph matching sequentially. Thus, we propose an efficient and parallel subhypergraph matching system, HGMatch, to handle subhypergraph matching in massive hypergraphs. We proposes a novel match-by-hyperedge framework to utilise high-order information in hypergraphs and uses set operations for efficient candidates generation. Moreover, we develop an optimised parallel execution engine in HGMatch based on the dataflow model, which features a task-based scheduler and fine-grained dynamic work stealing to achieve bounded memory execution and better load balancing. Experimental evaluation on 10 real-world datasets shows that HGMatch outperforms the extended version of the state-of-the-art subgraph matching algorithms (CFL, DAF, CECI and RapidMatch) by orders of magnitude when using a single thread, and achieves almost linear scalability when the number of threads increases.
-
Kongzhang Hao, Long Yuan, Zhengyi Yang, Wenjie Zhang, Xuemin Lin,
"Efficient and Scalable Distributed Graph Structural Clustering at Billion Scale",
Proceedings of the 28th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 234–251, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{hao2023efficient, address = {Cham}, author = {Kongzhang Hao and Long Yuan and Zhengyi Yang and Wenjie Zhang and Xuemin Lin}, booktitle = {Proceedings of the 28th International Conference on Database Systems for Advanced Applications (DASFAA)}, doi = {10.1007/978-3-031-30675-4_16}, pages = {234–251}, publisher = {Springer Nature Switzerland}, title = {Efficient and Scalable Distributed Graph Structural Clustering at Billion Scale}, url = {https://doi.org/10.1007/978-3-031-30675-4_16}, year = {2023} }Abstract
Structural Graph Clustering (SCAN) is a fundamental problem in graph analysis and has received considerable attention recently. Existing distributed solutions either lack efficiency or suffer from high memory consumption when addressing this problem in billion-scale graphs. Motivated by these, in this paper, we aim to devise a distributed algorithm for SCAN that is both efficient and scalable. We first propose a fine-grained clustering framework tailored for SCAN. Based on the new framework, we devise a distributed SCAN algorithm, which not only keeps a low communication overhead during execution, but also effectively reduces the memory consumption at all time. We also devise an effective workload balance mechanism that is automatically triggered by the idle machines to handle skewed workloads. The experiment results demonstrate the efficiency and scalability of our proposed algorithm.
-
Nimish Ukey, Zhengyi Yang*, Wenke Yang, Binghao Li, Runze Li,
"kNN Join for Dynamic High-Dimensional Data: A Parallel Approach",
Proceedings of the 34th edition of the Australasian Database Conference (ADC), pp. 3–16, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ukey2023knn, author = {Nimish Ukey and Zhengyi Yang* and Wenke Yang and Binghao Li and Runze Li}, booktitle = {Proceedings of the 34th edition of the Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-47843-7_1}, pages = {3–16}, publisher = {Springer}, title = {kNN Join for Dynamic High-Dimensional Data: A Parallel Approach}, url = {https://doi.org/10.1007/978-3-031-47843-7_1}, year = {2023} }Abstract
The k nearest neighbor (kNN) join operation is a fundamental task that combines two high-dimensional databases, enabling data points in the User dataset U to identify their k nearest neighbor points from the Item dataset I. This operation plays a crucial role in various domains, including knowledge discovery, data mining, similarity search applications, and scientific research. However, exact kNN search in high-dimensional spaces is computationally demanding, and existing sequential methods face challenges in handling large datasets. In this paper, we propose an efficient parallel solution for dynamic kNN join over high-dimensional data, leveraging the high-dimensional R tree (HDR Tree) for improved efficiency. Our solution harnesses the power of Simultaneous Multi- Threading (SMT) technologies and Single-Instruction-Multiple-Data (SIMD) instructions in modern CPUs for parallelisation. Importantly, our research is the first to introduce parallel computation for exact kNN join over high-dimensional data. Experimental results demonstrate that our proposed approach outperforms the sequential HDR Tree method by up to 1.2 times with a single thread. Moreover, our solution provides near-linear scalability as the number of threads increases.
-
Miao Ma, Zhengyi Yang*, Kongzhang Hao, Liuyi Chen, Chunling Wang, Yi Jin,
"An Empirical Analysis of Just-in-Time Compilation in Modern Databases",
Proceedings of the 34th edition of the Australasian Database Conference (ADC), pp. 227–240, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ma2023empirical, author = {Miao Ma and Zhengyi Yang* and Kongzhang Hao and Liuyi Chen and Chunling Wang and Yi Jin}, booktitle = {Proceedings of the 34th edition of the Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-47843-7_16}, pages = {227–240}, publisher = {Springer}, title = {An Empirical Analysis of Just-in-Time Compilation in Modern Databases}, url = {https://doi.org/10.1007/978-3-031-47843-7_16}, year = {2023} }Abstract
JIT (Just-in-Time) technology has garnered significant attention for improving the efficiency of database execution. It offers higher performance by eliminating interpretation overhead compared to traditional execution engines. LLVM serves as the primary JIT architecture, which was implemented in PostgreSQL since version 11. However, recent advancements in WASM-based databases, such as Mutable, present an alternative JIT approach. This approach minimizes the extensive engineering efforts associated with the execution engine and focuses on optimizing supported operators for lower latency and higher throughput. In this paper, we perform comprehensive experiments on these two representative open-source databases to gain deeper insights into the effectiveness of different JIT architectures.
-
Wenqian Zhang, Zhengyi Yang*, Dong Wen, Xiaoyang Wang,
"Efficient Distributed Core Graph Decomposition",
2023 IEEE International Conference on Data Mining Workshops (ICDMW), vol. , no. , pp. 1023–1031, 2023.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{zhang2023efficient, author = {Wenqian Zhang and Zhengyi Yang* and Dong Wen and Xiaoyang Wang}, booktitle = {2023 IEEE International Conference on Data Mining Workshops (ICDMW)}, doi = {10.1109/ICDMW60847.2023.00135}, number = {}, pages = {1023–1031}, title = {Efficient Distributed Core Graph Decomposition}, url = {https://dx.doi.org/10.1109/ICDMW60847.2023.00135}, volume = {}, year = {2023} }Abstract
Core decomposition is one of the most fundamental problems in graph analytics, which is associated with numerous applications, such as community detection, protein network analysis, and system structure analysis. As the sizes of graphs are becoming increasingly large, it is challenging to compute core decomposition on a single machine. In this paper, we study the problem of k-Core decomposition in the distributed environment. Specifically, we propose the distributed Filter-Array k-Core (FAkCore) algorithm, which adopts the commonly used Scatter-Gather framework. We design an auxiliary data structure of running counts for each vertex to track the statistics of its neighbors' core number. It allows us to recompute the core number of a vertex only when the value is updated. Together with an enhanced message filtering mechanism, our method significantly reduces redundant computation and communication in the existing distributed k-Core decomposition algorithm. Experiments on 10 real-world graphs show that our method outperforms the baseline algorithms by 1.4 times on average and up to 2.2 times.
2022
-
Weixiao Xu, Lin Sun, Cheng Zhen, Bo Liu, Zhengyi Yang, Wenke Yang,
"Deep Learning-Based Image Recognition of Agricultural Pests",
Applied Sciences, vol. 12, no. 24, 2022.
[link]
[bibtex]
[abstract]
Bibtex
@article{xu2022deep, author = {Weixiao Xu and Lin Sun and Cheng Zhen and Bo Liu and Zhengyi Yang and Wenke Yang}, doi = {10.3390/app122412896}, journal = {Applied Sciences}, number = {24}, title = {Deep Learning-Based Image Recognition of Agricultural Pests}, url = {https://www.mdpi.com/2076-3417/12/24/12896}, volume = {12}, year = {2022} }Abstract
Pests and diseases are an inevitable problem in agricultural production, causing substantial economic losses yearly. The application of convolutional neural networks to the intelligent recognition of crop pest images has become increasingly popular due to advances in deep learning methods and the rise of large-scale datasets. However, the diversity and complexity of pest samples, the size of sample images, and the number of examples all directly affect the performance of convolutional neural networks. Therefore, we designed a new target-detection framework based on Cascade RCNN (Regions with CNN features), aiming to solve the problems of large image size, many pest types, and small and unbalanced numbers of samples in pest sample datasets. Specifically, this study performed data enhancement on the original samples to solve the problem of a small and unbalanced number of examples in the dataset and developed a sliding window cropping method, which could increase the perceptual field to learn sample features more accurately and in more detail without changing the original image size. Secondly, combining the attention mechanism with the FPN (Feature Pyramid Networks) layer enabled the model to learn sample features that were more important for the current task from both channel and space aspects. Compared with the current popular target-detection frameworks, the average precision value of our model (mAP@0.5) was 84.16\%, the value of (mAP@0.5:0.95) was 65.23\%, the precision was 67.79\%, and the F1 score was 82.34\%. The experiments showed that our model solved the problem of convolutional neural networks being challenging to use because of the wide variety of pest types, the large size of sample images, and the difficulty of identifying tiny pests.
-
Xia Li, Kongzhang Hao, Zhengyi Yang, Xin Cao, Wenjie Zhang, Long Yuan, Xuemin Lin,
"Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs",
Proceedings of the 23rd International Conference on Web Information Systems Engineering (WISE), pp. 49–64, 2022.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{li2022hop, author = {Xia Li and Kongzhang Hao and Zhengyi Yang and Xin Cao and Wenjie Zhang and Long Yuan and Xuemin Lin}, booktitle = {Proceedings of the 23rd International Conference on Web Information Systems Engineering (WISE)}, doi = {10.1007/978-3-031-20891-1_5}, pages = {49–64}, publisher = {Springer}, title = {Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs}, url = {https://doi.org/10.1007/978-3-031-20891-1_5}, year = {2022} }Abstract
Hop-constrained s-t simple path (HC-s-tpath) enumeration is a fundamental problem in graph analysis. Existing solutions for this problem focus on unlabelled graphs and assume queries are issued without any label constraints. However, in many real-world applications, graphs are edge-labelled and the queries involve label constraints on the path connecting two vertices. Therefore, we study the problem of labelled hop-constrained s-t path (LHC-s-tpath) enumeration in this paper. We aim to efficiently enumerate the HC-s- tpaths using only edges with provided labels. To achieve this goal, we first demonstrate the existence of unnecessary computation specific to the label constraints in the state-of-the-art HC-s-tpath enumeration algorithm. We then devise a novel online index to identify the fruitless exploration during the enumeration. Based on the proposed index, we design an efficient LHC-s-tpath enumeration algorithm in which unnecessary computation is effectively pruned. Extensive experiments are conducted on real-world graphs with billions of edges. Experiment results show that our proposed algorithms significantly outperform the baseline methods by over one order of magnitude.
-
Nimish Ukey, Zhengyi Yang*, Guangjian Zhang, Boge Liu, Binghao Li, Wenjie Zhang,
"Efficient KNN Join Over Dynamic High-Dimensional Data",
Proceedings of the 33rd edition of the Australasian Database Conference (ADC), pp. 63–75, 2022.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ukey2022efficient, author = {Nimish Ukey and Zhengyi Yang* and Guangjian Zhang and Boge Liu and Binghao Li and Wenjie Zhang}, booktitle = {Proceedings of the 33rd edition of the Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-15512-3_5}, pages = {63–75}, publisher = {Springer}, title = {Efficient KNN Join Over Dynamic High-Dimensional Data}, url = {https://doi.org/10.1007/978-3-031-15512-3_5}, year = {2022} }Abstract
Given a user dataset U and an object dataset I in high-dimensional space, a kNN join query retrieves each object in dataset U its k nearest neighbors from the dataset I. kNN join is a fundamental and essential operation in applications from many domains such as databases, computer vision, multi-media, machine learning, recommendation systems, and many more. The datasets in real world often update dynamically on insertion or deletion of objects. However, existing algorithms of dynamic kNN join lack support for deletion and batch update, which are important in real-life applications. In this paper, we propose a new method of kNN join over dynamic high-dimensional data. Specifically, our method features lazy updates, batch operations, and optimised deletions. Experiments on real-world datasets show that our method outperforms the existing algorithms of naive RkNN join and HDR Tree by up to 5 and 4 times, respectively.
-
Xia Li, Kongzhang Hao, Zhengyi Yang, Xin Cao, Wenjie Zhang,
"Hop-Constrained s-t Simple Path Enumeration In Large Uncertain Graphs",
Proceedings of the 33rd edition of the Australasian Database Conference (ADC), pp. 115–127, 2022.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{li2022hop2, author = {Xia Li and Kongzhang Hao and Zhengyi Yang and Xin Cao and Wenjie Zhang}, booktitle = {Proceedings of the 33rd edition of the Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-15512-3_9}, pages = {115–127}, publisher = {Springer}, title = {Hop-Constrained s-t Simple Path Enumeration In Large Uncertain Graphs}, url = {https://doi.org/10.1007/978-3-031-15512-3_9}, year = {2022} }Abstract
Uncertain graphs are graphs where each edge is assigned with a probability of existence. In this paper, we study the problem of hop-constrained s-t simple path enumeration in large uncertain graphs. To the best of our knowledge, we are the first to study this problem in the literature. Specifically, we propose a light-weight index to prune candidate paths by adopting the concept of probability-constrained distance. An efficient enumeration algorithm is designed based on the index structure. Experiment results on real-world datasets show that our proposed methods significantly outperform the baseline methods by up to 6 times.
2021
-
Zhengyi Yang, Longbin Lai, Xuemin Lin, Kongzhang Hao, Wenjie Zhang,
"HUGE: An Efficient and Scalable Subgraph Enumeration System",
Proceedings of the 2021 International Conference on Management of Data (SIGMOD), pp. 2049–2062, 2021.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{yang2021huge, address = {New York, NY, USA}, author = {Zhengyi Yang and Longbin Lai and Xuemin Lin and Kongzhang Hao and Wenjie Zhang}, booktitle = {Proceedings of the 2021 International Conference on Management of Data (SIGMOD)}, doi = {10.1145/3448016.3457237}, pages = {2049–2062}, publisher = {Association for Computing Machinery}, series = {SIGMOD/PODS '21}, title = {HUGE: An Efficient and Scalable Subgraph Enumeration System}, url = {https://doi.org/10.1145/3448016.3457237}, year = {2021} }Abstract
Subgraph enumeration is a fundamental problem in graph analytics, which aims to find all instances of a given query graph on a large data graph. In this paper, we propose a system called HUGE to efficiently process subgraph enumeration at scale in the distributed context. HUGE features 1) an optimiser to compute an advanced execution plan without the constraints of existing works; 2) a hybrid communication layer that supports both pushing and pulling communication; 3) a novel two-stage execution mode with a lock-free and zero-copy cache design; 4) a BFS/DFS-adaptive scheduler to bound memory consumption; and 5) two-layer intra- and inter-machine load balancing. HUGE is generic such that all existing distributed subgraph enumeration algorithms can be plugged in to enjoy automatic speed up and bounded-memory execution.
-
Xin Jin, Zhengyi Yang, Xuemin Lin, Shiyu Yang, Lu Qin, You Peng,
"FAST: FPGA-based Subgraph Matching on Massive Graphs",
2021 IEEE 37th International Conference on Data Engineering (ICDE), vol. , no. , pp. 1452–1463, 2021.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{jin2021fast, author = {Xin Jin and Zhengyi Yang and Xuemin Lin and Shiyu Yang and Lu Qin and You Peng}, booktitle = {2021 IEEE 37th International Conference on Data Engineering (ICDE)}, doi = {10.1109/ICDE51399.2021.00129}, number = {}, pages = {1452–1463}, title = {FAST: FPGA-based Subgraph Matching on Massive Graphs}, url = {https://dx.doi.org/10.1109/ICDE51399.2021.00129}, volume = {}, year = {2021} }Abstract
Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments.
-
Shunyang Li, Zhengyi Yang, Xianhang Zhang, Wenjie Zhang, Xuemin Lin,
"SQL2Cypher: Automated Data and Query Migration from RDBMS to GDBMS",
Proceedings of the 22nd International Conference on Web Information Systems Engineering (WISE), pp. 510–517, 2021.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{li2021sql2cypher, author = {Shunyang Li and Zhengyi Yang and Xianhang Zhang and Wenjie Zhang and Xuemin Lin}, booktitle = {Proceedings of the 22nd International Conference on Web Information Systems Engineering (WISE)}, doi = {10.1007/978-3-030-91560-5_39}, pages = {510–517}, publisher = {Springer}, title = {SQL2Cypher: Automated Data and Query Migration from RDBMS to GDBMS}, url = {https://doi.org/10.1007/978-3-030-91560-5_39}, year = {2021} }Abstract
There are many real-world application domains where data can be naturally modelled as a graph, such as social networks and computer networks. Relational Database Management Systems (RDBMS) find it hard to capture the relationships and inherent graph structure of data and are inappropriate for storing highly connected data; thus, graph databases have emerged to address the challenges of high data connectivity. As the performance of querying highly connected data in relational query statements is usually worse than that in the graph database. Transforming data from a relational database to a graph database is imperative for improving the performance of graph queries. In this paper, we demonstrate SQL2Cypher, a system for migrating data from a relational database to a graph database automatically. This system also supports translating SQL queries into Cypher queries. SQL2Cypher is open-source (https://github.com/UNSW-database/SQL2Cypher) to allow researchers and programmers to migrate data efficiently. Our demonstration video can be found here: https://www.youtube.com/watch?v=eGaeBrVTJws.
2020
-
Ran Wang, Zhengyi Yang, Wenjie Zhang, Xuemin Lin,
"An Empirical Study on Recent Graph Database Systems",
Proceedings of the 14th International Conference on Knowledge Science, Engineering and Management (KSEM), pp. 328–340, 2020.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{wang2020empirical, address = {Berlin, Heidelberg}, author = {Ran Wang and Zhengyi Yang and Wenjie Zhang and Xuemin Lin}, booktitle = {Proceedings of the 14th International Conference on Knowledge Science, Engineering and Management (KSEM)}, doi = {10.1007/978-3-030-55130-8_29}, pages = {328–340}, publisher = {Springer}, title = {An Empirical Study on Recent Graph Database Systems}, url = {https://doi.org/10.1007/978-3-030-55130-8_29}, year = {2020} }Abstract
Graphs are widely used to model the intricate relationships among objects in a wide range of applications. The advance in graph data has brought significant value to artificial intelligence technologies. Recently, a number of graph database systems have been developed. In this paper, we present a comprehensive overview and empirical investigation on existing property graph database systems such as Neo4j, AgensGraph, TigerGraph and LightGraph (LightGraph has recently renamed to TuGraph.). These systems support declarative graph query languages. Our empirical studies are conducted in a single-machine environment against on the LDBC social network benchmark, consisting of three different large-scale datasets and a set of benchmark queries. This is the first empirical study to compare these graph database systems by evaluating data bulk importing and processing simple and complex queries. Experimental results provide insightful observations of various graph data systems and indicate that AgensGraph works well on SQL based workload and simple update queries, TigerGraph is powerful on complex business intelligence queries, Neo4j is user-friendly and suitable for small queries, and LightGraph is a more balanced product achieving good performance on different queries. The related code, scripts and data of this paper are available online (https://github.com/UNSW-database/GraphDB-Benchmark).
2019
-
Zhengmin Lai, Zhengyi Yang, Longbin Lai,
"Improving Distributed Subgraph Matching Algorithm on Timely Dataflow",
2019 IEEE 35th International Conference on Data Engineering Workshops (ICDEW), vol. , no. , pp. 266–273, 2019.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{lai2019improving, author = {Zhengmin Lai and Zhengyi Yang and Longbin Lai}, booktitle = {2019 IEEE 35th International Conference on Data Engineering Workshops (ICDEW)}, doi = {10.1109/ICDEW.2019.000-2}, number = {}, pages = {266–273}, title = {Improving Distributed Subgraph Matching Algorithm on Timely Dataflow}, url = {https://dx.doi.org/10.1109/ICDEW.2019.000-2}, volume = {}, year = {2019} }Abstract
The subgraph matching problem is defined to find all subgraphs of a data graph that are isomorphic to a given query graph. Subgraph matching plays a vital role in the fields of e-commerce, social media and biological science. CliqueJoin is a distributed subgraph matching algorithm that is designed to be efficient and scalable. However, CliqueJoin is originally developed on MapReduce, thus the performance of the algorithm can be affected by the notorious I/O issue of MapReduce while processing multi-round join tasks. Meanwhile, CliqueJoin does not propose a cost evaluation strategy for labelled graphs, which limits its application in practice where most real-world graphs are labelled. Targeting the limitations of CliqueJoin, we propose CliqueJoin++ to improve CliqueJoin in two aspects. Firstly, we implement CliqueJoin++ on the Timely dataflow system instead of MapReduce to avoid considerable I/O cost. Secondly, we extend the cost evaluation function in CliqueJoin to compute optimal join plans for labelled graphs in the distributed context. Extensive experiments have been conducted to show that the proposed method is up to 10 times faster than the MapReduce version for unlabelled matching, and it achieves good performance and scalability for labelled matching.
-
Longbin Lai, Zhu Qing, Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, Xuemin Lin, Lu Qin, Wenjie Zhang, Ying Zhang, Zhengping Qian, Jingren Zhou,
"Distributed Subgraph Matching on Timely Dataflow",
Proc. VLDB Endow. (VLDB), vol. 12, no. 10, pp. 1099–1112, June, 2019.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{lai2019distributed, author = {Longbin Lai and Zhu Qing and Zhengyi Yang and Xin Jin and Zhengmin Lai and Ran Wang and Kongzhang Hao and Xuemin Lin and Lu Qin and Wenjie Zhang and Ying Zhang and Zhengping Qian and Jingren Zhou}, booktitle = {Proc. VLDB Endow. (VLDB)}, doi = {10.14778/3339490.3339494}, month = {June}, number = {10}, pages = {1099–1112}, publisher = {VLDB Endowment}, title = {Distributed Subgraph Matching on Timely Dataflow}, url = {https://doi.org/10.14778/3339490.3339494}, volume = {12}, year = {2019} }Abstract
Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view of distributed subgraph matching mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art algorithms. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy- level comparison. Our implementation covers all representative algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.
-
Kongzhang Hao, Zhengyi Yang, Longbin Lai, Zhengmin Lai, Xin Jin, Xuemin Lin,
"PatMat: A Distributed Pattern Matching Engine with Cypher",
Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), pp. 2921–2924, 2019.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{hao2019patmat, address = {New York, NY, USA}, author = {Kongzhang Hao and Zhengyi Yang and Longbin Lai and Zhengmin Lai and Xin Jin and Xuemin Lin}, booktitle = {Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM)}, doi = {10.1145/3357384.3357840}, pages = {2921–2924}, publisher = {Association for Computing Machinery}, series = {CIKM '19}, title = {PatMat: A Distributed Pattern Matching Engine with Cypher}, url = {https://doi.org/10.1145/3357384.3357840}, year = {2019} }Abstract
Graph pattern matching is one of the most fundamental problems in graph database and is associated with a wide spectrum of applications. Due to its computational intensiveness, researchers have primarily devoted their efforts to improving the performance of the algorithm while constraining the graphs to have singular labels on vertices (edges) or no label. Whereas in practice graphs are typically associated with rich properties, thus the main focus in the industry is instead on powerful query languages that can express a sufficient number of pattern matching scenarios. We demo PatMat in this work to glue together the academic efforts on performance and the industrial efforts on expressiveness. To do so, we leverage the state-of-the-art join-based algorithms in the distributed contexts and Cypher query language - the most widely-adopted declarative language for graph pattern matching. The experiments demonstrate how we are capable of turning complex Cypher semantics into a distributed solution with high performance.