System and method for automated content aggregation using knowledge base construction

A method for enabling automated content aggregation based on deep Web sources, comprising: analyzing a plurality of deep web sources to detect a plurality of fields; selecting at least one field; and aggregating content provided to a plurality of deep web sources through said at least one field.

FIELD OF THE INVENTION

The present invention relates to systems and methods useful in developing knowledge bases. Specifically, embodiments of the present invention relate to automated knowledge base configuration and development.

BACKGROUND OF THE INVENTION

The Deep Web is the part of the Internet that is inaccessible to conventional search engines, and consequently, to most users. Deep Web content includes information in private databases that are indirectly accessible over the Internet but not crawlable by typical search engines. For example, libraries maintain data bases of books that are accessible to the public but in order to access them a user needs to fill out a web form in order to access the content.

In general, it is assumed that deep Web was growing much more quickly than the surface Web and that the quality of the content within it was significantly higher than the vast majority of surface Web content. Although most of this content is publicly available, it's accessibility to typical Internet end users is very limited.

It would be highly advantageous to have a platform that would enable end users to effectively configure and access surface web and deep web data sources remotely.

Implementation of the method and system of the present invention involves performing or completing certain selected tasks or stages manually, automatically, or a combination thereof. Moreover, according to actual instrumentation and equipment of preferred embodiments of the method and system of the present invention, several selected stages could be implemented by hardware or by software on any operating system of any firmware or a combination thereof. For example, as hardware, selected stages of the invention could be implemented as a chip or a circuit. As software, selected stages of the invention could be implemented as a plurality of software instructions being executed by a computer using any suitable operating system. In any case, selected stages of the method and system of the invention could be described as being performed by a data processor, such as a computing platform for executing a plurality of instructions.

Although the present invention is described with regard to a “computer” on a “computer network”, it should be noted that optionally any device featuring a data processor and/or the ability to execute one or more instructions may be described as a computer, including but not limited to a PC (personal computer), a server, a minicomputer. Any two or more of such devices in communication with each other, and/or any computer in communication with any other computer may optionally comprise a “computer network”.

The present invention relates at least partly to a method for enabling automated content aggregation based on deep Web sources, comprising: analyzing a plurality of deep web sources to detect a plurality of fields; selecting at least one field; and aggregating content provided to a plurality of deep web sources through the at least one field. The present invention also relates at least partly to a method for automatically generating domain based knowledge bases based on deep Web sources, comprising: selecting a plurality of deep web sources according to a domain; analyzing the plurality of deep web sources to detect a plurality of fields; selecting at least one field at least partially according to the domain; and aggregating content provided to a plurality of deep web sources through the at least one field.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the drawings have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the drawings to indicate corresponding or analogous elements throughout the serial views.

DETAILED DESCRIPTION OF THE INVENTION

The following description is presented to enable one of ordinary skill in the art to make and use the invention as provided in the context of a particular application and its requirements. Various modifications to the described embodiments will be apparent to those with skill in the art, and the general principles defined herein may be applied to other embodiments. Therefore, the present invention is not intended to be limited to the particular embodiments shown and described, but is to be accorded the widest scope consistent with the principles and novel features herein disclosed. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

The term “deep web” as used herein may encompass the Deepnet, the invisible Web, the dark Web, the hidden Web or other terms representing data sources that are not typically indexed by the standard search engines. The term “surface web” as used herein may encompass the visible Web or indexable Web, or other parts of the World Wide Web that is indexed by conventional search engines.

Non-limiting embodiments of the present invention enable automated knowledge base construction for extracting information from deep web resources, according to some embodiments. In some embodiments, the system may be used to automatically build domain specific knowledge bases substantially without prior knowledge of fields or values associated with the domain knowledge bases being built. Further, in some embodiments, the system may be used to automatically create a unified, normalized Database of deep web content from multiple data sources, whether the sources are surface or deep. In additional embodiments the system may be used to facilitate automated user designed field searches.

Reference is now made toFIG. 1Awhich is a system diagram describing a system enabled to execute automated knowledge base construction of deep web resources, according to some embodiments. As can be seen inFIG. 1A, Knowledge Base Construction System (KBCS)100may be in communication with external databases101, which are optionally deep web databases, accessible through web site interfaces102, or other suitable interfaces, in order to fetch data from related sites. KBCS100may feature a Deep Web crawler105for crawling Websites internally for content and forms (or other entry points) to access data content relating to a search request.

