On the Study of an Automatic Data Extraction Algorithm for Dynamic Web Pages

In this project, we will research on the designing of a new algorithm which can perform schema detection of web databases from the retrieved web dynamic pages. Specifically, the task of the algorithm is to discover the templates or patterns of database tables in order to facilitate the web information integration or other agent-based processing. Most of the valuable information provided on web pages is produced by applying some layout templates on source web database tables. The templates, or patterns, arrange the fields of a data record where and how to be displayed on a page. However, the HTML codes seen by users are only composed of tags and text only. This makes the automatic web data extraction become a complicated task. The direction of this project will be making use of the characteristics of DOM (document object model) trees to design a new leaf nodes representation and comparison method. We hope that the proposed method will have better performance in schema detection in terms of efficiency and accuracy. We will labor on this project by focusing on the designing of the new similarity evaluation methods among subtrees in DOM trees. It is because these are the two major tasks of a graph-based data mining method. We intend to design the method to have the advantage of efficiency and accuracy. Besides, we will also consider the contents of the texts, which may be the values of table fields, in accordance with tag structures to perform schema inference of database tables. The main components of this project are: (1) Design the matching method of data paths This process is divided into two parts further. The first part is to consider the data paths formed by the tags from the root to a leaf node. We plan to design a compact style of path codes and to use the path codes to evaluate the similarity of subtrees, which will also divide subtrees into groups. The second part is to design the merging and pruning methods of candidate groups. We plan to design a new method makes use of the visual information of data objects. (2) Design the method of positioning the data areas This process is to discover and prune the non-data areas such as advertisement and logo statement areas. However, the challenge is to handle the problem about the similarity between data and non-data areas. We plan to employ the visual characteristics of the area blocks shown by browsers such as size and position. (3) Design the method of aligning fields To capture the data on dynamic pages into the correct fields of database tables is the ultimate goal of automatic web data extraction systems. It is a challenge when designing this algorithm to align corresponding fields because some fields are optional, i.e., some fields are not shown in some records. In conclusion, the project will be completed by designing an automatic data extraction method for finding the schema of the tables in web databases. This method will discover the templates or patterns of dynamic pages and infer the schema of tables. The proposed method can be applied to the areas which need to perform web data integration or analysis. We will implement the proposed method and compare it with some well known methods for efficiency[[abstract]]資料擷取、演算法、網路探勘、網路資訊系統、動態網頁語意，並以路徑碼來判斷子樹間結構的相似度，藉以將相似度超過門檻的子樹初步分為同一群。 (2) 設計資料區域擷取目標標定的方法： 此部分主要是找出淘汰非「資訊區域」(data area)的方法，因為雜訊區塊在DOM Tree中也會擁有類似的結構，很容易會被誤判為資料區域。因此我們將設計資料區域擷取目標標定的方法，初步構想是藉由區塊在瀏覽器顯示時呈現的空間特徵如位置與大小等，作為選擇的依據。 (3) 設計資料項目對齊演算法： 經過了分群、合併與過濾之後，最終的目標將網頁上的資料自動轉成資料表儲存，以利後續的分析與整合。因為在呈現時有些欄位是「可選的」(optional)，亦即某些欄位在某些紀錄中不會出現，如何進行「欄位對齊」(attribute alignment)，讓紀錄與欄位作正確的對應，是演算法設計的挑戰。 綜合以上敘述，本計畫將設計一個自動化資料擷取方法，功能為發現網頁中的「型樣」或「樣版」，推定伺服器資料庫中資料表的「欄位結構」(schema)，以利後續進行網路資料的整合。我們預計將要實作所提出的擷取演算法，並且與幾個具有代表性的方法比較其效果