특별세션II - Top Conference

  • 홈ˆ
  • 행사안내
  • 특별세션II - Top Conference

한국정보과학회가 선정한 SW분야 최우수학술대회에서 발표된 논문의 저자를 초청하여, 핵심연구내용 소개와 질의응답을 통해 학생들의 연구의욕을 고취하는 프로그램을 마련하였습니다. 관심 있는 분들의 많은 참여 바랍니다.

▣ 일시 : 7.3(금) 13:00~15:30
특별세션II는 ZOOM 실시간 중계를 통해 방송됩니다.
등록자는 온라인컨퍼런스 페이지를 통해 접속하실 수 있습니다.

 

Top Conference 1 - 차세대 컴퓨터(Next Generation Computer) 세션                            좌장 : 권미령 박사(KAIST)

no

분과

학술대회

논문제목

발표자

지도교수

1

컴퓨터시스템

RTSS2019

Conditionally Optimal Task Parallelization for Global EDF on Multi-core Systems

조영은
(서울대)

이창건
(서울대)

2

DAC 2019

GATE: A Generalized Dataflow-level Approximation Tuning Engine For Data Parallel Architectures

강석원
(한양대)

박영준
(한양대)

3

NSDI 2019

JANUS: Fast and Flexible Deep Learning via Symbolic Graph Execution of Imperative Programs

정은지
(서울대)

전병곤
(서울대)

4

ISCA 2020

A Case for Hardware-Based Demand Paging

이규선
(성균관대)

정진규
(성균관대)

5

RTAS 2020

Real-Time Object Detection System with Multi-Path Neural Networks

허선영
(포항공대)

김한준
(연세대)

6

FAST 2020

DC-Store: Eliminating Noisy Neighbor Containers using Deterministic I/O Performance and Resource Isolation

권미령
(KAIST)

정명수
(KAIST)

7

EuroSys 2020

AniFilter: Parallel and Failure-Atomic Cuckoo Filter for Non-Volatile Memories

오형준
(한양대)

서지원
(한양대)

 

Top Conference 2 - 차세대 소프트웨어(Next Generation Software) 세션                     좌장 : 김윤호 교수(KAIST)

no

분과

학술대회

논문제목

발표자

지도교수

1

소프트웨어공학

ICSE 2019

Concolic Testing for High Test Coverage and Reduced Human Effort in Automotive Industry

김윤호
(KAIST)

김문주
(KAIST)

2

ESEC/FSE 2019

Target-driven compositional concolic testing with function summary refinement for effective bug detection

김윤호
(KAIST)

김문주
(KAIST)

3

프로그래밍언어

OOPSLA 2019

Automatic and Scalable Detection of Logical Errors in Functional Programming Assignments

송도원
(고려대)

오학주
(고려대)

4

ICSE 2020

SAVER: Scalable, Precise, and Safe Memory-Error Repair

홍성준
(고려대)

오학주
(고려대)

5

S&P 2020

VeriSmart: A Highly Precise Safety Verifier for Ethereum Smart Contracts

소순범
(고려대)

오학주
(고려대)

 

Top Conference 3 - 차세대 빅데이터(Next Generation BigData) 세션                  좌장 : 김현지 박사(포항공대)

no

분과

학술대회

논문제목

발표자

지도교수

1

데이터베이스

ICDE 2020

D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

장준기
(서울대)

강유
(서울대)

2

SIGMOD 2020

G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching

박연수
(포항공대)

한욱신
(포항공대)

3

VLDB 2020

Natural language to SQL: Where are we today?

김현지
(포항공대)

한욱신
(포항공대)

4

WWW'20

TRAP: Two-level Regularized Autoencoder-based Embedding for Power-law Distributed Data

박동민
(KAIST)

이재길
(KAIST)

5

USENIX ATC'19

Pre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines

이은재
(UNIST)

서지원
(한양대)
노삼혁
(UNIST)

6

VLDB 2020