Deep Web crawler105retrieves information as described for example in U.S. patent application Ser. No. 12/567,773, filed on 27 Sep. 2009, owned in common with the instant application and hereby incorporated by reference as if fully set forth herein. queries related sites and analyzes the result retrieved from each site. Such results can be retrieved from HTML/XML pages or from any other text format pages. According to this embodiment, a web browser104optionally applies its rendering composer engine on the HTML document to determine one or more geometrical properties of the document, for example optionally by generating a Document Object Model (DOM) tree, wherein each mark-up language tag (such as each HTML or XML tag) is associated with a node in the DOM-tree. For each node in the tree, the browser104also associates its geometrical representation for rendering the corresponding web page. The geometric representation is denoted, for example, by the XY origin offset, width, height and the like. The geometrical properties of such a tree are preferably analyzed to determine the layout of the document. Information is preferably then retrieved from the document according to the document layout. Optionally, semantic analysis is also applied as described in greater detail below.

In some embodiments Website lists may be generated by domain based crawler112, an operator, machine or any combination. Sites list109can optionally reside in a file or alternatively be collected by domain based crawlers112, for example, a specialized crawler that collects sites relevant for a certain domain (ie—for a certain area of knowledge or of interest, which searches for web sites having specific content). For example, domain based crawler112may optionally be provided with a list of content terms or with a collection of relevant web sites, and then searches for relevant web sites according to the terms and/or other information in the provided relevant web sites. Deep Web crawler105may use Website lists109, generated by Domain Based Crawler112which is configured to run code to search for Websites relevant to a search request or field, to populate Websites list109.

It is noted that the Deep Web crawler105may, if and when needed, execute automated web-form filling. For example, Deep Web crawler105may use the knowledge base Constructor114(described in greater detail below) to generate relevant queries in order to fill out the relevant web-forms in order to access selected data sources. Knowledge base constructor114receives the decomposed web page, which is decomposed by analyzing the page with the geometrical analyzer, which determines the record listings, without content analysis. Knowledge base constructor114analyzes the content in order to search for repeating terms and hence for repeating fields. The field may optionally be determined only according to location or only according to semantic analysis (such as a specific term or terms), but is preferably determined according to a combination of such parameters.

Knowledge base constructor114repeats this process for a plurality of web sites, and then cross-analyzes the fields and content for the plurality of web sites, for example to determine equivalent terms (such as for example “make” vs. “manufacturer”). Preferably fields of importance are determined according to statistical analysis of equivalent terms, such that the most frequently appearing fields are considered to be important. Knowledge base constructor114also preferably eliminates fields as being less important by detecting fields that do not appear in many web sites by statistical analysis. Preferably only the most important terms, according to statistical weighting, are then retained by knowledge base constructor114.

Knowledge base constructor114is preferably first trained on highly structured web sites, for which the geometric analyzer107is able to more easily decompose the web sites into a plurality of fields. However, once knowledge base constructor114has been trained on some minimum number of web sites (which may for example optionally be set by an administrator user), then knowledge base constructor114is more easily able to analyze less structured web sites.

KBCS100may feature a Scheduler106, which may run a program to control or manage the instructions to Deep Web crawler105. For example, scheduler106may schedule the crawler105to automatically query the data bases101via the web sites interfaces102in order to retrieve relevant or updated data. In one example, such data being searched may be art gallery events, where a user wants to learn about upcoming art exhibitions in the world or in a region. In such as example, the KBCS System100will search and aggregate requested data from multiple art sites in accordance to the definitions of the search request entered.

System100may include a visual or Geometric analysis module107, for using geometrical analysis of Web forms, tables, listings, text and other formats. In one example, a geometrical analysis tool such as that taught in the previously described U.S. patent application Ser. No. 12/567,773. Geometrical analyzer107typically receives the rendered pages from crawler105, including the DOM-tree along with page geometric representation. The geometrical analyzer107analyzes the regularities on a selected web page layout and decomposes the web page into records110representing reoccurring sequences (patterns). In some embodiments, the geometrical analyzer finds regularities in the layout of web pages and creates a pattern for each such reoccurring (regular) sequence.

