Zhengyi Yang's Publications
• SIGMOD (2) • VLDB (1) • ICDE (2) • WWW (3) • EDBT (1) • CIKM (2) • DASFAA (2) • WISE (2) • APWeb-WAIM (3) • ADMA (1) • KSEM (1) •
• Sorted by year • Journals • Conferences •
Journal Articles
-
Tianming Zhang, Renbo Zhang, Zhengyi Yang, Lu Chen, Yunjun Gao, Xiaochun Yang,
"TemsRoute: A temporally and socially aware routing framework for delay-tolerant networks",
Ad Hoc Networks, vol. 169, pp. 103755, 2025.
[link]
[bibtex]
[abstract]
Bibtex
@article{zhang2025temsroute, author = {Tianming Zhang and Renbo Zhang and Zhengyi Yang and Lu Chen and Yunjun Gao and Xiaochun Yang}, doi = {https://doi.org/10.1016/j.adhoc.2025.103755}, journal = {Ad Hoc Networks}, pages = {103755}, title = {TemsRoute: A temporally and socially aware routing framework for delay-tolerant networks}, url = {https://www.sciencedirect.com/science/article/pii/S1570870525000034}, volume = {169}, year = {2025} }Abstract
In the realm of delay-tolerant networks (DTNs), designing a routing strategy that optimizes relay vertex selection for faster message dissemination and lower network overhead is an important and challenging topic. DTNs inherently exhibit temporal variations, characterized by mobility and intermittent connectivity. In addressing this, in the paper, we model DTNs as temporal networks and propose a temporally and socially aware routing framework, called TemsRoute, which takes both the temporal betweenness centrality and the social information into consideration to intelligently identify optimal relay vertices. Within the TemsRoute, we devise exact and approximate heuristic sorting-based label propagation methods, together with two pruning lemmas, to efficiently compute the temporal betweenness centrality. We also introduce four metrics to calculate social relevance between pairs of vertices. Additionally, we explore how to incrementally update the approximate temporal betweenness centrality within the context of temporal graph streams. Extensive experiments conducted on real- world DTNs underscore the superior performance of TemsRoute. It achieves the highest message delivery rate and the lowest message average delay when compared to six other routing methods. This underscores the potential of TemsRoute to improve message dissemination efficiency in certain dynamic and challenging DTN scenarios, particularly those involving sporadic connectivity, frequent topology changes, and limited resources.
-
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, 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}, 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.
-
Jingtian Wei, Zhengyi Yang*, Qi Luo, Yu Zhang, Lu Qin, Wenjie Zhang,
"High-Order Local Clustering on Hypergraphs",
EAI Endorsed Transactions on Scalable Information Systems, vol. 11, no. 6, Nov., 2024.
[link]
[bibtex]
Bibtex
@article{wei2024high, author = {Jingtian Wei and Zhengyi Yang* and Qi Luo and Yu Zhang and Lu Qin and Wenjie Zhang}, doi = {10.4108/eetsis.7431}, journal = {EAI Endorsed Transactions on Scalable Information Systems}, month = {Nov.}, number = {6}, title = {High-Order Local Clustering on Hypergraphs}, url = {https://publications.eai.eu/index.php/sis/article/view/7431}, volume = {11}, year = {2024} } -
Nimish Ukey#, Guangjian Zhang#, Zhengyi Yang*, Binghao Li, Wei Li, Wenjie Zhang,
"Efficient continuous kNN join over dynamic high-dimensional data",
World Wide Web, 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}, 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.
-
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.
Conference Articles
-
Wenqian Zhang, Zhengyi Yang*, Dong Wen, Wentao Li, Wenjie Zhang, Xuemin Lin,
"Accelerating Core Decomposition in Billion-Scale Hypergraphs",
Proceedings of the ACM on Management of Data (SIGMOD), 2025.
[bibtex]
Bibtex
@inproceedings{zhang2025accelerating, author = {Wenqian Zhang and Zhengyi Yang* and Dong Wen and Wentao Li and Wenjie Zhang and Xuemin Lin}, booktitle = {Proceedings of the ACM on Management of Data (SIGMOD)}, title = {Accelerating Core Decomposition in Billion-Scale Hypergraphs}, year = {2025} } -
Kaiyu Chen, Dong Wen, Hanchen Wang, Zhengyi Yang, Wenjie Zhang, Xuemin Lin,
"Covering K-Cliques in Billion-Scale Graphs",
Proceedings of the ACM on Web Conference 2025 (WWW), 2025.
[bibtex]
Bibtex
@inproceedings{chen2025Efficient, author = {Kaiyu Chen and Dong Wen and Hanchen Wang and Zhengyi Yang and Wenjie Zhang and Xuemin Lin}, booktitle = {Proceedings of the ACM on Web Conference 2025 (WWW)}, title = {Covering K-Cliques in Billion-Scale Graphs}, year = {2025} } -
Boge Liu, Chunling Wang, Xiaoshuang Chen, Yu Hao, Zhengyi Yang*, Yi Jin, Yixing Yang, Wenke Yang, Wanchuan Zhang, Wenjie Zhang,
"PhoebeDB: A Disk-Based RDBMS Kernel for High-Performance and Cost-Effective OLTP",
International Conference on Extending Database Technology (EDBT), 2025.
[bibtex]
Bibtex
@inproceedings{liu2025phoebedb, author = {Boge Liu and Chunling Wang and Xiaoshuang Chen and Yu Hao and Zhengyi Yang* and Yi Jin and Yixing Yang and Wenke Yang and Wanchuan Zhang and Wenjie Zhang}, booktitle = {International Conference on Extending Database Technology (EDBT)}, title = {PhoebeDB: A Disk-Based RDBMS Kernel for High-Performance and Cost-Effective OLTP}, year = {2025} } -
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 ACM on Web Conference 2024 (WWW), pp. 2395–2406, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{zhang2024efficient, address = {New York, NY, USA}, 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 ACM on Web Conference 2024 (WWW)}, doi = {10.1145/3589334.3645438}, pages = {2395–2406}, publisher = {Association for Computing Machinery}, series = {WWW '24}, title = {Efficient Exact and Approximate Betweenness Centrality Computation for Temporal Graphs}, url = {https://doi.org/10.1145/3589334.3645438}, year = {2024} }Abstract
Betweenness centrality of a vertex in a graph evaluates how often the vertex occurs in the shortest paths. It is a widely used metric of vertex importance in graph analytics. While betweenness centrality on static graphs has been extensively investigated, many real-world graphs are time-varying and modeled as temporal graphs. Examples include social networks and telecommunication networks, where a relationship between two vertices occurs at a specific time. Hence, in this paper, we target efficient methods for temporal betweenness centrality computation. We firstly propose an exact algorithm with the new notion of time instance graph, based on which, we derive a temporal dependency accumulation theory for iterative computation. To reduce the size of the time instance graph and improve the efficiency, we propose an additional optimization, which compresses the time instance graph with equivalent vertices and edges, and extends the dependency theory to the compressed graph. Since it is theoretically complex to compute temporal betweenness centrality, we further devise a probabilistically guaranteed approximate method to handle massive temporal graphs. Extensive experimental results on real-world temporal networks demonstrate the superior performance of the proposed methods. In particular, our exact and approximate methods outperform the state- of-the-art methods by up to two and five orders of magnitude, respectively.
-
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 ACM on Web Conference 2024 (WWW), pp. 527–538, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{zhang2024tatkc, address = {New York, NY, USA}, author = {Tianming Zhang and Junkai Fang and Zhengyi Yang and Bin Cao and Jing Fan}, booktitle = {Proceedings of the ACM on Web Conference 2024 (WWW)}, doi = {10.1145/3589334.3645432}, pages = {527–538}, publisher = {Association for Computing Machinery}, series = {WWW '24}, title = {TATKC: A Temporal Graph Neural Network for Fast Approximate Temporal Katz Centrality Ranking}, url = {https://doi.org/10.1145/3589334.3645432}, year = {2024} }Abstract
Numerous real-world networks are represented as temporal graphs, which capture the dynamics of connections over time. Identifying important nodes on temporal graphs has a plethora of real-life applications, such as information propagation and influential user identification, etc. Temporal Katz centrality, a popular temporal metric, gauges the importance of nodes by taking into account both the number of temporal walks and the timespan between the interactions. The computation of traditional temporal Katz centrality is computationally expensive, especially when applied to massive temporal graphs. Therefore, in this paper, we design a temporal graph neural network to approximate temporal Katz centrality computation. To the best of our knowledge, we are the first to address temporal Katz centrality computation purely from a learning-based perspective. We propose a time-injected self- attention model that consists of two phases. In the first phase, we utilize a time-injected self-attention mechanism to acquire node representations that encompass both structural information and temporal relevance. The second phase is structured as a multi-layer perceptron (MLP) which uses the learned node representation to predict node rankings. Furthermore, normalization and neighbor sampling strategies are integrated into the model to enhance its overall performance. Extensive experiments on real-world networks demonstrate the efficiency and accuracy of TATKC.
-
Kaiyu Chen, Dong Wen, Wentao Li, Zhengyi Yang, Wenjie Zhang,
"On Compressing Historical Cliques in Temporal Graphs",
Database Systems for Advanced Applications (DASFAA), pp. 37–53, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{chen2024compressing, address = {Singapore}, author = {Kaiyu Chen and Dong Wen and Wentao Li and Zhengyi Yang and Wenjie Zhang}, booktitle = {Database Systems for Advanced Applications (DASFAA)}, doi = {10.1007/978-981-97-5552-3_3}, pages = {37–53}, publisher = {Springer Nature Singapore}, title = {On Compressing Historical Cliques in Temporal Graphs}, url = {https://doi.org/10.1007/978-981-97-5552-3_3}, year = {2024} }Abstract
Maximal clique is a fundamental cohesive subgraph model that plays an important role in many practical applications such as social network analysis and bioinformatics. Many real-world graphs change over time, with edges arriving continuously, and each edge has a timestamp representing the arrival time of that edge; such graphs are also known as temporal graphs. All maximal cliques in all snapshots since all possible historical moments are called historical cliques. Querying historical cliques has not been explored in existing research efforts. In this paper, we study the problem of compressing historical cliques in temporal graphs. We design a novel trie index structure called HC-Trie to compress historical cliques by exploiting the duration of historical cliques and the overlapping relationship between different historical cliques. We also propose an algorithm for maintaining the index when the graph changes. Experiments on real-world temporal graphs demonstrate that our solution achieves much faster query efficiency than the online solution and significantly less index space than the straightforward solution.
-
Wenke Yang, Zihan Yang, Liuyi Chen, Ruiqing Yan, Zhengyi Yang*, Linhan Zhang, Tang Yifu,
"Parallel Program Generation for Hybrid Tabular-Textual Question Answering",
Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM), pp. 121–137, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{yang2024parallel, address = {Singapore}, author = {Wenke Yang and Zihan Yang and Liuyi Chen and Ruiqing Yan and Zhengyi Yang* and Linhan Zhang and Tang Yifu}, booktitle = {Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM)}, doi = {10.1007/978-981-97-7232-2_9}, pages = {121–137}, publisher = {Springer Nature Singapore}, title = {Parallel Program Generation for Hybrid Tabular-Textual Question Answering}, url = {https://dx.doi.org/10.1007/978-981-97-7232-2_9}, year = {2024} }Abstract
Hybrid tabular-textual question answering (HTQA) involves tapping into a mosaic of data sources, traditionally managed through LSTM- based step-by-step reasoning, which has been vulnerable to exposure bias and subsequent error accumulation. This paper introduces an innovative parallel program generation method, ConcurGen, aiming to transform this paradigm by simultaneously formulating comprehensive program constructs that seamlessly blend operations and values. This approach not only rectifies the inherent pitfalls of sequential methodologies but also infuses efficiency into the process. When subjected to rigorous evaluation on benchmarks like the ConvFinQA and MultiHiertt datasets, our methodology showcased significant superiority over prevalent models such as FinQANet and MT2Net. This was evidenced by enhancements in various performance metrics, effectively raising the bar for what's deemed state-of-the-art. Notably, beyond setting these commendable benchmarks, our method facilitates a striking acceleration in program creation, achieving speeds nearly 21 times faster. Additionally, a salient feature of our approach becomes evident when numerical reasoning steps escalate: unlike traditional models, our system sustains its robust performance, emphasizing its adaptability and resilience in complex scenarios.
-
Yi Ding, Zhengyi Yang*, Shunyang Li, Liuyi Chen, Haoran Ning, Kongzhang Hao, Yongfei Liu,
"FGAQ: Accelerating Graph Analytical Queries Using FPGA",
Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM), pp. 357–361, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ding2024fgaq, address = {Singapore}, author = {Yi Ding and Zhengyi Yang* and Shunyang Li and Liuyi Chen and Haoran Ning and Kongzhang Hao and Yongfei Liu}, booktitle = {Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM)}, doi = {10.1007/978-981-97-7244-5_25}, pages = {357–361}, publisher = {Springer Nature Singapore}, title = {FGAQ: Accelerating Graph Analytical Queries Using FPGA}, url = {https://dx.doi.org/10.1007/978-981-97-7244-5_25}, year = {2024} }Abstract
Field-programmable gate arrays (FPGAs) have significant advantages in parallelism and energy efficiency over CPUs and GPUs and are widely deployed by many enterprises and cloud server providers nowadays. In this paper, we demonstrate FGAQ, an FPGA-based system for accelerating graph queries on massive graphs. FGAQ supports the two most fundamental types of graph queries, namely subgraph and path queries, and features 1) a CPU-FPGA co-designed framework, 2) a fully pipelined FPGA execution, and 3) reduced data transfer from FPGA's external memory. FGAQ provides a user-friendly interface and significantly improved performance. Performance evaluation shows that {\$}{\$}{\backslash}textsf{\{}FGAQ{\}}{\$}{\$}FGAQoutperforms the most popular graph database, Neo4j, by up to three orders of magnitude. The demo video can be found at https://www.youtube.com/watch?v=pEkzw{\_}DOQYE. -
Haoran Ning, Bocheng Han, Zhengyi Yang*, Kongzhang Hao, Miao Ma, Chunling Wang, Boge Liu, Xiaoshuang Cheng, Yu Hao, Yi Jin, Wanchun Zhang, Chengwei Zhang,
"Exploring Simple Architecture of Just-in-Time Compilation in Databases",
Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM), pp. 504–514, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ning2024exploring, address = {Singapore}, author = {Haoran Ning and Bocheng Han and Zhengyi Yang* and Kongzhang Hao and Miao Ma and Chunling Wang and Boge Liu and Xiaoshuang Cheng and Yu Hao and Yi Jin and Wanchun Zhang and Chengwei Zhang}, booktitle = {Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data (APWeb-WAIM)}, doi = {10.1007/978-981-97-7244-5_44}, pages = {504–514}, publisher = {Springer Nature Singapore}, title = {Exploring Simple Architecture of Just-in-Time Compilation in Databases}, url = {https://dx.doi.org/10.1007/978-981-97-7244-5_44}, year = {2024} }Abstract
Just-in-Time (JIT) compilation is an effective technique for enhancing query execution in modern relational databases, and it has gained increasing attention from academia and industry in recent years. However, the architectures of state-of-the-art JIT-based database systems are often complex, leading to challenges and limitations when adopted for commercial use. In this paper, we present an industrial view to JIT compilation for relational databases, emphasizing practicality and applicability. Our focus is on minimizing engineering effort, simplifying testing, and ensuring seamless integration with existing database ecosystems. We achieve these goals by adhering to three core principles: a simple, lightweight architecture; reuse of existing technologies and frameworks, particularly LLVM; and strong extensibility and compatibility. We demonstrate the feasibility and potential of this approach through an initial exploration using LLVM's mature JIT compilation capabilities to translate TPC-H database queries into optimized machine code. This proof-of-concept implementation shows the promise of our approach, pivoting the way for a comprehensive database system that leverages a lightweight yet powerfu JIT compilation framework for real-world applications.
-
Haonan Yan, Zhengyi Yang*, Tianming Zhang, Dong Wen, Qi Luo, Nimish Ukey,
"Approximating Temporal Katz Centrality with Monte Carlo Methods",
Web and Big Data. APWeb-WAIM 2024 International Workshops, pp. 3–16, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{yan2024approximating, address = {Singapore}, author = {Haonan Yan and Zhengyi Yang* and Tianming Zhang and Dong Wen and Qi Luo and Nimish Ukey}, booktitle = {Web and Big Data. APWeb-WAIM 2024 International Workshops}, doi = {https://doi.org/10.1007/978-981-96-0055-7_1}, pages = {3–16}, publisher = {Springer Nature Singapore}, title = {Approximating Temporal Katz Centrality with Monte Carlo Methods}, url = {https://dx.doi.org/https://doi.org/10.1007/978-981-96-0055-7_1}, year = {2024} }Abstract
Graphs have long served as fundamental data models across various disciplines such as data mining, social media analysis, and knowledge management. In real-world applications, interactions between nodes often evolve over time, necessitating the use of temporal graphs. Centrality measures are pivotal in graph analysis for identifying key nodes. Specifically, Temporal Katz Centrality (TKC) has garnered significant attention in recent years for its ability to measure node influence in temporal graphs. TKC evaluates the influence of nodes by considering all walks originating from a node, where contributions are weighted based on a user-specified time decay factor. This approach captures temporal dynamics by incorporating both the timing of interactions and the intervals between them, offering a comprehensive assessment of node importance over time. However, computing TKC in large temporal graphs is computationally intensive due to the requirement to traverse all edges and update centrality values along temporal paths. To address this challenge, this paper proposes an efficient Monte Carlo approximation method for TKC. This approach employs random sampling via Simple Random Walk and Alpha Walk to estimate TKC values. The paper rigorously proves the asymptotic consistency of the method using the Law of Large Numbers and Central Limit Theorem, ensuring that estimated TKC values converge to true TKC values as the sample size increases. Experiments conducted on six real-world temporal graph datasets demonstrate the effectiveness of the proposed approximation methods. Under the same running time, the Alpha walk outperforms other methods on large temporal graphs, exhibiting the lowest mean relative error and highest precision.
-
Diya Yan, Riza Yosia Sunindijo, Cynthia C Wang, Zhengyi Yang,
"Comparing the Career Paths of Male and Female Managers in the Construction Industry: Insights from LinkedIn Data",
Proceedings 40th Annual ARCOM Conference, pp. 247–256, September 2--4, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{yan2024comparing, address = {London South Bank University, UK}, author = {Diya Yan and Riza Yosia Sunindijo and Cynthia C Wang and Zhengyi Yang}, booktitle = {Proceedings 40th Annual ARCOM Conference}, editor = {Thomson, C. and Neilson, C. J.}, month = {September 2--4}, organization = {Association of Researchers in Construction Management}, pages = {247–256}, title = {Comparing the Career Paths of Male and Female Managers in the Construction Industry: Insights from LinkedIn Data}, url = {http://www.arcom.ac.uk/-docs/proceedings/1c4a060eab6e32fb9bf2c36acbd6093c.pdf}, year = {2024} }Abstract
As one of the most male-dominated industries, the construction industry in Australia is known for the low representation of women in the workforce. Previous studies have indicated that women face significant obstacles in their career developments, progressing more slowly than their male counterparts and struggling to attain managerial positions. Building on past research, this research compares the differences between the career paths of male and female managers in construction to understand key factors contributing to gender disparities in career progression. Based on an examination of the LinkedIn profiles of 480 managerial level employees from 61 companies, this research leveraged the rich dataset provided by the world's largest professional network, LinkedIn, to examine these key factors, such as educational backgrounds, years of experience, job titles, career transitions, and network sizes. This research contributes to existing literatures on gender disparities in leadership roles within the construction industry. By utilising LinkedIn data, which reflect the lived experiences of managers, this research provides empirical evidence that can inform policymaking, talent management, and diversity initiatives aimed at narrowing the gender gap in construction leadership.
-
Qi Luo, Wenjie Zhang, Zhengyi Yang, Dong Wen, Xiaoyang Wang, Dongxiao Yu, Xuemin Lin,
"Hierarchical Structure Construction on Hypergraphs",
Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM), pp. 1597–1606, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{qi2024hierarchical, address = {New York, NY, USA}, author = {Qi Luo and Wenjie Zhang and Zhengyi Yang and Dong Wen and Xiaoyang Wang and Dongxiao Yu and Xuemin Lin}, booktitle = {Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM)}, doi = {10.1145/3627673.3679765}, pages = {1597–1606}, publisher = {Association for Computing Machinery}, series = {CIKM '24}, title = {Hierarchical Structure Construction on Hypergraphs}, url = {https://doi.org/10.1145/3627673.3679765}, year = {2024} }Abstract
Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual- layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large- sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.
-
Nimish Ukey#, Guangjian Zhang#, Zhengyi Yang*, Xiaoyang Wang, Binghao Li, Serkan Saydam, Wenjie Zhang,
"A Cluster-Based Approach to kNN Join over Batch-Dynamic High-Dimensional Data",
International Conference Advanced Data Mining and Applications (ADMA), pp. 81–96, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ukey2024cluster, address = {Singapore}, author = {Nimish Ukey# and Guangjian Zhang# and Zhengyi Yang* and Xiaoyang Wang and Binghao Li and Serkan Saydam and Wenjie Zhang}, booktitle = {International Conference Advanced Data Mining and Applications (ADMA)}, doi = {10.1007/978-981-96-0814-0_6}, pages = {81–96}, publisher = {Springer Nature Singapore}, title = {A Cluster-Based Approach to kNN Join over Batch-Dynamic High-Dimensional Data}, url = {https://dx.doi.org/10.1007/978-981-96-0814-0_6}, year = {2024} }Abstract
The k nearest neighbors (kNN) join is a crucial operation in data mining, retrieving the kNN for each point in the query set within an answer set. This operation finds extensive applications in various domains, including recommendation systems, spatial databases, and knowledge discovery. With the surge in data volume and dimensionality, numerous approaches have emerged to enhance the efficiency of kNN join operations on static and dynamic high- dimensional data. However, we observed that research on batch- dynamic kNN join, where updates occur in batches rather than individually, remains scarce. To bridge this gap, we propose a novel cluster-based approach tailored for batch-dynamic kNN join over high-dimensional data. Our contributions include a cluster-based batch update technique, which efficiently processes similar updates in clusters, and a cluster-based pruning method using the high- dimensional R-tree (HDR-Tree) for optimised search during updates. Extensive experimental evaluations across 6 real-world datasets demonstrate the efficiency of our approach, significantly outperforming state-of-the-art methods by 19 to 55 times.
-
Zhuoqing Xu, Zhengyi Yang, Xiaoshuang Chen, Huangleshuai He, Xin Cao,
"Efficient Answering of k-Reachability on Temporal Bipartite Graphs",
Australasian Database Conference (ADC), pp. 224–238, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{xu2024efficient, address = {Singapore}, author = {Zhuoqing Xu and Zhengyi Yang and Xiaoshuang Chen and Huangleshuai He and Xin Cao}, booktitle = {Australasian Database Conference (ADC)}, doi = {10.1007/978-981-96-1242-0_17}, pages = {224–238}, publisher = {Springer Nature Singapore}, title = {Efficient Answering of k-Reachability on Temporal Bipartite Graphs}, url = {https://dx.doi.org/10.1007/978-981-96-1242-0_17}, year = {2024} }Abstract
This paper investigates the k-reachability problem on temporal bipartite graphs, which determines whether a vertex can reach another vertex within a given time interval I and a step constraint k. The problem is motivated by real-world scenarios where the number of hops from a source vertex s to a target vertex t reflects the influence s exerts on t. Bipartite graphs are used to model relationships between two types of entities, such as people- location, author-paper, and customer-product. When modeling real- world applications like disease outbreaks, biomedical reactions, and travel planning, edges are often enriched with temporal information. Temporal bipartite graphs provide an effective tool for modeling these dynamic scenarios. Recent studies show that k-reachability on temporal bipartite graphs can expand research in the above fields. Adding a step constraint k provides more insights into the connectivity of temporal bipartite graphs. Although k-reachability has been extensively studied on unipartite graphs, it remains unexplored on temporal bipartite graphs. To fill this research gap, we propose an efficient algorithm for k-reachability problem on temporal bipartite graphs in this paper. Specifically, we introduce a 2-hop index-based approach to efficiently answer k-reachability queries. Extensive experiments on real-world datasets demonstrate that the proposed method achieves a speedup of at least three orders of magnitude in query performance.
-
Xia Li, Zhengyi Yang, Kongzhang Hao, Xin Shu, Xin Cao, Wenjie Zhang,
"Distributed Hop-constrained s-t Simple Path Enumeration in Labelled Graphs",
Australasian Database Conference (ADC), pp. 265–278, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{li2024distributed, address = {Singapore}, author = {Xia Li and Zhengyi Yang and Kongzhang Hao and Xin Shu and Xin Cao and Wenjie Zhang}, booktitle = {Australasian Database Conference (ADC)}, doi = {10.1007/978-981-96-1242-0_20}, pages = {265–278}, publisher = {Springer Nature Singapore}, title = {Distributed Hop-constrained s-t Simple Path Enumeration in Labelled Graphs}, url = {https://dx.doi.org/10.1007/978-981-96-1242-0_20}, year = {2024} }Abstract
Hop-constrained s-t simple path (HC-s-t path) enumeration is a core problem in graph analysis, commonly applied to unlabelled graphs without considering label constraints. However, in many practical scenarios, graphs are edge-labelled, requiring queries to satisfy specific label constraints on the paths between vertices. This introduces new computational challenges that traditional HC-s-t path algorithms are not equipped to handle, especially in distributed environments dealing with large-scale graphs. To address these challenges, we propose a distributed algorithm for labelled hop- constrained s-t path (LHC-s-t path) enumeration. Our approach introduces an online label-based index to prune unnecessary computations, reducing both redundant processing and communication overhead. This enables efficient LHC-s-t path enumeration across distributed systems. Extensive experiments on large real-world graphs demonstrate that our algorithm significantly outperforms existing methods, achieving over an order of magnitude improvement in performance and scalability.
-
Yi Ding, Hualong Lin, Zhengyi Yang*, Dong Wen, Xiaoyang Wang, Wenjie Zhang,
"Benchmarking RDF Systems on the CloudAn Experimental Comparison of RDF Systems on Cloud",
Australasian Database Conference (ADC), pp. 30–43, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{ding2024benchmarking, address = {Singapore}, author = {Yi Ding and Hualong Lin and Zhengyi Yang* and Dong Wen and Xiaoyang Wang and Wenjie Zhang}, booktitle = {Australasian Database Conference (ADC)}, doi = {10.1007/978-981-96-1242-0_3}, pages = {30–43}, publisher = {Springer Nature Singapore}, title = {Benchmarking RDF Systems on the CloudAn Experimental Comparison of RDF Systems on Cloud}, url = {https://dx.doi.org/10.1007/978-981-96-1242-0_3}, year = {2024} }Abstract
With the growing use of graph-based applications across various domains, the demand for efficient and scalable RDF (Resource Description Framework) systems has intensified. As organizations increasingly deploy RDF systems on cloud infrastructures, understanding the trade-offs between performance and cost becomes critical. This paper presents a comprehensive experimental comparison of multiple RDF systems, analyzing their performance in cloud and on-premises environments. Our study evaluates key metrics such as query execution time, data ingestion speed, storage efficiency, and cost-effectiveness across several benchmarks, including LDBC SNB, WatDiv, LUBM, and DBpedia. The experiments reveal distinct advantages and limitations in RDF systems. Notably, Virtuoso demonstrated strong performance and cost-efficiency across most datasets, while systems like gStore exhibited higher variability under stress conditions. Our findings offer actionable insights for practitioners seeking to balance performance and cost when deploying RDF systems in cloud environments. We also highlight areas for improvement in system documentation, compatibility, and stability under extreme workloads. Future work will explore alternative architectures and further optimization strategies for cloud-based RDF solutions. The related code, scripts and data of this paper are available online (https://github.com/unswdb/RDF_on_Cloud).
-
Jiaxuan Wu, Xushuo Tang, Zhengyi Yang*, Kongzhang Hao, Longbin Lai, Yongfei Liu,
"An Experimental Evaluation of LLM on Image Classification",
Australasian Database Conference (ADC), pp. 506–518, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{wu2024experimental, address = {Singapore}, author = {Jiaxuan Wu and Xushuo Tang and Zhengyi Yang* and Kongzhang Hao and Longbin Lai and Yongfei Liu}, booktitle = {Australasian Database Conference (ADC)}, doi = {10.1007/978-981-96-1242-0_37}, pages = {506–518}, publisher = {Springer Nature Singapore}, title = {An Experimental Evaluation of LLM on Image Classification}, url = {https://dx.doi.org/10.1007/978-981-96-1242-0_37}, year = {2024} }Abstract
Image classification is one of the fundamental tasks in computer vision (CV) and has numerous practical applications. Traditionally, machine learning and deep learning methods such as k-Nearest Neighbors (kNN), decision trees, and Convolutional Neural Networks (CNN) have been widely used to perform this task. However, with the recent emergence of large language models (LLMs), such as Generative Pre-trained Transformers (GPT), originally designed for natural language processing, their cross-domain applications, including in CV, are now being explored. In this paper, we investigate the capabilities of GPT-4o, a variant of the GPT model, for image classification on the Fashion-MNIST dataset. By using carefully designed prompts, we evaluate GPT-4o's performance and compare it with more traditional models. Our study offers insights into the cross-domain potential of GPT models, explores how prompt engineering can enhance GPT's performance on image classification tasks, and suggests new avenues for developing more flexible and adaptable multimodal LLM systems. The code can be found at https://github.com/Tanghaha1424/gpt-fashionmnist.
-
Xiao Li, Yanping Wu, Xiaoyang Wang, Zhengyi Yang, Wenjie Zhang, Ying Zhang,
"Keyword-based Betweenness Centrality Maximization in Attributed Graphs",
Australasian Database Conference (ADC), pp. 209–223, 2024.
[link]
[bibtex]
[abstract]
Bibtex
@inproceedings{li2024keyword, address = {Singapore}, author = {Xiao Li and Yanping Wu and Xiaoyang Wang and Zhengyi Yang and Wenjie Zhang and Ying Zhang}, booktitle = {Australasian Database Conference (ADC)}, doi = {10.1007/978-981-96-1242-0_16}, pages = {209–223}, publisher = {Springer Nature Singapore}, title = {Keyword-based Betweenness Centrality Maximization in Attributed Graphs}, url = {https://dx.doi.org/10.1007/978-981-96-1242-0_16}, year = {2024} }Abstract
Betweenness centrality is a key concept in graph analysis that measures the significance of a node by counting how often it appears in the shortest paths between other nodes. The task of betweenness centrality maximization, which seeks to identify a set of nodes with the highest centrality scores, is crucial in various real-world applications. Most existing studies about betweenness centrality focus on general graphs. However, in reality, users in networks are usually associated with attributes such as preferences, which play an essential role in analyzing the properties of networks. Therefore, the traditional betweenness centrality is not applicable to the attribute graphs. Motivated by this, we propose a novel concept called Keyword-based Betweenness Centrality (KBC), which quantifies the number of times each node acts as the midpoint of shortest paths between nodes having one of the given attributes. Given an attribute graph G, a query attribute set Q, and a positive integer k, in this paper, we aim to find a node set of size no larger than k so that its KBC value based on Q is maximized. To address this problem, we propose a keyword-based hyper-edge sampler and devise an algorithm achieving the approximation guarantee of {\$}{\$}(1-1/e-{\backslash}epsilon ){\$}{\$}(1-1/e-ϵ)with at least 1-{\$}{\$}{\backslash}delta {\$}{\$}$\delta$probability. Extensive experiments on four real networks demonstrate the efficiency and effectiveness of our proposed algorithms. -
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",
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 = {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",
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 = {Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-47843-7_1}, pages = {3–16}, publisher = {Springer Nature Switzerland}, 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",
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 = {Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-47843-7_16}, pages = {227–240}, publisher = {Springer Nature Switzerland}, 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.
-
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",
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 = {Web Information Systems Engineering (WISE)}, doi = {10.1007/978-3-031-20891-1_5}, pages = {49–64}, publisher = {Springer International Publishing}, 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",
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 = {Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-15512-3_5}, pages = {63–75}, publisher = {Springer International Publishing}, 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",
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 = {Australasian Database Conference (ADC)}, doi = {10.1007/978-3-031-15512-3_9}, pages = {115–127}, publisher = {Springer International Publishing}, 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.
-
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",
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 = {Web Information Systems Engineering (WISE)}, doi = {10.1007/978-3-030-91560-5_39}, pages = {510–517}, publisher = {Springer International Publishing}, 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.
-
Ran Wang, Zhengyi Yang, Wenjie Zhang, Xuemin Lin,
"An Empirical Study on Recent Graph Database Systems",
13th International Conference 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 = {13th International Conference Knowledge Science, Engineering and Management (KSEM)}, doi = {10.1007/978-3-030-55130-8_29}, pages = {328–340}, publisher = {Springer International Publishing}, 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).
-
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, 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}, 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.