IDAR: Fast Supergraph Search Using DAG Integration

김현준
(서울대)

박근수
(서울대)

 

[컴퓨터시스템]

논문제목 : Conditionally Optimal Task Parallelization for Global EDF on Multi-core Systems

저자 : Youngeun Cho, Do Hyung Kim, Daechul Park, Seung Su Lee, Chang-Gun Lee(Seoul National University)

학술대회 : RTSS 2019

발표자 : 조영은(서울대)

지도교수 : 이창건(서울대)

논문초록 : Targeting global EDF scheduling, this paper proposes a conditionally optimal algorithm for parallelizing tasks with parallelization freedom. For this, we extend the interference-based sufficient schedulability analysis and derive monotonic increasing properties of both tolerance and interference for the schedulability. Leveraging those properties, we propose a one-way search based conditionally optimal algorithm with polynomial time complexity. Our extensive experiments through both simulation and actual implementation show that our proposed approach can significantly improve the schedulability up to 60 percent.

논문제목 : GATE: A Generalized Dataflow-level Approximation Tuning Engine For Data Parallel Architectures

저자 : Seokwon Kang, Yongseung Yu(Hanyang University), Jiho Kim(KAIST), Yongjun Park(Hanyang University)

학술대회 : DAC 2019

발표자 : 강석원(한양대)

지도교수 : 박영준(한양대)

논문초록 : Although approximate computing is widely used, it requires substantial programming effort to find appropriate approximation patterns among multiple pre-defined patterns to achieve a high performance. Therefore, we propose an automatic approximation framework called GATE to uncover hidden opportunities from any data-parallel program regardless of the code pattern or application characteristics using two compiler techniques, namely subgraph-level approximation (SGLA) and approximate thread merge (ATM). GATE also features conservative/aggressive tuning and dynamic calibration to maximize the performance while maintaining the TOQ level during runtime. Our framework achieves an average performance gain of 2.54x over the baseline with minimum accuracy loss.

논문제목 : JANUS: Fast and Flexible Deep Learning via Symbolic Graph Execution of Imperative Programs

저자 : Eunji Jeong, Sungwoo Cho, Gyeong-In Yu, Joo Seong Jeong, Dong-Jin Shin, Byung-Gon Chun(Seoul National University)

학술대회 : NSDI 2019

발표자 : 정은지(서울대)

지도교수 : 전병곤(서울대)

논문초록 : The rapid evolution of deep neural networks is demanding deep learning (DL) frameworks not only to satisfy the requirement of quickly executing large computations, but also to support straightforward programming models for quickly implementing and experimenting with complex network structures. However, existing frameworks fail to excel in both departments simultaneously, leading to diverged efforts for optimizing performance and improving usability.
This paper presents JANUS, a system that combines the advantages from both sides by transparently converting an imperative DL program written in Python, the de-facto scripting language for DL, into an efficiently executable symbolic dataflow graph. JANUS can convert various dynamic features of Python, including dynamic control flow, dynamic types, and impure functions, into the symbolic graph operations. Experiments demonstrate that JANUS can achieve fast DL training by exploiting the techniques imposed by symbolic graph-based DL frameworks, while maintaining the simple and flexible programmability of imperative DL frameworks at the same time.

논문제목 : A Case for Hardware-Based Demand Paging

저자 : Gyusun Lee(Sungkyunkwan University), Wenjing Jin(Seoul National University), Wonsuk Song(Sungkyunkwan University), Jeonghun Gong, Jonghyun Bae, Tae Jun Ham, Jae W. Lee(Seoul National University), Jinkyu Jeong(Sungkyunkwan University)

학술대회 : ISCA 2020

발표자 : 이규선(성균관대)

지도교수 : 정진규(성균관대)

