![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website-structure-understanding-and-its-applications-2.jpg\")
Website structure understanding can be treated as a reverse engineering for the purpose of automatically discovering the layout templates and URL patterns of a website, and understanding how these templates and patterns are integrated to organize the website. The study of this problem has had a great impact to many applications which can leverage such site-level knowledge to help web search and data mining.<\/p>\n
Almost every website on the Internet has a distinct design & organization structure. Experienced website designers usually create distinguishable layout templates for pages of different functions. They then organize the website by linking various pages with hyperlinks, each of which is represented by a URL string following some pre-defined syntactic patterns. This project is a reverse engineering to automatically discover the layout templates and URL patterns of a website, and understand how these templates and patterns are integrated to organize the website. To demonstrate the power of website structure understanding, this project also proposes some applications which leverage such site-level knowledge to help web search and data mining.<\/p>\n\t
We first give a brief introduction to the concept \u201cwebsite structure\u201d defined in this project, and then present the basic flowchart and methods currently developed to automatically mine the website structure of a given website.<\/p>\n
In this project, the website structure consists of three components: layout templates, URL patterns, and linkage structure.<\/p>\n
Most web pages consist of HTML elements like table, menu, button, image, and input box. The layout of a web page describes what HTML elements are included in the page, as well as how these elements are visually distributed in page rendering. Essentially, a page layout is represented by a so called DOM (Document Object Model) tree. In this project, a layout template is considered as a group of pages which have very similar layouts (DOM trees).<\/p>\n
In a website, pages are generated based on distinguishable templates according to their functions. That is to say, visually similar pages usually have same function. In this way, user can easily identify a page\u2019s function at a glance. Following are several typical layout templates identified from the ASP.NET Forums. Their functions are to show a) a list of discussion thread, b) a list of thread posts, and c) user profile, respectively.<\/p>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-aspnettemplates.jpg\")
Fig. 1. Typical layout templates from the ASP.NET Forums. They are designed to show a) a list of discussion thread, b) a list of thread posts, and c) user profile, respectively.<\/p><\/div>\n
A URL pattern is a generalization of a group of URLs sharing similar syntactic format. In general, a URL pattern can be represented with a regular expression.\u00a0Following we show some example URL patterns discovered, again,\u00a0from the ASP.NET Forums.<\/p>\n
It\u00a0is noticed that one layout templates can have more than one related URL pattern. For example,\u00a0a bookseller website usually designs one template to show a list of books,\u00a0and\u00a0provides\u00a0different query parameters to generate such a list. Various query parameters in this scenario will lead to different URL patterns, but the search results are shown with the same template. Another common case is duplicate pages, i.e., pages with the same content (and very likely the same layout)\u00a0but different URLs.<\/p>\n
Based on the layout templates and URL patterns, we can construct a directed graph to represent the website organization structure. That is, each layout template is considered as a node in a graph, and two nodes are linked if there are hyperlinks between the pages belonging to the two nodes. The link direction is the same as the related hyperlinks.\u00a0And each link is characterized with the URL pattern of the corresponding hyperlink URLs. Again, it should be noticed that\u00a0there could be multiple links from one node to another if the corresponding hyperlinks have more than one URL pattern.<\/p>\n
Fig. 2 gives an illustrative example of\u00a0the sub-graph constructed based on the layout templates and URL patterns above.<\/p>\n
To automatically discover the organization structure of a given website,\u00a0an unsupervised pipeline was proposed in this project. The basic idea is to first sample a few pages randomly from the target website, then discover layout template and URL patterns by grouping these sampled pages, and finally reconstruct the link graph. Figure 3 shows the flowchart of the pipeline, which consists of four components: random sampling<\/em>, page layout grouping<\/em>, URL pattern discovery<\/em>, and link structure reconstruction<\/em>.<\/p>\n The goal of random sampling is to provide a snapshot of a website by downloading only a relatively small number of pages. The sampling quality is the foundation of the whole mining process. To keep the downloaded pages as diverse as possible, in practice the sampling process adopts a strategy\u00a0combining both breadth-first and depth-first, and can quickly retrieve pages at deep levels within a few steps.<\/p>\n Pages with similar layout usually have similar HTML components. Fig. 4 gives an illustrative example. In Fig. 4 there are four pages from the website of Amazon, two of them are detailed pages of product introduction; while the other two are pages of help. Some salient HTML components in these four pages are marked with color ellipses. It is clear that similar layout have similar HTML components.<\/p>\n Inspired by this observation, in this project, DOM path is utilized to characterize the layout of a webpage. As shown in Fig. 5, a DOM path is a path from a leaf node to the root\u00a0of the DOM tree. The leaf node indicates the\u00a0component type, and the path-to-root approximately describes the visual location of that component in page rendering.<\/p>\n Given a set of HTML pages, all unique DOM paths are extracted to form a feature space. Each page is represented by a point in the feature space, and the layout similarity of two pages can be estimated. A bottom-up strategy is then utilized to group similar pages, and each cluster is considered as a layout template.<\/p>\n A URL is not an ordinary string but has a syntax structure scheme strictly defined by W3C standards. Based on a syntax structure, a URL string can be represented by a group of key-value pairs. Fig. 6 gives an example URL, its syntax structure, and the corresponding key-value pairs.<\/p>\n It is noticed that different URL components (or keys) usually have different functions and play different roles in a website. In general, keys denoting directories, functions, and document types are with only a few values, which should be explicitly recorded in a URL pattern. By contrast, keys denoting parameters such as user names are with quite diverse values, which should be generalized in the pattern.\u00a0Based on this observation,\u00a0a top-down recursive split process is proposed in this project to construct\u00a0a pattern tree to characterize a set of URLs. Fig. 7 gives an example pattern tree\u00a0based on\u00a0URLs from www.wretch.cc. Algorithm details please refer to [9].<\/p>\n Once the layout templates and URL patterns are avaliable, the construction of the link graph is\u00a0quite straigthforward. Two layout templates are linked if there are links between pages belonging to the two templates, and the link is characterized with the URL pattern of the corresponding pages.\u00a0Algorithm details please refer to [1-3].<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t Website structure information, as a kind of site-level knowledge, can help a lot of applications in web search and data mining. Currently, we have demonstrated the power of website structure information in two areas: 1) improving index quality of a search engine and 2) structure data extraction and mining.<\/p>\n Index quality is very critical to a search engine. Website structure information provides site specific knowledge and can help improve\u00a0the quality of a search engine\u00a0index.<\/p>\n Not all the pages in a website are\u00a0valuable to a search engine. For example, private\u00a0pages\u00a0may redirect the crawler to a login portal page. And for vertical search, only a part of pages\u00a0containing related information are worth crawling. Focused crawling is to optimize the bandwidth and download as many targeted pages as possible. With the mined site-level link graph, we can provide better strategy to do focused crawling.<\/p>\n In this project, we take web forum crawling as an example to show how such site-level structure information is useful. A framework was proposed in [1] to fetch a forum more efficiently and effectively. Around 50%\u00a0bandwidth can be saved by\u00a0only downloading list-of-thread and list-of-post pages and discarding valueless supplementary pages. The crawling traversal strategy was further improved in [2] to increase the performance. Targeted on incremental crawling, a list-wise strategy was developed in [3] to fetch newly published posts in the first time.<\/p>\n Ongoing work is to extend the focused crawling to websites general than forums. The basic idea is to\u00a0assign higher priorities to those pages important to users. Such a priority is assigned to a layout template or a URL pattern, instead of to individual pages.<\/p>\n Duplicate URLs have brought a series of troubles to a search engine. URL normalization is to rewrite a set of duplicate URLs to a canonical form. In this project, a pattern tree-based approach was proposed in [9] to automatically generate rewrite rules.\u00a0Instead of previous\u00a0research efforts working on\u00a0individual duplicate pairs, pattern tree provides statistical information of all duplicate pairs in a website. In this way, we can accelerate the learning process and generate more reliable rewrite rules. Fig. 8 shows the flowchart of this approach.<\/p>\n Previous\u00a0research on structured data extraction usually only works on process individual pages. The noise\u00a0information on\u00a0single page is easy to distort the extraction results. In contrast, if consider multiple pages having the same layout template, we can obtain relatively robust template-level statistical information and help improve the performance of structured data extraction.<\/p>\n Based on the site-level layout templates, a novel approach was proposed\u00a0in [4] to extract structured data like title\/author\/publish-date from web forums. Besides features extracted on a single page, we also leverage features extracted from cross pages.\u00a0Experimental results show that cross page features significantly improve the performance.<\/p>\n Ongoing work is to extend this\u00a0idea to\u00a0websites general than forums.<\/p>\n In this project, we also did data mining on web forums based on the extracted structured data. For example, a sparse coding approach was proposed in [5,6] to simultaneously model both\u00a0semantics and structure of discussion threads in forums. And we also investigated the user grouping behavior in forums in [7]; as well as mined reply relationships among posts in [8].<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t Special acknowledgement to team members who once contributed to, or are still working on, this project.<\/p>\n Rui Cai<\/a>, Jiang-Ming Yang (opens in new tab)<\/span><\/a>, Lei Zhang<\/a>, Wei Lai, Zhiwei Li, Xin-Jing Wang, Wei-Ying Ma<\/a><\/p>\n Yida Wang, Hua Huang, Tao Lei, Chunsong Wang, Chen Lin, Jun Zhu (opens in new tab)<\/span><\/a>, Bailu Ding (opens in new tab)<\/span><\/a>, Xiaolin Shi (opens in new tab)<\/span><\/a><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t\t\t\t\t<\/ul>\n\t<\/div>\n\t\n","protected":false},"excerpt":{"rendered":" Website structure understanding can be treated as a reverse engineering for the purpose of automatically discovering the layout templates and URL patterns of a website, and understanding how these templates and patterns are integrated to organize the website. The study of this problem has had a great impact to many applications which can leverage such […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"research-area":[13555],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-170515","msr-project","type-msr-project","status-publish","hentry","msr-research-area-search-information-retrieval","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2010-08-12","related-publications":[159466,159484,159485,159486,159487,159488,161608],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[],"msr_research_lab":[199560],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170515\/revisions"}],"predecessor-version":[{"id":392363,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170515\/revisions\/392363"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=170515"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=170515"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=170515"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=170515"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=170515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-link_graph.jpg\")
Fig. 2 An illustrative sub link-graph for the ASP.NET Forums.<\/span><\/span><\/p>\nUnderstand Website Structure<\/h2>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-flowchart.jpg\")
Fig. 3. The flowchat of the proposed pipeline for website structure understanding.<\/span><\/span><\/p>\nRandom Sampling<\/h3>\n
Page Layout Grouping<\/h3>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-page_grouping.jpg\")
Fig. 4. Four pages from the website of Amazon. It clear that they have different HTML elements (marked with color ellipses) and can be categorized into two layout templates.<\/span><\/span><\/p>\n![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-dom_path.jpg\")
Fig. 5. An illustrative example of a (patial) DOM tree and some extracted DOM paths as features for page layout grouping.<\/span><\/span><\/p>\nURL Pattern\u00a0Discovery<\/h3>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-url_syntax.jpg\")
Fig. 6. An illustration of the syntax structure of a URL, based on which it can be described as a set of key\u2013value pairs<\/span><\/span><\/p>\n![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-pattern_tree.jpg\")
Fig. 7. An illustration of the pattern tree based on URLs from www.wretch.cc. The tree has been simplified for a clear view.<\/span><\/span><\/p>\nLink Structure Reconstruction<\/h3>\n
\n\t\t\t\n\t\t\t\t<\/p>\nImproving Index Quality of a Search Engine<\/h2>\n
Focused Crawling<\/h3>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-forum_crawl.jpg\")
Fig. 7. An illustration of focused forum crawling.<\/span><\/span><\/p>\nURL Normalization for Duplication Deduction<\/h3>\n
![\"\"](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/website_structure_mining-url_norm.jpg\")
Fig. 8. The flowchart of the pattern tree-based approach to learn rewrite rules for URL normalization.<\/span><\/span><\/p>\nStructured Data Extraction and Mining<\/h2>\n
Structure Data Extraction<\/h3>\n
Modeling Semantics and Structure of Forum Thread<\/h3>\n
\n\t\t\t\n\t\t\t\t<\/p>\nResearchers<\/h3>\n
Interns<\/h3>\n