07 2019/08 09
28293031010203
04050607080910
11121314151617
18192021222324
252627 28 293031
Click セミナー

次回セミナー

開催日2019年8月28日(水曜日)
開催時間15時30分-16時30分
発表者山口 勇太郎 
発表者の紹介大阪大学
タイトル無制約XOS関数最大化に対する最適近似アルゴリズム 
発表の概要
いくつかの加法的な集合関数の最大値を取る形で表現できる集合関数は,XOS関数と呼ばれ,劣モジュラ関数などを含むことが知られている.本講演では,関数値オラクルで与えられたXOS関数を最大化する問題を考え,最適な近似比を達成する多項式時間アルゴリズムを提案する.本研究は,河瀬 康志氏,小林 佑輔氏との共同研究に基づき,これは昨年度の SSSW2018.09B において開始されたものである.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間16時30分-17時30分
発表者佐々木 勇和 
発表者の紹介大阪大学
タイトル Structural Indexing for Conjunctive Path Queries 
発表の概要
Structural indexing is a powerful approach to accelerating query
evaluation, whereby data objects are partitioned reflecting the
expressive power of a given
query language. Each partition block of the index holds exactly those
objects that are indistinguishable with respect to queries expressible
in the language.
Structural indexes have proven successful for XML, RDF, and relational
data management. In this paper we study structural indexing for
conjunctive path
queries. Conjunctive path queries form the core of contemporary graph
query languages such as SPARQL, Cypher, PGQL, and G-CORE. The
conjunctive path queries play the same fundamental role that the
conjunctive queries do for SQL. We develop the first
practical structural indexes for this important query language. In
particular, we propose a structural index based on
k-path-bisimulation, tightly
coupled to the expressive power of the conjunctive path queries, and
develop algorithms for efficient query processing with our index.
Furthermore, we
study workload-aware structural indexes to reduce both the
construction and space costs according to a given workload. We
demonstrate through
extensive experiments using real and synthetic graphs that our methods
accelerate query processing by up to four orders of magnitude over the
state-of-the-art methods, without increasing index size.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