dbjapanの皆様、 sigmod-jの皆様、 年の瀬も押し迫ってまいりましたが、 是非ともご参加を尾根がいたします。 -------------------------------------------------------------------- 　　　　　　　　講演会のご案内 　　　　　　　共催　ACM SIGMOD日本支部 　　　　　　　　　　日本データベース学会 日時　１２月２３日（金）　午後２時〜午後３時 場所　東京大学生産技術研究所　会議室A(Ew-501) E棟　5階　エレベータをあがってすぐ http://www.iis.u-tokyo.ac.jp/map/index.html 当日は休日のため、建物内へ入るときには、内部に 　　　ご連絡いただく必要がございます。当日、 　　　ビルディングEの入り口にその旨、掲載いたしますので、 　　　入り口の内線電話にてご連絡ください。 Title: Summarizing Level-two Topological Relationships in Large Spatial Datasets Speaker: Prof. Xuemin Lin (University of New South Wales) 参加費　無料 参加ご希望の方は、ＳＩＧＭＯＤホームページにて （ http://www.sigmodj.org ） 　　　会員登録の後（会費無料、すでに登録されている方は結構です）、 sigmodj_lecture@tkl.iis.u-tokyo.ac.jpに 　　　添付の参加申込書をお送り下さい。 皆様のご参加をお待ちしております。 ACM　SIGMOD日本支部　支部長　北川博之 　　　　　　　　　　　　　　　　　　　　　　 担当幹事　中野　美由紀 連絡(問合せ)先　ACM SIGMOD日本支部 sigmodj_lecture@tkl.iis.u-tokyo.ac.jp 　　　　　　　　　　　　　　　　http://www.sigmodj.org ----------------------------------------------------------------- To: sigmodj_lecture@tkl.iis.u-tokyo.ac.jp ACM SIGMOD日本支部　講演会　参加申し込み １２月２３日（金）の講演会に参加 ・名前　　　 ・ご所属 ------------------------------------------------------------------ Title: Summarizing Level-two Topological Relationships in Large Spatial Datasets Speaker: Prof. Xuemin Lin (University of New South Wales) Abstract: Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this talk, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. -- ----------------------------------------------------------------------- 中野　美由紀 東京大学　生産技術研究所　喜連川研究室 Miyuki NAKANO Institute of Industrial Science, Univ. of Tokyo miyuki@tkl.iis.u-tokyo.ac.jp