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@tkl.iis.u-tokyo.ac.jpに 添付の参加申込書をお送り下さい。 皆様のご参加をお待ちしております。 日本データベース学会 国際関係委員会 委員長 （ACM SIGMOD日本支部 支部長） 横田 治夫 連絡先 中野 美由紀 連絡(問合せ)先 日本データベース学会、 ACM SIGMOD 日本支部 sigmodj_lecture@tkl.iis.u-tokyo.ac.jp http://www.dbsj.org/ ----------------------------------------------------------------- To: sigmodj_lecture@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@tkl.iis.u-tokyo.ac.jp