논문초록 : The virtual memory system is pervasive in today’s computer systems, and demand paging is the key enabling mechanism for it. At a page miss, the CPU raises an exception, and the page fault handler is responsible for fetching the requested page from the disk. The OS typically performs a context switch to run other threads as traditional disk access is slow. However, with the widespread adoption of high-performance storage devices, such as low-latency solid-state drives (SSDs), the traditional OS-based demand paging is no longer effective because a considerable portion of the demand paging latency is now spent inside the OS kernel. Thus, this paper makes a case for hardware-based demand paging that mostly eliminates OS involvement in page miss handling to provide a near-disk-access-time latency for demand paging. To this end, two architectural extensions are proposed: LBA-augmented page table that moves I/O stack operations to the control plane and Storage Management Unit that enables CPU to directly issue I/O commands without OS intervention in most cases. OS support is also proposed to detach tasks for memory resource management from the critical path. The evaluation results using both a cycle-level simulator and a real x86 machine with an ultra-low latency SSD show that the proposed scheme reduces the demand paging latency by 37.0%, and hence improves the performance of FIO read random benchmark by up to 57.1% and a NoSQL server by up to 27.3% with real-world workloads. As a side effect of eliminating OS intervention, the IPC of the user-level code is also increased by up to 7.0%.

논문제목 : Real-Time Object Detection System with Multi-Path Neural Networks

저자 : Seonyeong Heo, Sungjun Cho(POSTECH), Youngsok Kim, Hanjun Kim(Yonsei University)

학술대회 : RTAS 2020

발표자 : 허선영(포항공대)

지도교수 : 김한준(연세대)

논문초록 : Thanks to the recent advances in Deep Neural Networks (DNNs), DNN-based object detection systems becomes highly accurate and widely used in real-time environments such as autonomous vehicles, drones and security robots. Although the systems should detect objects within a certain time limit that can vary depending on their execution environments such as vehicle speeds, existing systems blindly execute the entire long- latency DNNs without reflecting the time-varying time limits, and thus they cannot guarantee real-time constraints. This work proposes a novel real-time object detection system that employs multi-path neural networks based on a new worst-case execution time (WCET) model for DNNs on a GPU. This work designs the WCET model for a single-layer of DNNs analyzing processor and memory contention on GPUs, and extends the WCET model to the end-to-end networks. This work also designs the multi- path networks with three new operators such as skip, switch, and dynamic generate proposals that dynamically change their execution paths and the number of target objects. Finally, this work proposes a path decision model that chooses the optimal execution path at run-time reflecting dynamically changing en- vironments and time constraints. Our detailed evaluation using widely-used driving datasets shows that the proposed real-time object detection system performs as good as a baseline object detection system without violating the time-varying time limits. Moreover, the WCET model predicts the worst-case execution latency of convolutional and group normalization layers with only 28% and 64% errors on average, respectively.

논문제목 : DC-Store: Eliminating Noisy Neighbor Containers using Deterministic I/O Performance and Resource Isolation

저자 : Miryeong Kwon, Donghyun Gouk, Changrim Lee(KAIST), Byounggeun Kim, Jooyoung Hwang(Samsung), Myoungsoo Jung(KAIST)

학술대회 : FAST 2020

발표자 : 권미령(KAIST)

지도교수 : 정명수(KAIST)

논문초록 : We propose DC-store, a storage framework that offers deterministic I/O performance for a multi-container execution environment. DC-store’s hardware-level design implements multiple NVM sets on a shared storage pool, each providing a deterministic SSD access time by removing internal resource conflicts. In parallel, software support of DC-Store is aware of the NVM sets and enlightens Linux kernel to isolate noisy neighbor containers, performing page frame reclaiming, from peers. We prototype both hardware and software counterparts of DC-Store and evaluate them in a real system. The evaluation results demonstrate that containerized data-intensive applications on DC-Store exhibit 31% shorter average execution time, on average, compared to those on a baseline system.

논문제목 : AniFilter: Parallel and Failure-Atomic Cuckoo Filter for Non-Volatile Memories

저자 : Hyungjun Oh, Bongki Cho(Hanyang University), Changdae Kim(ETRI), Heejin Park, Jiwon Seo(Hanyang University)

