我想，同學們大概都修過 Database 的課程吧。何謂 Database 呢 ? 基本上就 是對 Data 的一個管理。譬如說，我們的學校裡有許多的資料，有同學的資料、 有老師的資料、有修課的資料，為了方便我們管理這些資料我們會把他丟到電腦 中，並且把它們組織成很好的結構。
這個結構呢，又分兩種，一種是 Schema 方面，屬於比較 logical 的 level， 也就是 conceptually 它的結構是很清楚的。當然另外一個結構是它的 storage ，是屬於比較底層的，那麼如果底層的結構比較好的話，系統就會比較的有效率 。而上層的結構如果比較好的話，就可以用的比較久，不會說一下子就需要再修 改。所以我們現在的資料庫呢，大致上就會學這些東西喔。
我們會學什麼呢？學 Data Model 的東西，就是以前的 Hierarchical，現在的 Relational，甚至 Object Oriented 或叫 Object Relational。那麼這些，就 是用不同的 model 來 model 你所要存的這些 data。
而今天我要講的這個題目『 Data Management』，也就是資料的管理，那麼我 們傳統的資料庫呢， Data Model 是屬於上層的 logical 的 level，對 Data 作 Modeling 的工作。再來就是有 structure，那在這個地方呢，我們就會各種 各樣的 structure， e.g. B+ tree，那這就牽扯到我們要如何有效率的把資料 放在 Disk 上面然後去擷取他。
還有比較傳統的資料庫系統，一般放的是屬於文數字的資料。譬如說，我剛剛 講的學校中，學生的資料可能有學號、名字、系級等等；或者是在公司中，可能 會記載員工的薪水、員工的專長等等。而這些都是屬於文數字的資料，這些就可 以很容易的用 Relational Data Model 來 Model 起來。所以我們就有一個 table，一個 table 的。譬如說我們有一個 student 的 relation，還有一個 teacher 的 relation。
而系統會提供一個語言，可以讓你把 student 和 teacher 之間的關係呢，譬 如說用一個 join 的 operation 連結起來，使得你能夠作一個這樣的查尋。譬 如說我想要知道『一個學生的老師的電話』這樣的查尋，所以說如果我們的學生 這邊有一個欄位是他的 teacher number 好了。那我們就可以利用這樣一個 attribute 呢，利用 join 這個 operation 把他的老師的資料找出來。
那麼我們目前提到的資料庫的管理系統，我想我們可以把他稱為傳統的資料管 理，當然其中有兩個重點，一個是我們 query 的 optimization。當今天一個使 用者下一個 query 的時候，我們怎樣的把這個查尋轉成一個執行的順序，使得 我們可以很快的找到我們所要的 data。當然這跟我們訂定的 structure，還有 table 大小都有關。
另一個重點就是 Transaction 的 management。那麼 Transaction Management 的意思，就是譬如說，今天我要從一個帳號中要轉 1000 塊到另一個帳號。那在 轉到一半時突然系統故障，而沒有將錢轉入該帳號。這就讓使用者平白的損失了 1000 塊。於是我們要想辦法來復原他，譬如說我們可以在系統 recover 後，我 們可以在把這一千塊還回到原來的帳號，回到像轉帳前的狀態。總而言之， Transaction Management 就是要確保資料在 update 前後正確性。
那麼 90 年的時候，有提到 Database 最偉大的三項成就，其中兩個就是 Relational Data model，另一個就是 Transaction Management 的提出。
而到了後來由於網路的興起就有人提出了 Distributed Database。也就是分散 式的資料庫，也就是將資料切割存放在各個不同的 computer 的 node 來管理。
另外還有一個觀念就是 Multi-Database。他觀念其實是跟 D-DB 是很像的。譬 如說清大有清大圖書館，交大則有交大的圖書館，所以我們就可以對兩個圖書館 的資料庫做一個整合。提供給我的使用者一個整合後的 database 的界面，使得 使用者不需知道資料是從交大來或清大來，只需對整合後的界面作 query 即可 得到他要的資料。所以它等於對資料庫做一個 integration 的動作。
接下來就有了 parallel computer 出來了。那我們就可以利用這種機器的平行 能力，使得資料的擷取更快速。
接下來我要講的是我在作的這個研究就是 Multimedia database。我們原始的 database 是針對文數字的 data，那麼 multimedia 的 database 就是要針對像 image、 video、 audio 等等資訊來作。但是這時候我們需要提供怎樣的介面， 來讓我的使用者可以去把他想要看的影片抓出來呢？傳統的方法可能是還是用一 個 relational 的方法來存他的 information，像他的片名、導演、演員呀等等 ，這樣來管理。
但是我們想要作的是，今天我的使用者可能不知道這些文字的資訊，於是就有 一種觀念叫 Content Based Retrieval。也就是呢，因為這些媒體它本身有很多 的內容。譬如說以一張 image 來看呢，可能裡面會有一座山、有一朵雲，那我 們是否可以提供使用者利用它的內容來尋找這張 image，也就是利用它的內容作 為查尋的依據。
那麼我現在先來講一下 image 的情形。我們要如何的去表示一張 image 呢？ 在一個 media 中呢，我們要去自動化取出其中的一個 feature。像 image 中有 一項的 feature 是顏色的分布等等，我們可以利用它的 features 作一個索引 。有一種查尋法稱之為 Query-by-example 也就是給一張圖用相同的方法把它的 features 取出來，然後系統中跟資料庫中的 index 作比對找出相似的圖形。
那有哪些東西我們可以拿來當 feature 呢？譬如說一張 image 中他的顏色分 布，它的 shape 等等。那麼在每一張照片中，我們先去取出它的 features。
那像 color 我們要怎麼描述呢？我們可以用一種方式稱為 color histogram， 什麼是 color histogram？就是我們統計圖中顏色的出現次數做成 histogram， 然後我們用 color histogram 來代表這張圖，而 user 的提供的 example 也取 出他的 color histogram。這樣便可以對這兩個 histogram 做比對。
但是這樣可能有一個缺點，就是如果說今天有一張圖它的紅色很強，也許他是 一個紅辣椒的圖片，另外一張是有很多紅色零星散布在圖中。雖然兩張圖很不一 樣，但是它的 color histogram 可能很像。
於是就有人想到再取 color 的位置去做判斷。譬如說一般我們照相時，會把目 標擺在中間。所以就只就中間比較它的 color histogram。當然還有很多種不同 的方式，當然你也可以把 color histogram 跟 shape 等等不同的 features combine 起來給他們 weight 去作比對，不過這樣未必會有比較好的效果。通常 是看你的 image 的形式來決定如何作索引。 接下來我們要談到的就是 video， video 就是會動的東西，我們怎麼去處理與 管理 video 的 data 呢？這管理的方法是跟我剛剛講得那個精神是差不多的， 將 video 解成 feature，然後再將這些 feature 集合起來建一個索引，大概就 是這樣子。
再來我們要看看什麼稱為一個 video 的 feature，因為這個 image database 是一種做的比較久的 database，而它為什麼做的比較久的原因我覺得有兩個， 第一個原因是因為很多做 image processing 的人都漸漸的 touch 到這個領域 。像我審國科會計畫時，就發現很多教授以前是做 image processing 的，現在 都在做 image database。那另外就是說它比較簡單，因為畢竟這兩個比較起來 ，這個有時間的觀念另一個沒有，所以這個比較簡單。第三個可能是說比較容易 ，那我們現在探討 video 的話，那 video 的 feature 到底是什麼呢？我們不 太清楚，這也是因為這個原因，我們一開始在做 multimedia database 時，就 選定了 audio 和 video，我們就不作 image 了，因為這樣子才會有比較新的結 果。
那在我們講比較純粹 video 的作法之前，我再講一個 image 可以用來處理 video 的方法。我們首先來看這個 video 的結構，它是一連串的 frame 所組成 ，而這一個一個的 frame 可以說就是一個 image。那我們有一個作法是這樣子 的，像在拍電影一樣的，我們在外面拍一拍，再換到裡面拍一拍，而這每次的拍 一拍我們叫它為一個 shot，一個鏡頭。所以什麼叫做一個鏡頭，因為它是同一 個地點拍嘛，所以它的內容就比較相似。那我們從一個鏡頭到另一個鏡頭就稱之 為 shot cut 或 shot change，那我們必須去做到從一個鏡頭到另一個鏡頭的 detection，分辨出來它是從那邊切割出來。
那這個過程並不是那麼難，因為我們怎麼稱之為一個 shot，就是因為它的內容 很類似。所以當我們判斷兩個 frame 的內容差很多時，就可以判斷它是一個 shot change 的地方。然候判斷出 shot change 的地方後，我們就把 shot 分 開。那每一個 shot 中的內容都很相似的，所以我們從其中選出一個 frame，稱 之為 key frame。而每一個 shot 裡都有一個 key frame，那一個 movie 裡會 有很多 frame，一般一秒裡大概是二十多張 frame，那一分鐘大約有 1200 張 frame，那一部片就有很多的 frame，假如說這一個 shot 是很長的，我們就可 以用一個 key frame 來代表這個 shot。
所以說一部電影裡有多少 shot，就會有多少 key frame，所以有了這些東西我 們就可以做什麼呢？第一個我們可以做這個 video browsing，就像一般看錄影 帶時的快轉或回轉的功能。而有了這個 key frame 時，我們就不須要一張一張 的去快轉或回轉，所以我們就可以根據我們的喜好從 key frame 裡去挑我們想 看的部份。
那另一個 key frame 的用途呢，就是我們可以用來作 image 的比對。譬如說 我們有一張某部電影的劇照，那我們想找出這部電影時，我們就可以利用這部電 影裡的 key frame 來做 image 的比對。那當我們發現某個 key frame 和我們 的 image 很相似時，那這個就可能是我們想找的電影。
可是大家可能會覺得這樣的效率不好呀 ! 這都是對的 ! 因為這樣做很不容易 ，像在一部電影裡，有一個鏡頭拍一個人，可能會又很多個角度，而且會一下拉 近一下拉遠，這樣的 shot change 是很容易發生的，加上許多影片的特殊處理 ，像是漸近、淡出、淡入等，都會產生很多問題，那我現在講得是我們可以用傳 統的 image 比對的方式來做這個 video retrival 的事情，那我剛剛講得就是 這個。
再來呢，我們認為既然是電影既然是 video 的話，就一定是會有某一個東西會 動。所以我們在想，如果我們能從 video 裡判斷出這個 object，譬如說那是一 個球，那我就可以看這個球在 frame 裡進行的過程。而這個球，我們可以登記 它的顏色、它的大小、它的形狀、它的行徑方向、速度之類的。所以說我們可以 看到事實上假設那是一隻鳥好了，這隻鳥呢就在影片裡飛上飛下，或者是轉來轉 去，所以基本上我就可以對於這個 object 記錄它的它的顏色、它的大小、它的 形狀、它的行徑方向、速度。
這樣我就可以對於影片裡這隻鳥的 information 記錄下來，記錄下來之後，我 們就可以提供一個介面，像是有很多 icon，鳥的 icon、花的、動物的，然後甚 至我們可以讓使用者輸入一定的軌跡，然後使用者就可以針對他想找的某一隻有 類似軌跡的鳥做搜尋，所以我們就可以利用這樣的機制來找尋我們要的物件。
那至於這方面的技術牽扯到的就是 curve matching。常常舉得一個比較好的例 子就是，有一個人想找一段滑雪的影片。所以呢，我們讓使用者畫一個類似滑雪 的路徑，而我們就把這些資料當做我們要找尋的 feature。這時後就會牽涉到 curve matching 的問題，譬如使用者所畫的 curve 比實際影片裡的 curve 小 而且是相反的，那我們如何判斷這兩個 curve 是否相同？所以我們做 matching 的時後，有時還要考慮到 curve 旋轉的角度、平移等，而其中也包括了 time 的 information ( 對於連教授的問題所做的回答 )。
而對於所要記錄的資料，我們可以增加必要的編碼。這些問題都有共同的特色 ，就是說如果你記載的越是繁雜的話，那效果是怎麼樣？就是說它在比對時會花 更多的時間，它可能因為記載的比較詳細所以比較難找的到，因為變成了每一項 都要滿足了，所以這就有點麻煩了。那找不到到底是好還是壞，我們當然是希望 它找的快，而找的慢，就要看找到的東西是不是你滿意的，這有個名詞叫做 effectness。
如果你剛剛有注意到的話，我們講到文數字的資料的時後，不談 effective， 只談 efficient。我們只看效率，看它 database structure 是不是夠好，使得 我能做 critical processing 能很快的找到答案，因為我們找出來的檔案就是 你想要的。但這在 multimedia database 裡確不是那麼容易的，所以在 multimedia database 的搜尋結果不是單一的，而是有 video 1， video 2…等 讓使用者選擇，由使用者來挑選最符合須求的 video。所以說如果這個能顯現出 這 video 的 feature 能選的好，就能提高搜尋的 effectness 就能提高了，所 以現在我們就很難去回答這個問題。再來對於 effective 的問題，我希望我找 到的答案也都是我想要看的。
另外我們還做了一些類似的工作，因為時間的關係我想我就寫一下大概就好了 ，像是 CVQL，我們提供一個語言和介面，還有一些 data structure。這些東西 到了最後都變成了一種 matching， string matching 的問題，就像之前提到的 curve matching。在這些問題之下它特別強調兩個 issue，一個是 approximated matching，因為 user 所畫的與我 database 裡所存的東西並不 是那麼的符合，是不是完全的比對一樣。所以我們要考慮到 approximation，就 像剛剛所提到有關使用者想找出有關滑雪的影片。另一種是 partial matching ，也許使用者只是提供了一部份的資料，其實我們大部份也要考慮到這個 partial。
那麼這最主要的是有關我們接下來要談到的這個 music，我們並不處理 speech 這個部份，其實我們講的就是歌曲。那 music 方面 partial 的味道就更濃了。 這邊我們是提到一個 3D list，一個 data structure 定義物體與物體之間的關 係，我們可以考慮到兩個 object 相對的關係，我們有一個 data structure 可 以處理這一方面的東西。
再來我們在來講有關 music 的問題，第一個我們還是提到 feature，與之前是 一樣的方法，我們到底要用那一個 feature 來代表音樂呢？一個比較簡單的就 是用旋律，旋律的意思就是把音樂節奏的部份拿掉，所以那叫做 melody。我可 以用旋律來代表一首歌，我可以用節奏來代表一首歌，因為音樂這個東西很少人 做，所以我們只要寫一下都會被接受，其實它可能都寫得不是那麼好。不過也是 沒有人寫到這些。
譬如說我們可以用合弦來代表一首歌，也就是說一小節就是一個合弦。所以我 們可以把一個比較長的資料用某一個 feature 或 index 來表示。這些用來表示 原來媒體的 feature 或 index 都必須要有一個基本的需求，就是要比原本的資 料簡單，所以我們這樣做才會比較快。當然你也可以整個五線譜記錄進去，不過 這樣也就比較花時間去找，所以像這個合弦也是。
還有一個比較重要的就是 theme，一個比較有趣的東西。 theme 就是一個主題 ，主題呢在流行歌曲裡也就是副歌。所以我們要怎麼找出一個東西來做整體的一 個代表，就是使用者最有可能拿這個東西去當作查詢的根據。所以就像是我想要 去找一首歌，那我不知道是誰唱得，也不知道歌名，只會哼某一小段，這段可能 就是副歌，因為它一直重覆一直重覆，所以你的印象最深刻。就像那貝多芬的命 運交響曲，那是一直重覆一直重覆，所以用 theme 來表示一首歌是一種很好的 方式。第一是因為 theme 它通常都很短，另一個是因為這個 theme 通常都是很 特別的，可以用來代表這首歌的。所以我們接下來的研究就是去找這個 theme， 那 theme 是什麼呢？其實 theme 就是一個 repeating pattern，它是一直重覆 的。所以我們就想到給你一首歌，然候找出一個一種重覆的弦律，就像命運交響 曲裡的弦律可以讓我們找出來，也就是找出 repeating pattern。那當你找出了 theme，那你就可以拿它當做這個歌的 feature。
那我們另外還做一個有趣的實驗，就是這個 theme 到底是不是能表達這首歌？ 我們拿了幾首古典的交響樂做比較，我們把它們最長的 repeating pattern 找 出來。最後我們發現有某位作曲家，他所做的歌曲的 repeating pattern 發現 都是很像的。所以就可以提出一個很有趣的結論，就是這個作曲家在作曲上重覆 的地方都是很相像的。
其實你說這個結果是很令人 surprising，其實也不見得。像現在的流行音樂裡 有很多音樂弦律都是很類似的，這有個好處。你可以去分析現在流行歌曲裡有那 些共同性，然後把這些共同性擺一擺，再加一些其它的，很可能就可以變成另外 一首熱門新歌。
所以我們做了一些分類的工作。那我現在已經把 multimedia database 的部份 講得差不多了，而現在其它學校做的東西大概可以分成三類，而之前的 multimedia database 也只是其中的一類而已。
而我才講一個部份就以經三點二十了，所以等一下同學有什麼不懂的地方可以 提出來討論，那今天我講得東西並沒有針對某一個特殊的解法，而只是概括的告 訴大家他有這些問題可以思考。
再來我們講的是 web 這個東西，一談到 web 我們就覺得有點辛苦，原因就是 這個 web 太熱門了，太多人在做了，再來就是這個 web 裡面太沒有結構了、太 難做了，第三個原因就因為它太不容易可以寫成一個很漂亮的理論，所以我們做 了一陣子也沒有什麼特殊的結果。
而我現在有個學生在做一個題目，我們要在這個 web 的環境裡做一個推薦的事 情，推薦的意思就是，第一個， user 會從 web 裡面 access 這個 web，我從 它這個 access log 裡面我希望能去建立這個 interest profile，我要知道這 個 user 的興趣在什麼地方，所以我們可以從某一個人看的網頁，…
合在一起。譬如說我們這個以 accesslog 來看，我們以書本來看。他今天看的 書，譬如說他看這個是余秋雨的書，接下去他又看看這個也是余秋雨的書，接下 去他又看看旅行文學的書，譬如說「文化途旅」，大致上我們可以知道說他可能 對余秋雨的書很有興趣、他可能對旅行文字很有興趣。我們可以大概去算算看他 對哪一些 page access 最多，就可以來代表是他的 interest。
另外一點就是說，他會不會常常把某一類的書和某一類的書一起看。這個如果 有同學在做 data mining，這個我等一下會提到，就會感覺到我們所有做的是什 麼。就是說他是不是有兩本會常常一起看呢？也許他看了三個之後就一陣子都沒 看了，那下一次他又看的時候，就是說這兩種類型的又會常常一起看，這樣子的 話我們把它定成是他的 behavior。他看了這一類的書後，他就想看那一類的書 ，這些我們都希望是從 access log 去把它 mine 出來。
就是說我現在可以把某一個 user 他的興趣跟他的習慣，可以用某一種方式表 達出來，我們用一種圖把他表現出來。那麼再來就是說，每一個 user 都有一個 這樣子的圖，這個裡面代表這個 user 的 interest 和 behavior，每一個人都 有一個這樣的圖。那麼接下去的動作就是說，我要去看看哪一些 user 有類似的 興趣、類似的 behavior，這樣的話就可以把他們歸成一類。
再來就是說，有一個新書出來了，我就知道把這個新書推薦給這一類的人，這 是一種。另外一種就是說，假如今天某一個 user 去 access 了某一本書，這一 本書在他同樣一個 cluster 裡面沒有看到的，我是不是能夠推薦給他呢？我就 可以跟他說：「你是不是想看這一本書。所以我們所謂的推薦，在電子商務上是 非常重要的事情。我們要能主動的是告訴 user 說我有哪些書了，而不是說只去 設計網頁等著 user 來看，等著他來訂書，有的時候我們能夠主動一點，我們是 有在做這一方面的工作。
另外一個也是比較以前做的，我們去根據這個 aceess log，如果我們統計夠多 人 browing 的 behavior，也許你可能發現，每一個人他看了 A 之後，他都會 看 B。不管他是直接看，還是繞了一大圈再看。他繞了一大圈再來看 B，有可能 是因為他不曉得這邊可以直接看到 B 來。如果有這種情形的話，我們可以在這 邊加一個 anchor 是 B 讓他可以直接連到 B 來。
另外一件事情是說，我現在如果是在 access A 的時候，我可不可以去做 prefetch 的動作，或者是叫做 prediction。我預期說如果這種 pattern 夠多 的話，那我是不是能夠說去 predict 說，這些人一旦到 A 的話，接下去其實他 是要看 B 的。那我就可以跟他講說你是不是要看 B，或者說先把 B prefetch 給他看。特別在我們以前和連教授一起做的「行動資訊系統」的時候，我們就有 考慮，也許你是拿著手機去 access internet。有時候你為了不要讓電池耗費太 多，希望他能夠根據你以前 access 的行為，我能夠去 predict，能夠讓你很快 的看到你本來想看到的東西。
接下去我們可以講到 data mining 的東西。那麼 data mining 基本上他是希 望從大量的資料裡面去獲取 knowledge。有時候我們叫做 knowledge，有時候我 們叫做 information，譬如說 knowledge discovery。或者叫做 rule，我們去 推導這個 rule 出來，或者說 pattern，這些名辭都是很相像的。反正就是說我 要從大量的資料裡面去找出一些法則，使得我可以用這些法則來做一些有用的事 情。所以我們就開始討論有哪一些有趣的問題。
基本上這個 data mining 的部分，我認為我們可以把它分為三個部分來考慮。 一個就是說應用，一個是資料的型態、一個是 mining 的方法技術，我覺得是可 以分成這三個。應用和資料型態是很有關係的，那麼方法就是說有各式各樣的方 法。
最原始的一個叫做 association rule，基本上他是對於 transaction data， 譬如說你去大賣場，然後你出來的時候，這種問題有時候我們把它叫做 basket 的問題。比如說你買了一些東西，然後你提了一個菜籃，你到算錢的地方，現在 都有條碼，他就刷刷刷，第一個 transaction 他就買了 A、 C、 F 之類的，第 二個 transaction 他就買了什麼，第三個 transaction 他買了什麼，我們是不 是能夠從這個資料找出到底哪一些物品會同時被購買，這是最傳統的問題。所以 你也許就可以推出來，譬如說牛奶和麵包常常會被購買。
另一個例子就是說尿布和啤酒常常會被購買。這是一種現象，第一個你可以去 分析為什麼會有這樣的情形，第二個你可以利用這個結果，是不是尿布和啤酒常 常會被購買，那你是不是要把他們放在一起比較好呢？還是你要把他們放在你店 裡最極端的兩個角落呢？這要看看啤酒和尿布同時被購買的 confidence 有多高 。如果你買啤酒一定會買尿布的話，我想你最好把他們放得很遠，所以你買了啤 酒之後你就開始去找尿布，那這個找尿布的過程之中也許你又會多買一些東西。 另外有一種就是說那你就把他擺在旁邊，那就是順道。假如說你買了啤酒之後會 有 70% 會去買尿布，或者是 60%，不是那麼的強，那我看你最好把它們放在一 起，他買了會順便買。如果是 95%，那你可能可以把他們把擺很遠。
這個是一種，這個叫做 association rule。那麼另外我們是不是能推導出來另 一種叫做 sequential pattern，這個時候又有加入了一個顧客的觀念在裡面了 ，這有個 C1,C2。這個 C1 在買了這個之後隔一陣子他會買某一些、再隔一陣子 他會再買某一些。大量的顧客在買了一個東西之後又會買這一樣東西，這個叫做 sequentail pattern。那這個應用和資料型態可能不太一樣，這邊有 customer 的觀念，這個我等一下再談方法。那麼現在有一個應用就是 stock prediction ，股票的預測，假如今天有這個股票 A,C,F 是漲，明天有 C,D,G 股票漲。所以 我現在要找某一個股票漲了之後，在兩天內到底有哪些股票會漲。所以說他的應 用是不一樣的，他的資料型態是天的味道在裡面，在兩天內，所以他會有一個 sliding window，所以他的技術方法也會不太一樣，這個方法我想我不太多談。
如果說我們做 web 的 prediction，如果說這一次他看了哪一些東西，這個時 候 data 也是不太一樣的，這個時候他看了 A 之後、再看 C、再看 F，那這個 看的之間是有次序性的，而我本來的那一些都是沒有次序性的，那隔一陣子之後 他又會去看這一些東西，那你是不是像我剛剛講的，看了某一些網頁後，不管過 了多久，總之還是會看哪一個網頁，所以這個就是不太一樣。
還有另外一個有 cycle 的觀念。我希望知道多少的人，星期一買了什麼東西之 後，他下一個星期一還會買什麼東西，因為我們做的東西常常都是週期性的。很 多人早上起來，吃個早餐，然後看看報紙，我覺得都好像沒有辦法享受這個。譬 如說週日早上，我們可能很多人去上教堂，所以，這樣的話，他可能有一個週期 性。這裡強調的是週期性，很多少的人會有某一個週期性。所以，你找出這個有 什麼用，就看你要做什麼應用。
還有現在方法有很多種，像我們知道的這個股票有他自己的方法，我們有看到 一篇 paper 有他自己的方法，可以把股票的資料轉一轉之後，可以用 sequential 的方法，我就可以去解它了。有時候你會覺得這個不一樣，但是事 實上，相同的方法可以應用在不同的地方。那這個是我的最二個 topic。
那最後一個就是談到 mobile 方面的。不曉得你們會不會太累。最後一個我說 mobile database 好像不太對，不過我告訴你們我們在做些什麼東西。所以說 mobile DB 裡面，我們第一個做的就是 location management 這樣的事情，那 location management 是什麼呢？假如說我們這個是一個 celluar 的網路，那 麼我現在我怎麼知道我現在在什麼地方呢？我怎麼讓人家知道我現在在什麼地方 ，好讓人家打電話時找我們。
當然這是一個比較大的範圍，不過我們現在就把他講成一個 cell，那你到這個 細胞裡面你必須去註冊，告訴人家你到哪細胞。所以這個有兩個 cost，一個就 是 registeration，我必須要去註冊。第二個就是 tracking，譬如說人家去找 我的時候有很完整的 data，就很容易找到這個地方。那這裡的確有他的 trade off，如果說你到一個地方你就註冊，你去註冊的 cost 就會很高，但是人家去 找你就會很快。
那麼假如說今天有一個人常常就在這兩個 cell 跑來跑去，卻不太有人去找他 ，那你一直在 register。你當然可以說我把剛剛那個保留，他一直就 delete 掉，假如是這樣的話，你就必須要一直註冊，但是卻沒有人去找你，所以這樣你 就浪費了。我們就是一個想法，根據 user 的 behavior 的角度來看，這個跟 mining 的味道有點像。假如說我能夠知道 user 走的路徑，在這邊晃晃晃的時 候，我就可以把這兩個 cell group 在一起，就規定這個 user 在這邊走來走去 的時候，他不需要註冊，那這個 registeration cost 就變成是 0 了。那麼這 個 tracking cost 就會比較高一點，因為我只知道你是在這區域裡面，但是不 我不曉得你是在這個 cell 或是那一個 cell。所以就是說我可以把 registeration cost 把他降低，但是我這個 tracking cost 可能會稍微增高。 這個 tracking 我當然可以把它 broadcast 到這兩個 cell，或是我根據他在這 邊停留的時間，可能他在這個 cell 的機率比較高，所以先來這個 cell 找你， 找不到再找另外一邊。
所以，我就可以依據他從這邊跑過來跑過去有幾次，形成一個 graph。上面的 weight 代他他從這邊到這邊的次數。我希望從這個 graph 裡面，我去做 grouping，假如說我這個和這個 group 起來，那我怎麼樣 group 起來是比較好 的，那我要去 minimize 這個 location management cost，這個是我的 goal。 我們要做的就是去 grouping，那 grouping 的效應就是這裡面是不需要 register，但是這裡面 tracking cost 會增高。這個地方我們有很多把他 simplify，那事實上一般做這方面的 paper 也是這種情形，有時候做的實際上 比較不去考慮。
再來說這個 data broadcasting 的問題，我就給一個 broadcast channel，你 可以想像成一個圓圈， data 就這樣子跑跑跑，一直繞這樣的東西，然後你要去 拿你所想要的。因為假如說 no index 的時候，那麼這個時候 data 的量是比較 少的，那麼一個 broadcast cycle 是比較小的。假如說你一進去就在這邊聽著 ，那麼 data 一直過去，有你要的 data 你就把它抓出來，這種方式可能就是說 你要一直在這邊聽著。
那另外一種就是你把它 build index，然後你一進去聽的時候，你接收到有一 個 index 的時候，這個 index 會告訴你所想要的 data 再過多久之後會來。所 以這個時候你就可以把你的手機轉到這個所謂的睡眠模式，等著這個東西來的時 候，你再把它開起來，這樣子應該是說會省掉 battery 或是 power。但是因為 你加了 index 進去，有可能會造成你等待的時間會更長，那這個同樣是一種 trade off，到底怎麼樣才是最好的。當然我們在這個地方還有考慮說有些東西 是有問題的，有一些 failure，那你就必須再找到另外一個 index，然後再回到 你原來那種 search 的模式，這個我很不容易講得清楚，不過大致上就是這個樣 子。
然後再來就是說，考慮 multiple channel，假如說有多個 channel 的時候， 那我到底要在多個 channel 裡面，我怎麼把我的 data、我的 index 丟出去， 使得我很快地找到我要的 data。
再來就是說有一種情形，我這個把這些 data 往這些 channel 上面丟，我現在 有 data A,B,C,D 之類的，那有些 user 要的是 A,B,D，有些要的是 A,B,E，有 些是…。那我要怎麼樣去排列我這一些 data，使得每一個 user 都能夠滿意， 能夠很快地得他要的資料。那如果說 D 常常被要求的話，那是不是我們可以把 它複製在這個地方。這樣 broadcast 的時候有很多 D 在這邊繞，那這樣的話比 較容易滿足這一些要求。
那最後一個是，我們還需要野心更大一點，邊做 broadcast 的時候，邊做 data processing。這叫做 database 的 processing，前面我講的叫做 data item，那現在講的是 database，那 database 可能就是一個 table，這就是把 一個 table 在這邊去轉的話要怎麼存。你是一個 tuple 去 broadcast，還是你 把一個個 attribute 去 broadcast，那這個就跟你的查詢有關了。就是說我到 底我要的 data 是怎麼樣子。那這個 query 如果是要某些 attribute 的話，那 我用 attribute 可以比較好的。那如果我這個 query 裡面有這個 table A R1 必須要跟 R2 去做 join 的話，那到底我這個 R1、 R2 要怎麼去擺。假如說我 有一個夠快的 processor，抓到 data 馬上做，可以繼續抓 data，那我要怎麼 樣把我要的 data 擺在這個 broadcast channel，然後很快的去做 query processing。
那麼我想我做的東西大概是這個樣子。
回主頁
演講摘要
相關資料
相關網站