System100further includes a Knowledge Base Constructor module114, which is an active module configured to run code or programs to communicate with geometrical analyzer107to receive at least the geometrically decomposed pages. In some examples the geometric analyzer107may execute code to decompose a webpage into records, from which patterns may be identified. Such patterns may initially be identified within a single webpage, yet once found, these patterns may be matched with other pages of the website. Optionally, a semantic module (not shown) may further analyze the text within the matched pattern. The knowledge base creator114may also be in communication with Deep web crawler105. In some embodiments, Deep Web crawler105may execute instructions to search for a link to the next results page preferably only if the page has been identified as a relevant results page. Knowledge base Constructor114may run code to identify the fields that comprise records of the Deep Web source sites, and may execute a program to create a knowledge base, based on the description above, and the workflow described below with reference toFIG. 2.

Constructor114may, for example, utilize records generated by Geometric Analyzer107and compare/process and compile meaningful records, for example, the analysis may be done, for example, by comparing the different records of each site to each other and analyzing repetitive and non repetitive parts of the records. The knowledge base creator114may use records data110, and optionally communicate with deep web crawler105, to integrate data based on previous queries from records110, and to optionally generate new queries in addition deep web sites. The knowledge base is a database that may contain semantic information relevant to one or more selected domains, such as field names, potential values, recognition rules and more.

According to some embodiments, Knowledge base creation module114may be used to analyze the text in the patterns recognized by the visual analysis, to identify structures that may be used for automated formation of fields and values relating to specific data fields. For example, Knowledge base construction module114may run an analysis on the records of art galleries, and identify common fields such as dates, addresses, artists etc. that are in common in multiple sites. Initially such an analysis may be run on a single site, and subsequently it may be run on multiple other sites, using cross referencing by analyzing field names/field values similarity. In this way, KBCS system100is able to use automated analysis of geometric + semantic results to provide dynamic, growing and learning databases and lists of field and value specific content from deep web and surface web data sources.

In some embodiments there may be no need for the list of websites to scan109and/or the scheduler106, since the Knowledge base creation module114may facilitate substantially real time configuration and searching of selected queries by an end user.

In some embodiments, in a second phase, as can be seen with reference toFIG. 1B, the KBCS system may execute an Aggregation Engine or Module130to help automatically construct a search results database135. Aggregation module130receives records from knowledge base creator module114and then constructs a database of aggregated results from all examined relevant web sites. The results of the analysis may comprise, for example, records, data and links to the relevant web pages, which may be stored in search results data base135.

When a user queries for information, such as, for example a list of all higher education programs in the user's area, using for example a search engine111, the information is retrieved from the results data base135. Optionally an automated user may request the information, such as an automated feed provider. The information delivered to the requesting entity preferably comprises data and links to relevant sites for retrieving additional data, according to the analysis performed above.

Reference is now made toFIG. 2, which describes an implementation of the Knowledge base creation module200, according to some embodiments. Knowledge base creation module200may feature a Field/value Recognition module210to identify similar fields that are described in different ways in different sites. Such an identification may allow normalization of substantially same fields from different data sources into one consolidated database. Field/value Recognition module210, as described previously for Knowledge base creation module114, recognizes the fields as being fields, according to repeat structure and/or content. Field/value Recognition module210then determines the type of values that may be found in such a field.

Knowledge base creation module200may further feature a Field Ranking module220, for identifying ranking of fields based on repetition/usage in the source sites. Greater frequency with which the field appears in a plurality of web sites is one non-limiting example of a parameter which may increase the importance of a field. Another non-limiting example of such a parameter is the connection between a particular field and other fields. Yet another non-limiting example of such a parameter is the content of the field, which may optionally for example be determined to be important.

The Knowledge base creation module200may further feature a Refinement module225, for analyzing the ranked fields to improve machine confidence and accuracy of the operation of Knowledge base creation module200. Refinement module225determines which fields are clearly correctly designated as fields and also determines which fields are clearly not correctly designated (for example terms that do not repeat across many web sites or that do not repeat within a band of statistical confidence). Fields which are clearly not correctly designated as such are preferably removed. Terms which may or may not represent field labels are preferably further analyzed to determine whether they are to be accepted as fields or not.