학술대회 : EuroSys 2020

발표자 : 오형준(한양대)

지도교수 : 서지원(한양대)

논문초록 : Approximate Membership Query (AMQ) data structures are widely used in databases, storage systems, and other domains. Recent advances in Non-Volatile Memory (NVM) technologies made possible byte-addressable, high performance persistent memories. This paper presents an optimized persistent AMQ for NVM, called AniFilter (AF). Based on Cuckoo Filter (CF), AF improves insertion throughput on NVM with Spillable Buckets and Lookahead Eviction, and lookup throughput with Bucket Primacy. To analyze the effect of our optimizations, we design a probabilistic model to estimate the performance of CF and AF. For failure atomicity, AF writes minimum amount of logging to maintain its consistency. We evaluated AF and four other AMQs - CF, Morton Filter (MF), Rank-and-Select Quotient Filter (RSQF), and Bloom Filter (BF) - on NVM. We use Intel Optane DC Persistent Memory and Quartz emulation for the evaluation. AF and CF are generally much faster than the other filters for sequential runs. However, in high load factors CF's insertion throughput becomes prohibitively low due to the eviction overhead. With our optimizations, AF's insertion throughput is fastest even in high load factors. In parallel evaluation, AF's performance is substantially higher than CF for both insertion and lookup. Our optimizations reduce the bandwidth consumption, making AF's parallel performance much faster than CF's on bandwidth-limited NVM. For parallel insertion AF is up to 10.7X faster than CF (2.6X faster on average) and for parallel lookup AF is up to 1.2X faster (1.1X faster on average).

 

[소프트웨어공학]

논문제목 : Concolic Testing for High Test Coverage and Reduced Human Effort in Automotive Industry

저자 : Yunho Kim(KAIST), Dongju Lee, Junki Baek(Hyundai Mobis), Moonzoo Kim(KAIST)

학술대회 : ICSE 2019

발표자 : 김윤호(KAIST)

지도교수 : 김문주(KAIST)

논문초록 : The importance of automotive software has been rapidly increasing because software now controls many components in motor vehicles such as window controller, smart-key system, and tire pressure monitoring system. Consequently, the automotive industry spends a large amount of human effort testing automotive software and is interested in automated software testing techniques that can ensure high-quality automotive software with reduced human effort. In this paper, we report our industrial experience applying concolic testing to automotive software developed by Hyundai Mobis. We have developed an automated testing framework MAIST that automatically generates the test driver, stubs, and test inputs to a target task by applying concolic testing. As a result, MAIST has achieved 90.5% branch coverage and 77.8% MC/DC coverage on the integrated body unit (IBU) software. Furthermore, it reduced the cost of IBU coverage testing by reducing the manual testing effort for coverage testing by 53.3%.

논문제목 : Target-driven compositional concolic testing with function summary refinement for effective bug detection

저자 : Yunho Kim(KAIST), Shin Hong(Handong Global University), Moonzoo Kim(KAIST)

학술대회 : ESEC/FSE 2019

발표자 : 김윤호(KAIST)

지도교수 : 김문주(KAIST)

논문초록 : Concolic testing is popular in unit testing because it can detect bugs quickly in a relatively small search space. But, in system-level testing, it suffers from the symbolic path explosion and often misses bugs. To resolve this problem, we have developed a focusedcompositional concolic testing technique, FOCAL, for effective bug detection. Focusing on a target unit failure v (a crash or an assert violation) detected by concolic unit testing, FOCAL generates a system-level test input that validates v. This test input is obtained by building and solving symbolic path formulas that represent system-level executions raising v. FOCAL builds such formulas by combining function summaries one by one backward from a function that raised v to main. If a function summary φa of function a conflicts with the summaries of the other functions, FOCAL refines φa to φa′ by applying a refining constraint learned from the conflict. FOCAL showed high system-level bug detection ability by detecting 71 out of the 100 real-world target bugs in the SIR benchmark, while other relevant cutting edge techniques (i.e., AFL-fast, KATCH, Mix-CCBSE) detected at most 40 bugs. Also, FOCAL detected 13 new crash bugs in popular file parsing programs.

 

