Majority schema in semi-structured data

Details Majority schema in semi-structured data Majority schema in semi-structured data

2000-07-27

2003-08-05

Popovici, Dov (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C717S104000

Reexamination Certificate

active

06604099

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of automated information retrieval in the context of document processing. Particularly, the present invention relates to a system and associated method for discovering a majority schema from a set of related documents that share similar but not identical schemas.
BACKGROUND OF THE INVENTION
The World Wide Web (WWW) is comprised of an expansive network of interconnected computers upon which businesses, governments, groups, and individuals throughout the world maintain inter-linked computer files known as web pages. Users navigate these pages by means of computer software programs commonly known as Internet browsers. Due to the vast number of WWW sites, many web pages have a redundancy of information or share a strong likeness in either function or title. The vastness of the unstructured WWW causes users to rely primarily on Internet search engines to retrieve information or to locate businesses. These search engines use various means to determine the relevance of a user-defined search to the information retrieved.
The authors of web pages provide information known as metadata, within the body of the hypertext markup language (HTML) document that defines the web pages. A computer software product known as a web crawler, systematically accesses web pages by sequentially following hypertext links from page to page. The crawler indexes the pages for use by the search engines using information about a web page as provided by its address or Universal Resource Locator (URL), metadata, and other criteria found within the page. The crawler is run periodically to update previously stored data and to append information about newly created web pages. The information compiled by the crawler is stored in a metadata repository or database. The search engines search this repository to identify matches for the user-defined search rather than attempt to find matches in real time.
A typical search engine has an interface with a search window where the user enters an alphanumeric search expression or keywords. The search engine sifts through available web sites for the user's search terms, and returns the search of results in the form of HTML pages. Each search result includes a list of individual entries that have been identified by the search engine as satisfying the user's search expression. Each entry or “hit” may include a hyperlink that points to a Uniform Resource Locator (URL) location or web page.
In addition to the hyperlink, certain search result pages include a short summary or abstract that describes the content of the URL location. Typically, search engines generate this abstract from the file at the URL, and provide acceptable results for URLs that point to HTML format documents. For URLs that point to HTML documents or web pages, a typical abstract includes a combination of values selected from HTML tags. These values may include a text from the web page's “title” tag, from what are referred to as “annotations” or “meta tag values” such as “description”, “keywords”, etc., from “heading” tag values (e.g., H
1
, H
2
tags), or from some combination of the content of these tags.
Automatic programs, such as web crawlers also known as spiders or robots, visit the web sites and extract information. For example, comparison shopping search engines visit web sites describing information, such as prices, and extract semantic information from these sites. Given the format variances between topically related web pages, the retrieved data are oftentimes unhelpful, unrelated or difficult to extract.
The present invention addresses the need to build search engines that allow users to formulate structural queries like “find a student with a Master's degree and a GPA of 3.5 or more and skills in Java.” Heretofore, there is no fully adequate mechanism that allows the extraction of structural information buried in the web pages that cater to the same topic but are authored with significantly different styles.
Several attempts have been made to address this need, exemplary of which are the following references that generally describe methods of investigating the structure of documents and retrieving documents from large databases in response to user queries:
Rodrigo A. Botafogo, Ben Shneiderman, “Identifying Aggregates in Hypertext Structures,” Proceedings of ACM Hypertext '91, pp. 63-74.
IBM Almaden Research Center, “All searches start at Grand Central,” Network World, front page, November 1997.
Tao Guan, Kam-Fai Wong, “KPS: a Web Information Mining Algorithm,” WWW8/Computer Networks 31(11-16): 1495-1507 (1999).
Seongbin Park, “Structural Properties of Hypertext,” Proceedings of the Ninth ACM Conference on Hypertext, pp. 180-187, 1998.
Svetlozar Nestorov, Serge Abiteboul, Rajeev Motwani, “Inferring Structure in Semistructured Data,” SIGMOD Record 26(4): 39-43 (1997).
Svetlozar Nestorov, Serge Abiteboul, Rajeev Motwani, “Extracting Schema from Semistructured Data,” SIGMOD Conference 1998, pp. 295-306.
Ke Wang and H. Q. Liu, “Discovering Association of Structure from Semistructured Objects,” IEEE Trans. on Knowledge and Data Engineering, 1999.
U.S. Pat. No. 5,694,592 to Driscoll describes a method of querying and retrieving documents from a database using semantic knowledge about the query string to determine document relevancy.
U.S. Pat. No. 5,848,407 to Ishikawa describes a method of presenting potentially related hypertext document summaries to a user who is using a search engine that indexes a plurality of hypertext documents.
However, the need for a system and associated method for discovering a majority schema (also referred to herein as common schema) from a set of related documents that share similar but not identical schemas has remained unsatisfied. For example, consider HTML documents, such as resumes, that describe the same concept but are marked up differently. Some authors may describe the degree by date, name, and the institute granting the degree, while other authors may describe the degree by name, institute granting the degree, and the date. Prospective employers searching for potential candidates may not pay attention to the order of description, and would rather have all degrees described in a conventional order. In addition, some candidates may include hobbies session in their resume, which information may be largely overlooked by employers. Briefly, prospective employers prefer to have a uniform view of the majority of the documents and search the repository of documents under such view.
Existing approaches do not offer a “majority schema” which is shared by most of the documents being searched, which presents a uniform and summary view of these documents and that can be used to guide the transformation of the HTML documents to a global schema in data integration. This need has heretofore remained unsatisfied.
SUMMARY OF THE INVENTION
The present invention teaches a schema discovery system and associated method that satisfy this need. In accordance with one embodiment, the system discovers a majority schema for a set of related and similarly marked up documents, such as HTML documents, based on the assumption that though the structure of these documents is mostly for visual purposes, the keywords used in the documents along with the structural tags provide some hints, and allow a rough sketch of the underlying intended schema. It is further assumed that albeit the set of HTML documents are marked up differently due to diverse authoring skills, they are closely related in content. Therefore, it is reasonable to assume the presence of a schema that can unify these different schemas, which schema is shared by the most (i.e., majority) of these HTML documents.
The copending U.S. patent application Ser. No. 09/531,019 generally describes a process that uses visual clues and structural tags to extract basic schematic structures of HTML documents. The present invention describes a method that reconstructs a majority of schemas from these schematic structures. It also proposes constraints-based mec

Affiliated with

Also associated with

Rating

Majority schema in semi-structured data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Majority schema in semi-structured data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Majority schema in semi-structured data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3094378