For example, after understanding similarity of structures in a single site, and subsequently verifying and improving the identification of such structures across multiple sites, the Refinement module225can generate greater confidence and accuracy by learning from previous experience in identifying structures, such that when identified and verified structures are seen again, the probability of identification with increasing accuracy increases.

Knowledge base creation module200may further feature an Expansion module230for preferably expanding the analysis to other web sites for expanding scope and accuracy. Expansion module230considers the degree of statistical confidence of the known fields and also how much more information was added in the last iteration. If a statistically significant amount of information was added in the last iteration, expansion module230determines how many more web sites should be considered in a new iteration. Alternatively, expansion module230may optionally determine that a significant amount of new information was not added in the last iteration and so the iterations may be finished.

According to some embodiments, expansion module230can define limits or thresholds at which to start expansion to analyze more new web sites. For example, the module may determine that once a selected confidence level of field identification has been achieved, then a further number if sites may be crawled and processed. On the other hand, if a selected threshold of accuracy has been reached, such that further expansion will not be expected to enhance accuracy substantially, the expansion module may determine that no more expansion be required or executed. Expansion module230may be in communication with domain based crawler205, for new sources from which to add data to the domain knowledge base. Of course, other structures and dimensions, or combinations of elements, may be used.

The above described modules may be used to automatically derive a Domain Knowledge base250, in accordance with the descriptions above and with reference toFIG. 2.

In an additional phase, domain knowledge base250may be used in conjunction with aggregation module260to generate a results database240.

The above described components of the KBCS system100may work together to generate automated field-specific knowledge bases, thereby enabling highly accurate delivery of field data and values in accordance with user requests. Further, such knowledge bases may be based on unlimited data sources, whether surface web and/or deep web. Additionally, the system100learns and grows in accuracy as the number of sources used to contribute to the knowledge base increases.

In accordance with an example of a work flow used in executing an automated knowledge base configuration of deep web resources, field/value recognition module210may optionally identify similar values from field analysis based on multiple field based sources; this module may also additionally optionally refine value certainly based on quantity of sources and by following internal links from sources. Field ranking module220may optionally perform ranking to identify ranking of fields based on repetition/usage parameters. Refinement module225may optionally grow or develop machine confidence and accuracy based on refining and correcting knowledge base records. Expansion module230may optionally expand the scope and accuracy of the knowledge base, by including automated expansion to new sources, and processing/refining of new knowledge base elements. Any steps or combination of the above steps may be implemented. Further, other steps or series of steps may be used.

Reference is now made toFIG. 3, which is a flow chart showing an example of a process in which a Domain Knowledge base is generated, according to some embodiments of the present invention. As can be seen inFIG. 3, at stage305records may be automatically extracted, using visual, geometric and/or structural analysis, from Websites' results pages or other relevant pages, as previously described (for example optionally by using DOM-trees, also as previously described). At stage310fields may be extracted, along with their associated values from the extracted records by analyzing recurring patterns within the extracted records. Again as previously described, such recurring patterns may optionally be analyzed statistically in order to determine the significance of such patterns and/or optionally in order to eliminate patterns that are less important or non-important.

At stage315fields may be mapped or consolidated from one or more sites, for example, according to field name and field value similarity. Such mapping enables similar fields having similar content to be grouped together for example, so that synonymous or similar names (or field labels) and/or content may optionally be grouped according to their degree of similarity. At stage320fields may be ranked, for example, based on the frequency of their occurrence in the source sites. At stage325the system confidence or level of accuracy may be refined, for example relative to top ranked fields and values. At decision stage330, the Constructor considers or determines whether substantial new fields or values were discovered. If not, then a field and values entries may be added into the knowledgebase, at stage335. If a substantial number of new fields or values were discovered at stage330, then at stage340new sites may be added for processing, using the expansion step.

According to some embodiments, the system may be used to automatically build field specific knowledge bases without prior knowledge of fields or values associated with the field knowledge bases being built.

According to some embodiments, the system may be used to automatically develop a unified, normalized Database of deep web content from multiple data sources, whether the sources are surface or deep.

According to some embodiments, the system may be substantially language independent, since the visual analyzer enables patterns to be recognized and fields and values to be accurately synchronized and refined in spite of specific languages used in the knowledge base sources.

The foregoing description of the embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. It should be appreciated by persons skilled in the art that many modifications, variations, substitutions, changes, and equivalents are possible in light of the above teaching. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.