[프로그래밍언어]

논문제목 : Automatic and Scalable Detection of Logical Errors in Functional Programming Assignments

저자 : Dowon Song, Myungho Lee, Hakjoo Oh(Korea University)

학술대회 : OOPSLA 2019

발표자 : 송도원(고려대)

지도교수 : 오학주(고려대)

논문초록 : We present a new technique for automatically detecting logical errors in functional programming assignments. Compared to syntax or type errors, detecting logical errors remains largely a manual process that requires hand-made test cases. However, designing proper test cases is nontrivial and involves a lot of human effort. Furthermore, manual test cases are unlikely to catch diverse errors because instructors cannot predict all corner cases of diverse student submissions. We aim to reduce this burden by automatically generating test cases for functional programs. Given a reference program and a student's submission, our technique generates a counter-example that captures the semantic difference of the two programs without any manual effort. The key novelty behind our approach is the counter-example generation algorithm that combines enumerative search and symbolic verification techniques in a synergistic way. The experimental results show that our technique is able to detect 88 more errors not found by mature test cases that have been improved over the past few years, and performs better than the existing property-based testing techniques. We also demonstrate the usefulness of our technique in the context of automated program repair, where it effectively helps to eliminate test-suite-overfitted patches.

논문제목 : SAVER: Scalable, Precise, and Safe Memory-Error Repair

저자 : Seongjoon Hong, Junhee Lee, Jeongsoo Lee, Hakjoo Oh(Korea University)

학술대회 : ICSE 2020

발표자 : 홍성준(고려대)

지도교수 : 오학주(고려대)

논문초록 : We present SAVER, a new memory-error repair technique for C programs. Memory errors such as memory leak, double-free, and use-after-free are highly prevalent and fixing them requires significant effort. Automated program repair techniques hold the promise of reducing this burden but the state-of-the-art is still unsatisfactory. In particular, no existing techniques are able to fix those errors in a scalable, precise, and safe way, all of which are required for a truly practical tool. SAVER aims to address these shortcomings. To this end, we propose a method based on a novel representation of the program called object flow graph, which summarizes the program’s heap-related behavior using static analysis. We show that fixing memory errors can be formulated as a graph labeling problem over object flow graph and present an efficient algorithm. We evaluated SAVER in combination with Infer, an industrial-strength static bug-finder, and showed that 74% of the reported errors can be fixed automatically for a range of open-source C programs.

논문제목 : VeriSmart: A Highly Precise Safety Verifier for Ethereum Smart Contracts

저자 : Sunbeom So, Myungho Lee, Jisu Park, Heejo Lee, Hakjoo Oh(Korea University)

학술대회 : S&P 2020

발표자 : 소순범(고려대)

지도교수 : 오학주(고려대)

논문초록 : We present VeriSmart, a highly precise verifier for ensuring arithmetic safety of Ethereum smart contracts. Writing safe smart contracts without unintended behavior is critically important because smart contracts are immutable and even a single flaw can cause huge financial damage. In particular, ensuring that arithmetic operations are safe is one of the most important and common security concerns of Ethereum smart contracts nowadays. In response, several safety analyzers have been proposed over the past few years, but state-of-the-art is still unsatisfactory; no existing tools achieve high precision and recall at the same time, inherently limited to producing annoying false alarms or missing critical bugs. By contrast, VeriSmart aims for an uncompromising analyzer that performs exhaustive verification without compromising precision or scalability, thereby greatly reducing the burden of manually checking undiscovered or incorrectly-reported issues. To achieve this goal, we present a new domain-specific algorithm for verifying smart contracts, which is able to automatically discover and leverage transaction invariants that are essential for precisely analyzing smart contracts. Evaluation with real-world smart contracts shows that VeriSmart can detect all arithmetic bugs with a negligible number of false alarms, far outperforming existing analyzers.

 

