[dbjapan] DBSJ & ACM SIGMODJ 講演会 のご案内 （８月１日）

[Miyuki Nakano <miyuki [at] tkl.iis.u-tokyo.ac.jp>]

DBSJの皆様、

8月1日（水）に下記のとおり、講演会を開催いたします。
ふるってご参加ください。


-------------------------------------------------------------------
　☆☆☆　8月1日　講演会のご案内　　　☆☆☆

共催　日本データベース学会
　　　ACM SIGMOD日本支部
　　　電子情報通信学会東京支部

日時　8月1日（水）　午後４時〜午後５時半
場所　東京大学生産技術研究所　Ｅ棟　５階　会議室Ａ（Ew-501）
      http://www.iis.u-tokyo.ac.jp/map/index.html

Speaker :　Prof. Jefferey Xu Yu (The Chinese University of Hong Kong)
Title :Finding Top-k Min-Cost Connected Trees in Databases



参加費　無料

参加ご希望の方は、
　日本データベース学会のホームページにて
　　　( http://www.dbsj.org/ )
　　　会員登録の後（会費無料、すでに登録されている方は結構です）、
      sigmodj_lecture [at] tkl.iis.u-tokyo.ac.jpに
　　　添付の参加申込書をお送り下さい。

皆様のご参加をお待ちしております。

                        日本データベース学会　国際関係委員会　委員長
                        （ACM　SIGMOD日本支部　支部長）　横田　治夫

　　　　　　　　　　　　　　　　　　　　　　  連絡先　 中野　美由紀
　　　　　　　　　　
                        連絡(問合せ)先　日本データベース学会、
　　　　　　　　　　　　　　　　        ACM SIGMOD 日本支部
                                sigmodj_lecture [at] tkl.iis.u-tokyo.ac.jp
　　　　　　　　　　　　　　　　http://www.dbsj.org/

-----------------------------------------------------------------
To: sigmodj_lecture [at] tkl.iis.u-tokyo.ac.jp

日本データベース学会・ACM SIGMOD日本支部共催　講演会　参加申し込み

８月１日（水）の講演会に参加
・名前　　　
・ご所属
------------------------------------------------------------------
プログラム

Title: Finding Top-k Min-Cost Connected Trees in Databases

Abstract:
It is widely realized that the integration of database and information
retrieval techniques will provide users with a wide range of high
quality services.  In this work, we study processing an l-keyword
query (p1, p2, ..., pl) against a relational database which can be
modeled as a weighted graph, G(V, E). Here V is a set of nodes
(tuples) and E is a set of edges representing foreign key references
between tuples.  Let Vi be a set of nodes that contain the keyword
pi. We study finding top-k minimum cost connected trees that contain
at least one node in every subset Vi. We denote our problem as GST-k.
When k = 1, it is known as a minimum cost group Steiner tree problem
which is NP-Complete.  We observe that the number of keywords, l, is
small, and propose a novel parameterized solution, with l as a
parameter, to find the optimal GST-1, in better time complexity.  Our
solution can handle graphs with a large number of nodes. Our GST-1
solution can be easily extended to support GST-k, which outperforms
the existing GST-k solutions over both weighted undirected/directed
graphs.  We conducted extensive experimental studies, and report our
finding.


-----------------------------------------------------------------------
中野　美由紀		東京大学　生産技術研究所　喜連川研究室
Miyuki NAKANO		Institute of Industrial Science, Univ. of Tokyo
miyuki [at] tkl.iis.u-tokyo.ac.jp