Contributions to large-scale information acquisition from the Web

Abstract

TheWorld WideWeb offers an increasingly huge and rapidly changing amount of information. Automatic web information extraction approaches aim to use this available source of information to create structured databases that allow subsequent querying of information. This thesis addresses two principal questions arising in this context: (i) what is the theoretic effectiveness of automatic web information acquisition presuming that the distribution of information on the Web follows some kind of power law; and (ii) how can automatic information acquisition systems utilize the readily available meta information encoded in the current Visual Web without the need to resort to a future Semantic Web? The first part develops the mathematical tools necessary to describe the effects of redundancy and bias on the overall theoretic efficiency of an information acquisition process from many distributed data sources, such as those found on the Web. For this purpose, an intuitive efficiency measure called unique recall is developed as a function of the overall shape of redundancy and the crawled fraction of the Web. Following a limit value consideration, complete mathematical descriptions and general constraints on this measure are derived. These mathematical tools are then applied to example redundancy distributions with a particular emphasis on power laws, the commonly found pattern of bias in information dissemination.<br />The second part investigates how redundancy distributions evolve as a whole in sampled data as function of the original redundancy distribution and the sampled fraction. The thus derived equations allow estimating the influence on the reliability of the information acquisition process. One particular result is the description of a power law like family of redundancy distributions which keeps its overall shape during a sampling process and, thus, remains invariant during a process of information acquisition. This part finishes with the still-to-verify conjecture that this invariance is one reason for the ubiquity of power laws in information systems involving not only multiplicative growth processes, but also iterative renewal processes.<br />The third part starts from the observation that much information in the Web, as we know it today, is originally encoded in a visual rather than a semantic or semi-structured language. Following this idea, a visual model of the representation of information on the Web is developed.<br />Methods and algorithms are then described of how to use this model to recognize and extract tables from web pages. A method for ground truthing of arbitrary web tables is sketched and a simple implementation of the extraction method is finally evaluated on a broad test set of web tables.<br />

Das Internet bietet eine rasant wachsende und sich stetig ändernde Menge an Informationen. Automatisierte Ansätze zur Informationsextraktion versuchen diese vorhandene Informationsquelle zur Erzeugung von strukturierten Datenbanken zu nutzen, die in weiterer Folge gezielt abgefragt werden können. Vor diesem Hintergrund beschäftigt sich diese Doktorarbeit mit zwei Fragen: (i) wie hoch ist die theoretisch zu erwartende Effizienz von automatischer Informationsgewinnung aus dem Web unter der Annahme einer Potenzgesetzverteilung von Informationen im Web; und (ii) wie können Informationsextraktionsansätze die im Web heute vorhandenen visuell präsentierten Meta Informationen bestmöglich verwenden, ohne auf ein zukünftig zu erwartendes Semantisches Web warten zu müssen.<br />Der erste Teil entwickelt das mathematische Formelwerk zur Beschreibung der theoretischen Effizienz von Informationsgewinnung aus vielen verteilten Datenquellen. Zu diesem Zweck wird eine intuitive Kennzahl genannt unique recall ("Einfache Abdeckung") als Funktion der Verteilung von Redundanzen oder Wiederholungshäufigkeiten individueller Informationen entwickelt. Nach einer Grenzwertbetrachtung werden komplette mathematische Beschreibungen und allgemeine Randbedingungen für dieses Maß hergeleitet. Die Formeln werden danach auf Beispielsverteilungen angewendet und Potenzgesetze besonders ausführlich behandelt.<br />Der zweite Teil untersucht wie sich gesamte Redundanzverteilungen während eines Zufallsauswahlverfahren entwickeln. Die daraus erhaltenen Gleichungen erlauben eine Abschätzung der Zuverlässigkeit von Informationsgewinnung. Ein besonderes Resultat ist die Beschreibung einer potenzgesetzähnlichen Familie von Verteilungen, die ihre Form während eines randomisierten Auswahlprozesses beibehält und daher unverändert während eines Informationsgewinnungsprozesses bleibt. Dieser Teil endet mit der noch zu verifizierenden Vermutung, dass diese gefundene Invarianz ein Grund für die Allgegenwärtigkeit von Potenzgesetzen in Informationssystemen ist und sie nicht nur durch multiplikative Wachstumsprozesse, sondern auch durch wiederholte Auswahlprozesse erklärt werden können.<br />Der dritte Teil beginnt mit der Feststellung, dass ein Großteil der Informationen im heutigen Web in einer visuellen statt einer semantischen oder semi-strukturierten Sprache kodiert ist. Um diese visuelle Sprache zu adressieren werden ein Model und eine Beschreibung von visueller Information im Web entwickelt. Methoden und Algorithmen werden erläutert, die dieses Modell verwenden, um Tabellen imWeb zu finden und zu extrahieren. Schließlich wird eine Methode skizziert, eine Ground Truth von beliebigen Webtabellen zu erstellen, und die Tabellenextraktionsmethode auf einem breiten Testset evaluiert.