[데이터베이스]

논문제목 : D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

저자 : Jun-Gi Jang, U Kang(Seoul National University)

학술대회 : ICDE 2020

발표자 : 장준기(서울대)

지도교수 : 강유(서울대)

논문초록 : Given a dense tensor, how can we find latent patterns and relations efficiently? Existing Tucker decomposition methods based on Alternating Least Square (ALS) have limitations in terms of time and space since they directly handle large dense tensors to obtain the result of Tucker decomposition. Although few methods have tried to reduce their computational time by sampling tensors, sketching tensors, and efficient matrix operations, their speed and memory efficiency are limited.
In this paper, we propose D-Tucker, a fast and memory-efficient method for Tucker decomposition on large dense tensors. D-Tucker consists of the approximation, the initialization, and the iteration phases. D-Tucker 1) compresses an input tensor by computing randomized singular value decomposition of matrices sliced from the input tensor, and 2) efficiently obtains orthogonal factor matrices and a core tensor by using SVD results of sliced matrices. Through experiments, we show that D-Tucker is up to 38.4x faster, and requires up to 17.2x less space than existing methods with little sacrifice in accuracy.

논문제목 : G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching

저자 : Yeonsu Park, Seongyun Ko(POSTECH), Sourav Bhowmick(NTU), Kyoungmin Kim, Kijae Hong, Wook-Shin Han (POSTECH)

학술대회 : SIGMOD 2020

발표자 : 박연수(포항공대)

지도교수 : 한욱신(포항공대)

논문초록 : Despite the crucial role of cardinality estimation in query optimization, there has been no systematic and in-depth study of the existing cardinality estimation techniques for subgraph matching queries. In this paper, for the first time, we present a comprehensive study of the existing cardinality estimation techniques for subgraph matching queries, scaling far beyond the original experiments. We first introduce a novel framework called G-CARE that enables us to realize all existing techniques on top of it and that provides insights on their performance. By using G-CARE, we then reimplement representative cardinality estimation techniques for graph databases as well as relational databases. We next evaluate these techniques w.r.t accuracy on RDF and non-RDF graphs from different domains with subgraph matching queries of various topologies so far considered. Surprisingly, our results reveal that all existing techniques have serious problems in accuracy for various scenarios and datasets. Intriguingly, a simple sampling method based on an online aggregation technique designed for relational data, consistently outperforms all existing techniques.

논문제목 : Natural language to SQL: Where are we today?

저자 : Hyeonji Kim, Byeong-Hoon So, Wook-Shin Han(POSTECH), Hongrae Lee(Google)

학술대회 : VLDB 2020

발표자 : 김현지(포항공대)

지도교수 : 한욱신(포항공대)

논문초록 : Translating natural language to SQL (NL2SQL) has received extensive attention lately, especially with the recent success of deep learning technologies. However, despite the large number of studies, we do not have a thorough understanding of how good existing techniques really are and how much is applicable to real-world situations. A key difficulty is that different studies are based on different datasets, which often have their own limitations and assumptions that are implicitly hidden in the context or datasets. Moreover, a couple of evaluation metrics are commonly employed but they are rather simplistic and do not properly depict the accuracy of results, as will be shown in our experiments. To provide a holistic view of NL2SQL technologies and access current advancements, we perform extensive experiments under our unified framework using eleven of recent techniques over 10+ benchmarks including a new benchmark (WTQ) and TPC-H. We provide the comprehensive survey of recent NL2SQL methods, introducing a taxonomy of them. We reveal major assumptions of the methods and classify translation errors through extensive experiments. We also provide a practical tool for validation by using existing, mature database technologies such as query rewrite and database testing. We then suggest future research directions so that the translation can be used in practice.

논문제목 : TRAP: Two-level Regularized Autoencoder-based Embedding for Power-law Distributed Data

