Webpage Extraction - Using Visual Structure and Text Analysis to Label Blocks (Microsoft) - Patent Application - PRIOR ART REQUEST

Question

This Patent Application was given a "final rejection" by the US Patent Office. An applicant has several ways to keep an application in this state alive. They include a request for continuing examination. It just involves paying more fees and responding to the rejection. Appealing the rejection is another avenue. If nothing is done it will go abandoned six months from the final rejection.

Some of the grounds for rejection (can be seen in Public PAIR) are based on scientific publications by the applicants themselves.

Thanks to YOU, the Ask Patents community, overly-broad claims have at least been narrowed. Follow @askpatents to block more overly-broad patent applications.

AN OVERBROAD PATENT ON ANALYZING A WEBPAGE - This application from Microsoft seeks to patent the idea of...extracting information blocks from a webpage based on text and visual layout! 10 minutes of your time can help narrow US patent applications before they become patents. Follow @askpatents on twitter to help.

TITLE: Webpage extraction through page structure and sentences

Summary: [Translated from Legalese into English] A system for extracting entities in a webpage using a text understanding component and a visual layout extraction" component.

• Publication Number: US 20110078554 A1
• Application Number: 12/569,912
• Assignee: Microsoft, Inc.
• Prior Art Date: Seeking prior Art predating Sep 30, 2009

Claim 1 requires each and every step below:

1. In a computing environment, a system comprising, at least one processor, a memory communicatively coupled to the at least one processor and including components comprising, a framework configured to process a webpage to understand one or more entities of the webpage, the framework including

   • a text understanding component and

   • a structure understanding component,

   • the text understanding component configured to provide text-related data to the structure understanding component,

   • the structure understanding component configured to use the text-related data and visual layout features of the webpage to produce a labeled block,

   • the text understanding component configured to use the labeled block to understand text of the one or more entities.

In English this means:

A system for processing a webpage, comprising:

1. A text understanding component; and

2. A visual layout ("structure") understanding component; where

3. The text component provides data to the visual layout component; and

4. The visual layout component produces a labeled block based on the visual layout and the text; and

5. The text understanding component uses the labeled block to "understand" the text of an entity on the webpage

Good prior art would be evidence of a system that did each and every one of these steps prior to the Sep 30, 2009.

"A natural language processing framework for labeling webpages” from Microsoft

---

What is good prior art? Please see our FAQ.

Want to help? Please vote or comment on submissions below. We welcome you to post your own request for prior art on other questionable US Patent Applications.

Answer 1

For reference, excellent prior art was mentioned during examination so far including scientific papers by the same authors. This was probably eased by the fact that this patent application is based on a scientific paper published by the same authors in October 2009, and closest prior art used by examiner was actually provided by applicant as part of the IDS.

Examination has started and the prosecution is currently focused on the first step of the process (what the application calls bi-directional). The method they propose starts with identifying interesting bits in the web page using entity recognition techniques, and then they focus on those parts using structure detection techniques, and finally they extract the entities.

The following prior art dating 2005 actually includes this first step:

• Krüpl, B.; Herzog, M.; and Gatterbauer, W. 2005. Using visual cues for extraction of tabular data from arbitrary HTML documents. In Poster Proc. WWW’05, 1000–1001. ACM. [PDF]

Indeed, Krüpl et al. tries to solve a similar problem (identifying tabular data in web pages) and teaches:

• a text understanding component,

• a structure understanding component,

• the text understanding component configured to provide text-related data to the structure understanding component, (We employ Named Entity Recognizers (NERs) [2] to find interesting text nodes on a given page [section 3]);

• the structure understanding component configured to use the text-related data and visual layout features of the webpage to produce a labeled block [section 4.2 "Detection algorithm"],

• the text understanding component configured to use the labeled block to understand text of the one or more entities [section 4.3 "Table detection"].

Answer 2

First there is Optical Character Recognition http://en.m.wikipedia.org/wiki/Optical_character_recognition, which analyses printed text and looks for visual structures (columns, tables) to produce a digital version of the book or translate a pdf to plain text.

To label parts of a text as a business, person or city you can refer to techniques suchs as Geotagging. An example is http://www.maproomblog.com/2009/05/yahoo_placemaker.php from May 2009. This service analyses a piece of text for reference to locations and returns a set of cities and there likelyhood of being mentioned.

Tagging of other tags in a text is describe in 2006 http://viget.com/extend/tagging-text-automatically. This article mentions another service of Yahoo and one called TagThe.net

And of course there is the scientific field of text mining which exists since 1980. http://en.m.wikipedia.org/wiki/Text_mining There are lots of books/papers on this topic

In my opinion OCR handles point 1 to 4 and 5 is just text mining

Answer 3

While I think that user4857's answer on Text Mining is good, I think it could be said that most text mining services qualify for 1-5.

But I think it's quite clear that Web Mining does cover it quite completely.

Particularly, I'm thinking about those pages that give you custom ads that highlight certain words in the webpages you visit. I can't think of any of those pages offhand, mostly because I don't like pages like that, but they qualify. They even put up a popup on the text to help the user understand (or purchase) the text in question.

Answer 4

In addition to what Paul described above, Avrim Blum and Tom Mitchell, both at CMU, used similar techniques to extract data from web pages. Their work is first described in

Blum, A., Mitchell, T. Combining labeled and unlabeled data with co-training. COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann, 1998, p. 92-100.

This paper does not explicitly mention using visual layout features, but they did later use such features in their work at FlipDog, where they extracted resumes and job listings from web pages in order to populate a new job finder site. I recall this from a talk I attended in 2000, and the technology is described in this 2005 article:

Andrew McCallum. 2005. Information Extraction: Distilling Structured Data from Unstructured Text. Queue 3, 9 (November 2005), 48-57.