Shixuan Sun

Email Address
dcssuns@nus.edu.sg


Organizational Units
OrgUnit Logo
Organizational Unit
COMPUTING
faculty
OrgUnit Logo
Organizational Unit
OrgUnit Logo
Organizational Unit
OrgUnit Logo
Organizational Unit

Filters

20212
Reset filters

Settings

Citations

Publication Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Publication
    PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration
    (ACM, 2021-01-01) Sun, S; Chen, Y; He, B; Hooi, B; Assoc Prof Bingsheng He; DEPARTMENT OF COMPUTER SCIENCE; CIVIL AND ENVIRONMENTAL ENGINEERING; DEAN'S OFFICE (SCHOOL OF COMPUTING)
    We study the hop-constrained s-t path enumeration (HcPE ) problem, which takes a graph G, two distinct vertices s,t and a hop constraint k as input, and outputs all paths from s to t whose length is at most k. The state-of-the-art algorithms suffer from severe performance issues caused by the costly pruning operations during enumeration for the workloads with the large search space. Consequently, these algorithms hardly meet the real-time constraints of many online applications. In this paper, we propose PathEnum, an efficient index-based algorithm towards real-time HcPE. For an input query, PathEnum first builds a light-weight index aiming to reduce the number of edges involved in the enumeration, and develops efficient index-based approaches for enumeration, one based on depth-first search and the other based on joins. We further develop a query optimizer based on a join-based cost model to optimize the search order. We conduct experiments with 15 real-world graphs. Our experiment results show that PathEnum outperforms the state-of-the-art approaches by orders of magnitude in terms of the query time, throughput and response time.
  • No Thumbnail Available
    Publication
    Efficient Deep Learning Pipelines for Accurate Cost Estimations over Large Scale Query Workload
    (ACM, 2021-01-01) Zhi Kang, JK; Gaurav; Tan, SY; Cheng, F; Sun, S; He, B; Assoc Prof Bingsheng He; DEPARTMENT OF COMPUTER SCIENCE; DEAN'S OFFICE (SCHOOL OF COMPUTING)
    The use of deep learning models for forecasting the resource consumption patterns of SQL queries have recently been a popular area of study. While these models have demonstrated promising accuracy, training them over large scale industry workloads are expensive. Space inefficiencies of encoding techniques over large numbers of queries and excessive padding used to enforce shape consistency across diverse query plans implies 1) longer model training time and 2) the need for expensive, scaled up infrastructure to support batched training. In turn, we developed Prestroid, a tree convolution based data science pipeline that accurately predicts resource consumption patterns of query traces, but at a much lower cost. We evaluated our pipeline over 19K Presto OLAP queries, on a data lake of more than 20PB of data from Grab. Experimental results imply that our pipeline outperforms benchmarks on predictive accuracy, contributing to more precise resource prediction for large-scale workloads, yet also reduces per-batch memory footprint by 13.5x and per-epoch training time by 3.45x. We demonstrate direct cost savings of up to 13.2x for large batched model training over Microsoft Azure VMs.