저자 : Dongmin Park, Hwanjun Song, Minseok Kim, Jae-Gil Lee(KAIST)

학술대회 : WWW'20

발표자 : 박동민(KAIST)

지도교수 : 이재길(KAIST)

논문초록 : Recently, autoencoder (AE)-based embedding approaches have achieved state-of-the-art performance in many tasks, especially in top-k recommendation with user embedding or node classification with node embedding. However, we find that many real-world data follow the power-law distribution with respect to the data object sparsity. When learning AE-based embeddings of these data, dense inputs move away from sparse inputs in an embedding space even when they are highly correlated. This phenomenon, which we call polarization, obviously distorts the embedding. In this paper, we propose TRAP that leverages two-level regularizers to effectively alleviate the polarization problem. The macroscopic regularizer generally prevents dense input objects from being distant from other sparse input objects, and the microscopic regularizer individually attracts each object to correlated neighbor objects rather than uncorrelated ones. Importantly, TRAP is a meta-algorithm that can be easily coupled with existing AE-based embedding methods with a simple modification. In extensive experiments on two representative embedding tasks using six-real world datasets, TRAP boosted the performance of the state-of-the-art algorithms by up to 31.53% and 94.99% respectively.

논문제목 : Pre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines

저자 : Eunjae Lee(UNIST), Junghyun Kim(TmaxOS), Keunhak Lim(Nexon), Sam H. Noh(UNIST), Jiwon Seo(Hanyang University)

학술대회 : USENIX ATC'19

발표자 : 이은재(UNIST)

지도교수 : 서지원(한양대), 노삼혁(UNIST)

논문초록 : Many important graph algorithms are based on the breadth first search (BFS) approach, which builds itself on recursive vertex traversal. We classify algorithms that share this characteristic into what we call a BFS-like algorithm. In this work, we first analyze and study the I/O request patterns of BFS-like algorithms executed on disk-based graph engines. Our analysis exposes two shortcomings in executing BFS-like algorithms. First, we find that the use of the cache is ineffective. To make use of the cache more effectively, we propose an in-memory static cache, which we call BFS-Aware Static Cache or Basc, for short. Basc is static as its contents, which are edge lists of vertices that are pre-selected before algorithm execution, do not change throughout the execution of the algorithm. Second, we find that the state-of-the-art ordering method for graphs on disks is ineffective with BFS-like algorithms. Thus, based on an I/O cost model that estimates the performance based on the ordering of graphs, we develop an efficient graph ordering called Neighborhood Ordering or Norder. We provide extensive evaluations of Basc and Norder on two well-known graph engines using five real-world graphs including Twitter that has 1.9 billion edges. Our experimental results show that Basc and Norder, collectively have substantial performance impact.

논문제목 : IDAR: Fast Supergraph Search Using DAG Integration

저자 : Hyunjoon Kim, Seunghwan Min, Kunsoo Park(Seoul National University), Xuemin Lin(University of New South Wales), Seok-Hee Hong(University of Sydney) Wook-Shin Han(POSTECH)

학술대회 : VLDB 2020

발표자 : 김현준(서울대)

지도교수 : 박근수(서울대)

논문초록 : Supergraph search is one of fundamental graph query processing problems in many application domains. Given a query graph and a set of data graphs, supergraph search is to find all the data graphs contained in the query graph as subgraphs. In existing algorithms, index construction or filtering approaches are computationally expensive, and search methods can cause redundant computations. In this paper, we introduce four new concepts to address these limitations: (1) DAG integration, (2) dynamic programming between integrated DAG and graph, (3) active-first search, and (4) relevance-size order, which together lead to a much faster and scalable algorithm for supergraph search. Extensive experiments with real datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.


서울시 서초구 방배로 76 (방배동, 머리재빌딩 401호) 우)06704 | (Tel)1588-2728 | (Fax)02-521-1352 | 고유번호 : 114-82-03170 | 대표 : 김두현

Copyright (c) KIISE. All rights reserved.