Die vorliegende Erfindung betrifft das Gebiet der Informationenvisualisierung und insbesondere die Anzeige von Darstellungen von verknüpften Informationen auf Basis des Benutzer-Interesses.

Viele Anwendungen von Rechnern auf praktische Probleme sind mit der Anzeige von Darstellungen von verknüpften Informationen, wie beispielsweise hierarchischen Daten, verbunden. Verknüpfte Informationen beziehen sich auf Informationen, die irgendeine logische oder organisatorische Beziehung aufweisen. Beispiele dafür sind Organigramme, Computerprogramme, Websites, Ablagesysteme oder biologische Taxonomien. Diese Datenstrukturen sind oft viel größer als bequem auf den Bildschirm eines Computer-Anzeigemonitors passt, damit Informationen leicht abgerufen werden können. Jedoch einen Weg zu finden, diese Strukturen für Benutzer so darzustellen, dass sie (1) Elemente in der Struktur rasch finden können und (2) die Beziehung eines Elements zu dem umgebenden Kontext verstehen können, ist eine ausschlaggebende Funktion (enabler) für viele Einsatzmöglichkeiten solcher Daten.

Ein Beispiel ist im Bereich von verknüpften hierarchischen Daten zu finden. Verknüpfte hierarchische Daten werden oft in einer Baumstruktur angezeigt. Mehrere Verfahrenstypen sind verwendet worden, um solche Baumstrukturen anzuzeigen, einschließlich gleichmäßigem oder skaliertem Aufbau solcher Baumstrukturen, Baum-Abbildungen, Fischaugen-Darstellungen, Fokus-plus-Kontext-Darstellungen und hyperbolische Bäume.

Einige Beispiele von Anzeigeverfahren und -Techniken werden in "Improving the visualization of hierarchies with treemaps: design issues and experimentation", D. Turo und andere, (Proceeding Visualization 1992, S. 124–131, 19.–23. Okt. 1992, XP002228633) bereitgestellt. Insbesondere werden spezielle Algorithmen zur Partitionierung eines Anzeigeplatzes offenbart, die darauf beruhen, dass jeder Knoten eine vorgegebene "Gewichtung" aufweist, die gemäß den angezeigten Informationen ermittelt wird. Diese Technik leidet jedoch darunter, dass Knoten mit niedriger Gewichtung unlesbar werden, je mehr die Anzeige partitioniert wird.

"Graphical fisheye views of graphs", M. Sarkar und andere, CHI '92, 3.–7. Mai 1992, XP000426810) beschreibt eine verzerrende Fischaugen-Darstellungstechnik, die den "visuellen Wert" eines Knotens auf Basis seines geometrischen Abstands von einem ausgewählten Knoten in der normalen (unverzerrten) Darstellung ermittelt. Diese Näherungsweise ist nur effektiv, wenn der abstrakte Abstand zwischen Knoten ihrer Nähe in der Zeichnung entspricht. Wenn dies nicht der Fall ist, treten erhebliche Anomalien in der Fischaugen-Darstellung auf.

"Exploring large hyperdocuments: fisheye views of nested networks", E.G. Noik, (Proceeding cascon 1993, S. 661–676, Bad. 2, XP002228634) beschreibt eine Technik zum Generieren von Fischaugen-Darstellungen von verschachtelten Strukturen ohne Filterung oder Verzerrung. Die Größe jedes Knotens wird geändert, um seinen Interessegrad (DOI) wiederzugeben, bevor er positioniert wird. Da diese Technik eine bestehende Anordnung nicht verändert, werden in dem Dokument keine Probleme erörtert, die sich beim Einpassen der Visualisierung in den Anzeigebereich ergeben können.

Trotz solcher Verfahren und Techniken besteht weiterhin ein Bedarf, nützliche Informationen aus großen Hauptteilen von verknüpften Daten anzuzeigen und zu extrahieren.

Die vorliegende Erfindung dient Benutzern zum Durchsuchen von großen Sammlungen von verknüpften Informationen auf einer rechnerbasierten Anzeige. Eine Visualisierung wird erzeugt, die eine Darstellung der vollständigen Sammlung von Informationen auf der Anzeige bietet. Die Visualisierung passt vollständig in einen festen Bereich der rechnerbasierten Anzeige, wodurch die Notwendigkeit entfällt, Informationen in den Anzeigebereich hinein oder aus diesem heraus zu verschieben. Die Visualisierung basiert auf identifizierten Fokus-Knoten und erfolgt durch Berechnung eines Interessegrads (DOI) für jeden der Knoten in der Struktur. Anordnung und Darstellung der Visualisierungsstruktur basieren auf den DOI-Werten in Kombination mit Berücksichtigungen von verfügbarem Anzeigeplatz. Ein Benutzer kann Ansichten der Struktur dynamisch manipulieren, indem einer oder mehrere Fokus-Knoten ausgewählt werden, wodurch eine erneute Berechnung des Interessegrads veranlasst wird.

In Übereinstimmung mit der vorliegenden Erfindung wird ein Verfahren zum Anzeigen einer Darstellung einer gesamten Sammlung von verknüpften Informationen unter Verwendung einer Visualisierungstechnik in einem Anzeigebereich bereitgestellt, wobei jede der verknüpften Informationen eine Vielzahl von Knoten umfasst, die jeweils eine oder mehrere Verknüpfungen zu der Vielzahl von Knoten aufweisen, wobei das Verfahren die folgenden Schritte umfasst:

• a) identifizieren von einem oder mehreren Fokus-Knoten aus der Vielzahl von Knoten;
• b) Generieren eines Interessegrad-(DOI)Werts für jeden der Vielzahl von Knoten, wobei der Interessegrad-Wert auf wenigstens einem Abstand zwischen jedem Knoten und dem einen oder mehreren Fokus-Knoten basiert und einer Knoten-Anzeigegröße entspricht und die folgenden Schritte umfasst:
  
  b1) Zuordnen eines höchsten DOI-Werts zu dem einen oder mehreren Fokus-Knoten und ihrem bzw. ihren übergeordneten Knoten bis zu einem Hauptverzeichnis der verknüpften Informationen;
  
  b2) für jedes Geschwister der Fokus-Knoten Zuordnen eines DOI-Werts, der kleiner als der höchste DOI-Wert ist und auf einer Reihenfolge des Geschwister-Knotens basiert; und
  
  b3) für alle restlichen Knoten Zuordnen eines DOI-Werts, der kleiner als derjenige ihres übergeordneten Knotens ist;
• c) Anordnen der Vielzahl von Knoten, die auf verbundenen Verknüpfungen basierend in einer Baumstruktur positioniert und auf verbundenen Interessegrad-Werten basierend dimensioniert sind;
• d) Identifizieren und Durchführen irgendeiner Komprimierung der Knoten-Anzeigegrößen, die zum Anzeigen der verknüpften Informationen auf Basis der Anordnung der Vielzahl von Knoten notwendig sind, so dass die Darstellung vollständig in dem Anzeigebereich angezeigt wird; und
• e) Anzeigen der verknüpften Informationen auf Basis der Anordnung der Vielzahl von Knoten und der Knoten-Komprimierung in dem Anzeigebereich, und wobei das Generieren der DOI-Werte des Weiteren nach Schritt b2 und vor Schritt b3 das Identifizieren des bzw. der interessantesten abgeleiteten Knoten des Fokus-Knotens bis zu einer benutzerdefinierten Anzahl von Ebenen unter dem Fokus-Knoten und das Zuordnen von DOI-Werten, die niedriger als diejenigen der identifizierten Knoten sind und auf einer Reihenfolge des Geschwister-Knotens basieren, zu den Geschwistern der identifizierten Knoten umfasst.

Die Erfindung stellt des Weiteren ein System zum Durchsuchen einer Sammlung von verknüpften Datenelementen bereit, wobei das System umfasst:

eine Anzeigeeinrichtung, die einen Anzeigebereich zum Darstellen von Ansichten einer Visualisierung der Sammlung von verknüpften Datenelementen aufweist; und

eine Eingabevorrichtung zum Bereitstellen einer Eingabe zum Ändern der Ansicht der Visualisierung der Sammlung von verknüpften Datenelementen; gekennzeichnet durch

ein Visualisierungsverarbeitungselement, das mit der Anzeigeeinrichtung und der Eingabevorrichtung gekoppelt ist, wobei das Element so ausgelegt ist, dass es eine Visualisierung der Sammlung von verknüpften Datenelementen auf Basis eines Interessegrads und einer Größe des Anzeigebereichs in Übereinstimmung mit dem oben beschriebenen Verfahren erzeugt.

Die vorliegende Erfindung kann verwendet werden, um Informationen-Einheiten anzuzeigen, die aus Datenelementen bestehen, die statisch, dynamisch oder eine Kombination aus statisch und dynamisch sind. Ein Beispiel für Informationen-Einheiten, die statische Datenelemente aufweisen, wären die Knoten in einem Organigramm. Ein Beispiel für eine Informationen-Einheit, die dynamische Daten aufweist, wäre die Darstellung einer Website, in der eine Informationen-Einheit eine Web-Seite innerhalb der Site darstellt und ein dynamisches Datenelement enthält, welches die Anzahl von "Treffern" darstellt, auf welche die entsprechende Seite über einen bestimmten Zeitraum trifft.

Einige Beispiele für Verfahren und Systeme gemäß der vorliegenden Erfindung werden im Folgenden unter Bezugnahme auf die folgenden begleitenden Zeichnungen beschrieben:

1 ist ein Ablaufdiagramm der grundlegenden Schritte zum Erzeugen einer Visualisierung einer verknüpften Struktur;

2 ist eine Veranschaulichung eines DOI-Baums mit gleichmäßiger Struktur, die den Stammknoten als den Fokus-Knoten aufweist;

3 ist eine Veranschaulichung des DOI-Baums von 2, wobei sich der Fokus-Knoten zu einem Knoten zweiter Ebene verschoben hat;

4 ist eine Veranschaulichung des DOI-Baums von 2, wobei sich der Fokus zu einem Astknoten verschoben hat, so dass er der neue Fokus-Knoten wird;

5 ist eine Veranschaulichung eines DOI-Baums, der verschiedene Baum-Komprimierungstechniken zeigt;

6 ist eine Veranschaulichung von verschiedenen vorgegebenen Bereichen in einem Anzeigebereich, der zum Anzeigen eines DOI-Baums verwendet werden kann;

7 und 8 sind Veranschaulichungen des DOI-Baums von 2 mit und ohne Verwendung der Techniken zur Erweiterung auf Passform (Expand to Fit) der vorliegenden Erfindung;

9 ist eine Veranschaulichung eines großen Organigramms;

10 ist eine Veranschaulichung einer Darstellung einer großen Datenbank mit einem Astknoten, der als der Gegenstand einer Suche festgelegt ist und damit als ein Fokus-Knoten angezeigt wird;

11 ist eine Veranschaulichung eines Baums, der von einer Datenbank mit mehreren Verknüpfungen pro Knoten abgeleitet ist, wobei ein Knoten verwendet wird, um die Baumstruktur zu generieren, und andere Verknüpfungen nach einer Benutzer-Aktion sichtbar werden;

12 ist eine Veranschaulichung eines Biblioplex, der mehrere Generationen von Verknüpfungen aus einem Hauptdokument zeigt;

13 ist eine Veranschaulichung eines Bedienfelds zum Steuern der DOI-Baum-Visualisierung der gegenwärtig bevorzugten Ausführungsform der vorliegenden Erfindung;

14 ist ein Blockschaltplan, der die funktionalen, von der Software implementierten Komponenten und den Datenfluss veranschaulicht, der zum Implementieren der gegenwärtig bevorzugten Ausführungsform der vorliegenden Erfindung verwendet werden kann; und

15 ist ein Blockschaltbild eines rechnerbasierten Systems, das verwendet werden kann, um die gegenwärtig bevorzugte Ausführungsform der vorliegenden Erfindung zu implementieren.

Die vorliegende Erfindung stellt eine Informationen-Visualisierungstechnik bereit, die es einem Benutzer ermöglicht, große Sammlungen von verknüpften Daten effizient zu durchsuchen. Wenn ein Benutzer die vorliegende Erfindung einsetzt, ist er in der Lage, Ansichten von großen Mengen von angezeigten Daten so zu manipulieren, dass die dargestellten Informationen vom Betrachter effektiv wahrgenommen werden. Die vorliegende Erfindung kann verwendet werden, um Informationen-Einheiten anzuzeigen, die aus Datenelementen bestehen, die statisch, dynamisch oder eine Kombination aus statisch und dynamisch sind. Ein Beispiel für Informationen-Einheiten, die statische Datenelemente aufweisen, wären die Knoten in einem Organigramm. Ein Beispiel für eine Informationen-Einheit, die dynamische Daten aufweist, wäre die Darstellung einer Website, in der eine Informationen-Einheit eine Web-Seite innerhalb der Site darstellt und ein dynamisches Datenelement enthält, welches die Anzahl von "Treffern" darstellt, auf welche die entsprechende Seite über einen bestimmten Zeitraum trifft.

Die vorliegende Erfindung arbeitet an verknüpften Informationen, die oft als eine Knoten-Verknüpfungs-Struktur dargestellt werden können. in einer Knoten-Verknüpfungs-Darstellung stellt jeder Knoten eine Informationen-Einheit dar, und die Verknüpfung stellt eine Beziehung zwischen den verschiedenen Knoten dar. Die zu Grunde liegenden Daten können eine tatsächliche Verknüpfung aufweisen, z.B. Web-Seiten oder andere Dokumente, die Hypertext-Verknüpfungen enthalten), oder eine logische Verknüpfung, (z.B. die Knoten, aus denen ein Organigramm besteht).

Die vorliegende Erfindung wurde für den Betrieb auf rechnerbasierten Systemen, die eine grafische Benutzerschnittstelle aufweisen, implementiert, wie beispielsweise diejenigen, die das Windows^®-Betriebssystem von Microsoft, Inc. oder das MAC-OS-Betriebssystem von Apple Computer, Inc. einsetzen. Solche grafischen Benutzerschnittstellen weisen das Merkmal auf, dass ein Benutzer mit dem Rechnersystem unter Verwendung einer Cursor-Steuervorrichtung und/oder über eine Sensorbildschirm-Anzeige statt nur über eine Tastatur-Eingabevorrichtung interagieren kann. Solche Systeme weisen auch das Merkmal auf, dass sie mehrere "Fenster" aufweisen können, in denen diskrete Betriebsfunktionen oder Anwendungen vorkommen können. Eine umfassendere Beschreibung eines solchen rechnerbasierten Systems, auf dem die vorliegende Erfindung implementiert werden kann, wird im Folgenden bereitgestellt.

Die vorliegende Erfindung kombiniert (a) den Gedanken der Berechnung der Interessegrad-(DOI)Schätzwerte von Benutzer-Interesse mit (b) Fokus- + Kontext-Techniken zum dynamischen Ändern der Ansicht, wenn sich der DOI ändert, und (c) der Anpassung dessen, was angezeigt wird, auf der Basis der verfügbaren Anzeige-Ressource, (z.B. der sichtbare Bereich einer Computer-Anzeige oder die Größe eines "Fensters" auf der Anzeige).

Die vorliegende Erfindung kann man sich als modular vorstellen, so dass die Anzeige von Informationen für den Benutzer in zwei Teilen berechnet wird: (1) eine Schätzung des Interessegrads des Benutzers an jedem der Knoten und (2) eine Visualisierung der Daten auf Basis des berechneten Benutzer-Interesses und der Menge an verfügbarer Anzeige-Ressource. Eine Visualisierung unter Verwendung der vorliegenden Erfindung kann dazu verwendet werden, verschiedene Visualisierungen von verknüpften Informationen darzustellen, wie beispielsweise Baumstrukturen oder Sammlungen von hyperverknüpften Dokumenten. Die vorliegende Erfindung setzt des Weiteren Animation ein, um glatte visuelle Übergänge für die Angabe von DOI-Änderungen in der angezeigten Struktur zu ermöglichen.

Der Interessegrad (DOI) bezieht sich auf einen Wert, der einem speziellen Knoten in Bezug auf irgendeinen Fokus-Knoten beigeordnet wird. Der DOI-Wert bietet eine Möglichkeit, den Knoten einen quantitativen Wert beizumessen. Der DOI-Wert kann auf viele verschiedene Arten berechnet werden und steht oft in direktem Bezug zu der Art und Weise, wie die zu visualisierenden Daten erfasst werden. Zum Beispiel können Echtzeit-Nutzungsdaten zum Berechnen eines DOI verwendet werden, also könnte der DOI-Wert auf der Nutzung basieren.

Beim bisherigen Stand der Technik wird der DOI eines Knotens in einer Baumstruktur als die intrinsische Wichtigkeit (intrinsic Importance) plus dem Abstand von einem Fokus-Knoten geschätzt. Die intrinsische Wichtigkeit stellt die Relevanz oder Wichtigkeit eines Knotens in Bezug auf einen Stammknoten dar und wird als die Anzahl von Knoten ab dem Stammknoten bis zu dem betreffenden Knoten gemessen. Der Abstand eines Knotens von dem Fokus-Knoten ist die Anzahl der Knoten, die von folgenden über- und untergeordneten Verknüpfungen ab dem interessanten Knoten durchquert werden müssen, bis der betreffende Knoten erreicht ist.

In der vorliegenden Erfindung unterscheidet sich die Berechnung des Interessegrades für eine Baumstruktur von derjenigen, die im bisherigen Stand der Technik offenbart wurde. Im bisherigen Stand der Technik weisen alle Geschwister-Knoten, die den gleichen Abstand von dem Fokus-Knoten haben, den gleichen DOI-Wert auf. Die Berechnung der vorliegenden Erfindung behandelt die abgeleiteten Knoten eines übergeordneten Knotens als in Reihenfolge angeordnet (ordered) und weist den abgeleiteten Knoten auf Basis eines Reihenfolge-Abstands von dem Fokus-Knoten fraktionale DOI-Versätze zu. Je weiter der Geschwister-Knoten von dem Fokus-Knoten auf Basis der Reihenfolgen-Anordnung entfernt ist, desto höher ist die fraktionale Verringerung in seinem DOI, (doch ist die Verringerung immer kleiner als 1). Des Weiteren basiert der DOI der abgeleiteten Knoten von den Geschwister-Knoten auf dem Geschwister-DOI. Dies ermöglicht es dem Visualisierungselement zu entscheiden, welche Geschwister-Knoten komprimiert werden, und wie sie komprimiert werden.

Wie oben angemerkt, können verschiedene Visualisierungstechniken verwendet werden, wenn die vorliegende Erfindung implementiert wird. Zunächst entspricht jeder DOI-Wert einem Knotengrößen-Parameter. Typischerweise kann dieser Knotengrößen-Parameter einer größten Knotengröße für einen bestimmten Bereich von DOI-Werten entsprechen. Beim Generieren der Struktur in der Visualisierung werden die Knoten unter Verwendung des Knotengrößen-Parameters zusammen mit beliebigen strukturbasierten Anpassungen angeordnet. Diese strukturbasierten Anpassungen erleichtern die optimale Nutzung des Anzeigebereichs in Bezug auf die Darstellung der Informationen sowie die Bereitstellung eines glatteren visuellen Erscheinungsbilds der Struktur. Weitere Visualisierungskomprimierungen der Knoten in der Struktur können auf dem verfügbaren Anzeigebereich basieren. Zum Beispiel können Teile der Struktur, die in vorbestimmten Bereichen liegen, vereinigt werden, oder gewisse Teile der Struktur können als Ergebnis ihrer niedrigeren DOI-Werte kollektiv durch ein Symbol dargestellt werden, (wobei die Größe des Symbols für die Anzahl von Knoten stehen kann, die dargestellt werden). Alternativ kann die angezeigte Struktur eine Anzeige-Ressource nicht vollständig nutzen, in welchem Fall Visualisierungserweiterungen eintreten, um die verfügbare Anzeige-Ressource effizient zu nutzen.

Die gegenwärtig bevorzugte Ausführungsform der vorliegenden Erfindung wird implementiert, um hierarchisch verknüpfte Daten in einer Baumstruktur anzuzeigen. Dies wird im Folgenden als ein Interessegrad (DOI) bezeichnet. Der DOI-Baum kann zum Anzeigen verschiedener Typen von hierarchischen Informationen verwendet werden, wie beispielsweise Organigramme, Dateistrukturen oder Darstellungen von Web-Sites.

Die folgende Terminologie wird verwendet, um eine Baumstruktur zu beschreiben. Ein Stammknoten bezieht sich auf den obersten Knoten in der Struktur und denjenigen, von dem der Rest der Baumstruktur ausgeht. Eine Baumstruktur weist mehrere Ebenen auf, wobei jede Ebene einen horizontalen Teil der Struktur darstellt. Die Knoten in der Baumstruktur sind Ober Verknüpfungen verbunden. Die Knoten weisen Beziehungen zu anderen Knoten auf, die als übergeordneter Knoten, abgeleiteter Knoten oder Geschwister-Knoten bezeichnet werden. Ein Knoten ist ein zu einem anderen Knoten übergeordneter Knoten, wenn er direkt verknüpft ist und eine Ebene über dem anderen Knoten liegt. Desgleichen ist ein Knoten ein abgeleiteter Knoten, wenn er direkt verknüpft ist und eine Ebene unter dem anderen Knoten liegt. Geschwister-Knoten sind diejenigen, die auf der gleichen Ebene liegen und den gleichen übergeordneten Knoten aufweisen.

1 ist ein Ablaufdiagramm, welches das allgemeine Verfahren der vorliegenden Erfindung beschreibt. Zunächst werden Knoten-Informationen für Knoten in der Visualisierung generiert, Schritt 101. Diese Knoten-Informationen werden unter Verwendung von gespeicherten Daten für die Knoten generiert. Anschließend wird ein Fokus-Knoten bestimmt, Schritt 102. Nach dem ersten Anzeigen der Visualisierung kann der Fokus-Knoten der "Stamm"-Knoten sein oder darauf basieren, wie die Anzeige der Struktur angefordert wurde. Während des Durchsuchens der Struktur wird der Fokus-Knoten typischerweise durch die Benutzer-Auswahl eines bestimmten Knotens identifiziert. Dann wird der DOI für die Knoten generiert, Schritt 103. Wie oben beschrieben, wird der DOI nicht nur durch den Abstand von dem Fokus-Knoten bestimmt, sondern basiert auch auf seiner Reihenfolge (bzw. seines übergeordneten Knotens) in Bezug auf den Fokus-Knoten. Die Knoten werden dann dimensioniert und auf der Basis ihres DOI-Werts angeordnet, Schritt 104. Eine Art und Weise, in welcher Knoten dimensioniert werden, wird im Folgenden unter Bezugnahme auf den in Tabelle 1 bereitgestellten Pseudo-Code angegeben. Die Art und Weise der Anordnung der Knoten basiert auf der Visualisierungsstruktur (z.B. ein Baum oder irgendeine andere Struktur). Dann werden Visualisierungsanpassungen vorgenommen, um die Nutzung des Anzeigebereichs zu optimieren, Schritt 105. Wie oben angemerkt, können diese Visualisierungsanpassungen Visualisierungskomprimierungen oder Visualisierungserweiterungen sein. Die Visualisierungsstruktur wird angezeigt, Schritt 106. Wenn ein neuer Fokus-Knoten ausgewählt und erfasst wird, Schritt 107, werden die Schritte ab Schritt 103 wiederholt, wobei die neue Visualisierungsstruktur vorzugsweise unter Verwendung von Animations-Techniken angezeigt wird.

Tabelle 1 stellt Pseudo-Code bereit, der die Art und Weise der Verarbeitung von Knoten in der gegenwärtig bevorzugten Ausführungsform beschreibt.

Unter Bezugnahme auf Tabelle 1 werden die aufgelisteten Abläufe rekursiv für jeden Knoten wiederholt. Im Allgemeinen weisen die Fokus-Knoten die größtmögliche Größe auf, wobei kleinere Größen auf Basis des DOI-Werts zugewiesen werden. Die in Tabelle 1 angegebenen numerischen Werte dienen zur Veranschaulichung und sind eigentlich parametrische Schwellenwerte, die sich ändern könnten. Es ist anzumerken, dass die Knotengrößen auf Basis von DOI-Werten zugewiesen werden, die in einen bestimmten Bereich fallen. Die Verwendung von anderen Werten oder parametrischen Schwellenwerten würde keine Abweichung vom Gedanken und Umfang der vorliegenden Erfindung verursachen. Die Option des Ausblendwerts ist eine Technik, um kleine Unterscheidungen zwischen Knoten zu treffen, die andernfalls die gleiche Größe aufweisen würden. Der Ausblendwert ist ein fraktionaler Wert, der zum Verringern der Größe von Knoten verwendet wird, je weiter sie vom Fokus-Knoten entfernt sind. Zum Beispiel würde ein Ausblendwert von 0,10 für eine hierarchische Struktur die Größe der Reihe von Knoten über und unter der Fokus-Reihe um 10% verkleinern. Die nächste Reihe über und unter diesen Reihen wäre um 20% kleiner. Dies lässt mehr Platz für den Fokus-Knoten für große Bäume mit vielen Ebenen zu.

Anhand von Tabelle 1 sollte ebenfalls angemerkt werden, dass, wenn ein DOI-Wert unter einen bestimmten Schwellenwert fällt, hier <–4, dann wird der Knoten übergangen, (d.h. er wird nicht angezeigt).

Die grundlegende Berechnung des Interessegrades (DOI) für Knoten unter Verwendung der Standard-Anordnung folgt den nachstehenden Regeln:

• 1. Den Fokus-Knoten und übergeordneten Knoten bis zum Stammknoten wird ein DOI-Wert von 0 zugewiesen.
• 2. Ein DOI-Wert von –1 plus Versatz wird Geschwister-Knoten von Knoten mit einem DOI-Wert von 0 zugewiesen.
• 3. Für die restlichen Knoten wird ein DOI-Wert zugewiesen, der um eins geringer ist der ihrer übergeordneten Knoten.

Die Standard-Anordnung ist eine, in der ein einzelner Fokus-Knoten vorhanden ist. In einem alternativen Schema, in dem mehrere Fokus-Knoten vorhanden sein können, (z. B. Knoten, die als Ergebnis einer Suche gefunden werden), würden die Regeln zum Zuweisen des DOI wie folgt lauten:

• 1. Ein DOI-Wert von –1 wird allen ausgewählten Knoten zugewiesen.
• 2. Ein DOI-Wert von –1 wird übergeordneten Knoten von ausgewählten Knoten bis zum Stammknoten zugewiesen.
• 3. Für die restlichen Knoten wird ein DOI-Wert zugewiesen, der um eins geringer ist der ihrer übergeordneten Knoten.

In Bezug auf den oben beschriebenen Versatz behandelt die DOI-Berechnung der vorliegenden Erfindung die abgeleiteten Knoten eines übergeordneten Knotens als in Reihenfolge angeordnet und weist den abgeleiteten Knoten auf Basis eines Reihenfolge-Abstands von dem Fokus-Knoten fraktionale DOI-Versätze zu. Je weiter der Geschwister-Knoten von dem Fokus-Knoten auf Basis der Reihenfolgen-Anordnung entfernt ist, desto höher ist die fraktionale Verringerung in seinem DOI, (doch ist die Verringerung immer kleiner als 1).

Für die Visualisierung des DOI-Baums ist eine kleine Anzahl von möglichen Knotengrößen zum Darstellen der Informationen vorhanden, die mit dem Knoten verbunden sind. Für die meisten Baumstrukturen wurde bestimmt, dass drei eine sinnvolle Zahl von Knotengrößen ist, doch könnten genauso gut fünf oder irgendeine andere Zahl von Knotengrößen verwendet werden. Wie oben unter Bezugnahme auf allgemeine Konzepte beschrieben, hängt die spezielle verwendete Knotengröße vom DOI des Knotens ab. Während der Erstellung der Visualisierung kann für die Abbildung von DOI-Werten in Knotengrößen eine Tabelle verwendet werden. Die Tabelle kann tatsächliche Knotengrößen oder Dimensionierungsfaktoren für die Verwendung beim Zeichnen jedes der Knoten enthalten.

2 zeigt die Anzeige eines gleichmäßigen Baums von 4 Ebenen mit jeweils 4 Zweigen auf jeder Ebene und dem Fokus auf dem Stammknoten 201. Der Stammknoten 201 ist als Fokus-Knoten ausgewählt worden und weist automatisch eine größere Größe auf. Um ferner anzugeben, dass es sich um einen Fokus-Knoten handelt, kann er so angezeigt werden, dass er sich optisch mehr unterscheidet, z. B. in einer anderen Farbe als die anderen Knoten. Für Knoten mit einem niedrigeren DOI wurden automatisch kleinere Knotengrößen ausgewählt. Zum Beispiel werden Knoten auf Ebene 202, Ebene 203 und Ebene 204 als fortlaufend kleiner dargestellt. Es ist ebenfalls anzumerken, dass in 2 auf Grund der Anzeigeplatz-Einschränkungen die Sammlung von Knoten auf Ebene 205 (unter Ebene 204) insgesamt als ein Dreieck dargestellt wird. In der gegenwärtig bevorzugten Ausführungsform ist der höchste DOI 0, die niedrigeren DOIs sind negative Zahlen.

In 3 ist ein Knoten 301 des in 2 angezeigten Baums ausgewählt worden. Der Knoten 301 befindet sich auf der nächstniedrigeren Ebene, und die Auswahl verursacht die Änderung der DOI-Berechnung für die Knoten. Wenn der Knoten angezeigt wird, wird gemäß den berechneten DOIs für die Knoten eine Verkleinerung des Knotens 201 und eine Vergrößerung der abgeleiteten Knoten 302 unter dem neuen Fokus-Knoten 301 in dem Baum vorgenommen. Obwohl nicht dargestellt, erfolgt der Übergang von einem Zustand in den nächsten vorzugsweise über eine glatte Animation. Es wurde festgestellt, dass eine solche Animation wünschenswert ist, damit der Benutzer die Übersicht behält und keine Verwechslung in Bezug auf Übergang und Änderung in Fokus-Knoten entsteht.

Unter Bezugnahme auf 4 hat der Benutzer einen der niedrigsten Knoten 401 entweder durch direkte Auswahl oder durch Auswahl nahe gelegener Knoten ausgewählt, wodurch verursacht wird, dass der Fokus-Knoten größer und leichter auswahlbar wird. Es ist anzumerken, dass andere Knoten auf Basis ihres DOI-Werts neu dimensioniert worden sind. Zum Beispiel sind die Knoten 402 und 403 größer geworden, während die Knoten 301 und 201 kleiner geworden sind. Wiederum würde dies für den Benutzer durch einen animierten Übergang dargestellt werden.

Das Verfahren zum Anordnen der Knoten ist wie folgt. Für mehrere inkrementelle Knotengrößen gibt es eine feste Originalgröße. Der Baum wird mit diesen Größen so angeordnet, als ob unbegrenzter Platz vorhanden wäre. Wenn die Höhe des Baums größer als die Höhe des Fensters ist, wird ein Skalierungsfaktor berechnet, so dass er vertikal hinein passt. Das Verfahren bestimmt dann die tatsächliche Knotengrößen multipliziert mit dem Skalierungsfaktor und ordnet die Bildschirmpositionen auf Basis dieser Größen an. Wenn für die Knoten auf einer bestimmten Ebene horizontal nicht genügend Platz vorhanden ist, wird Platz für den Fokus-Knoten und für seine übergeordneten Knoten und anschließend für ihre Geschwister-Knoten in der Reihenfolge rechts und links vom Fokus-Knoten zugeteilt, bis ein gewisser Prozentsatz des horizontalen Raums übrig ist. Dann wird der horizontale Raum für den Rest der Knoten und die Zweige darunter gleichmäßig komprimiert. Das heißt, der Zweig unter jedem Geschwister-Knoten wird horizontal so komprimiert, dass er unter den Geschwister-Knoten passt.

Es wurde festgestellt, dass es wünschenswert ist, immer eine Darstellung des vollständigen Baums in dem verfügbaren Anzeigebereich anzuzeigen. Der Anzeigebereich für den Baum auf der Anzeigevorrichtung ist im Allgemeinen jedoch eine feste Ressource. Dementsprechend muss der Baum so eingeschränkt werden, dass er innerhalb der Ressource bleibt. Die grundlegende Anzeigetechnik auf DOI-Basis reduziert den Druck auf diese Ressource in hohem Maße. Selbst mit der bisher beschriebenen Technik ist es möglich, dass nicht alle Knoten effektiv auf dem Bildschirm dargestellt werden. Dabei sind zwei Fälle zu berücksichtigen, und zwar dass der Baum nicht in der horizontalen Richtung hineinpasst, und dass der Baum nicht in der vertikalen Richtung hineinpasst. Dass der Baum nicht in der horizontalen Richtung hineinpasst, kommt oft vor und ist entweder auf einen großen Verzweigungsfaktor unter einem Knoten oder, weil sich Bäume in der Breite exponentiell erweitern, auf eine Ansammlung von Breiten zurückzuführen.

Wenn die Anzahl von Knoten auf Grund der Ansammlung von mehreren Zweigen groß ist, werden diese speziell bearbeitet, weil die Knoten unter jeder Box in dem für jede Box verfügbaren horizontalen Platz angeordnet sind. Dieses Muster ist in dem Baum zu sehen, der in 5 dargestellt ist. Wenn der Verzweigungsfaktor groß ist, werden die Knoten gefaltet, wie bei den Knotengruppen 501 und 502, die in 5 dargestellt sind. Die Faltung bezieht sich auf eine Technik, in der eine Knotengruppe so organisiert ist, dass ein Teil von ihr vertikal unter einen anderen Teil verschoben wird. Wenn übergangene Knoten unter einem Schwellenwert-DOI-Wert vorhanden sind, wird ein Dreieckssymbol verwendet, das eine entsprechende Größe aufweist, um die Anzahl der Knoten zu protokollieren. Ein solches Symbol ist das Dreieck 503, das in 5 gezeigt ist.

Wenn die Anzahl von Knoten über die Anzeige auf jeder Ebene groß ist, wird die verfügbare Anzeige-Ressource, in welcher die Knoten angezeigt werden sollen, vertikal in drei Bereiche aufgeteilt, wie in 6 dargestellt. Unter Bezugnahme auf 6 wird eine reguläre freie Anordnungszone 601, eine Komprimierungszone 602 und eine Zusammenfassungszone 603 angezeigt. Typischerweise liegen 70% des Bildschirms in der freien Anordnungszone 601, 20% in den kombinierten Komprimierungszonen 602 und 10% in kombinierten Zusammenfassungszonen 603. Falls notwendig, kann die horizontale Anordnung für einige der Knoten komprimiert werden, indem sie zum Beispiel überlappt werden. Dies wird durch Ebene 504 von 5 veranschaulicht. Wenn in der gegenwärtig bevorzugten Ausführungsform eine Cursor-Steuervorrichtung über diese Knoten bewegt wird, werden sie in den Vordergrund versetzt, wobei sie ihre Nachbarn überlappen, wodurch es dem Benutzer gestattet wird, sie zu prüfen. Wenn die höchste Komprimierung erreicht ist, wird eine Zusammenfassungs-Darstellung für die restlichen Knoten vorgenommen, so dass durch eine Auswahl in diesem Bereich der diesem Bereich entsprechende Knoten ausgewählt wird. Wenn sich zum Beispiel 100 Knoten in dem Zusammenfassungsbereich befinden, würde durch Auswählen von 30% des Wegs zur Kante der Anzeige der 30. Knoten ab der Innenkante des Bereichs ausgewählt.

Tabelle 2 enthält Pseudo-Code, der die Anordnung einer Visualisierungsstruktur, in der Knoten komprimiert sind, ausführlicher beschreibt.

Die Knoten mit den höchsten DOIs auf einer Ebene weisen die größte Knotengröße auf, (siehe zum Beispiel Knoten 401 in 4). Diese Knotengröße bildet die vertikale Höhe eines Bereichs, in dem die unmittelbaren Abkömmlinge aller Knoten auf dieser Ebene angeordnet werden sollen. Wenn horizontal zu viele Abkömmlinge vorhanden sind, werden die Abkömmlinge in mehrere Reihen gefaltet. Eine solche Faltung in mehrere Reihen ist eine übliche Organigramm-Konvention, (wobei eine vertikale Linie die Reihen verbindet).

Der lokale DOI-Wert bezieht sich auf den Wert auf jeder Ebene des Baumes, der Prioritäten für horizontalen Raum nur auf dieser Ebene bestimmt. Dieser Wert könnte auch für geringfügige Variationen in der Größe von Geschwister-Knoten auf einer Ebene verwendet werden. Die Verwendung des DOI für eine selektive Knoten-Erweiterung (wie im Folgenden beschrieben) und die Verwendung von Faltungsreihen erhöhen die Größe eines Baums, der horizontal angeordnet werden kann, in hohem Maße. Des Weiteren gestattet die Verwendung von Komprimierungs- und Zusammenfassungszonen, dass alle Bäume in einen festen Anzeigebereich eingepasst werden können. Es kann auch vorkommen, dass ein Baum in vertikaler Richtung zu tief ist, um in den Platz zu passen. In diesem Fall werden die Knoten abhängig vom DOI entweder im unteren oder mittleren Bereich des Baums übergangen. Der Begriff übergehen bzw. übergangen soll angeben, dass die Knoten nicht angezeigt werden und nicht, dass der Knoten oder seine zu Grunde liegenden Daten gelöscht werden. Zunächst wird ein Schwellenwert-DOI so erstellt, dass, wenn die Knoten für einen Baum kleiner sind als der Schwellenwert-DOI, sie übergangen und durch eine Übergehungs-Grafik ersetzt werden. Da die Knoten in elliptischer Wichtigkeit mit dem Abstand vom Hauptverzeichnis und in Abstandswichtigkeit mit dem Abstand von dem bzw. den Fokus-Knoten abnehmen, würde ein sehr tiefer Baum dann dazu neigen, einige Knoten um das Hauptverzeichnis und einige Knoten um den Fokus-Knoten zu zeigen, wodurch typischerweise verursacht würde, dass einige der dazwischenliegenden Knoten übergangen würden. Die vorliegende bevorzugte Ausführungsform sorgt jedoch für die Erstellung einer Übergehungs-Grafik über einem Knoten in einem gewissen Abstand über dem Fokus-Knoten. Die Übergehungsgrafik würde übergangene Knoten, einschließlich des Stammknotens darstellen. Die Breite des Symbols ist proportional zu der Aufzeichnung der Anzahl von dargestellten Knoten. Die Anzahl der Ebenen über dem anzuzeigenden Fokus kann durch eine Variable gesteuert werden, die vom Benutzer spezifiziert wird.

Wenn der DOI für den unteren Teil des Baums niedriger ist, wie dies für Zweige der Fall ist, die in eine Knotenhöhe eingepasst werden oder die bis zum Boden des Anzeigebereichs reichen würden, wird der untere Teil des Baums durch eine entsprechend proportionierte Übergehungs-Grafik ersetzt, d.h. ein Dreieck, dessen Breite zu der Aufzeichnung der Baumbreite proportional ist und dessen Höhe zu der Baumtiefe proportional ist.

Es kann sein, dass wie in 2 der Einsatz der bisher beschriebenen Techniken nicht genutzten Platz in dem Anzeigebereich lässt. Daher sorgt die vorliegende Erfindung dafür, dass ein Benutzer einen Teil des Baums in diesen nicht genutzten Platz erweitern kann. Ungenutzter Platz ergibt sich normalerweise aus einer Obergrenze bezüglich der Knotengröße, wodurch der Baum veranlasst wird, weniger vertikalen Platz einzunehmen, als in einem typischen Fenster vorhanden ist. Es wurde festgestellt, dass eine Erweiterung zur vertikalen Einpassung verursachen würde, dass die Knoten ungewöhnlich groß und verzerrt erscheinen würden. Des Weiteren würde horizontaler Platz begrenzt, von dem sich herausgestellt hat, dass er noch beengter ist.

Eine Knoten-Erweiterung erfolgt, wenn auf der Anzeige noch vertikaler Platz verfügbar ist. Die Erweiterung tritt auf dem "interessantesten Knoten" auf. Die Anzahl von Ebenen unter dem Fokus-Knoten, der sich automatisch erweitern soll, kann durch den Benutzer gesteuert werden. Als praktische Grenze haben sich drei oder vier Ebenen erwiesen.

Die Grenze ist notwendig, um zu verhindern, dass ein sehr tiefer Baum skaliert wird, so dass alle Knoten zu klein werden. Eine Knoten-Erweiterung auf jeder Ebene tritt bei dem "interessantesten Knoten" ein.

Tabelle 3 stellt einen Pseudo-Code bereit, der eine solche Knoten-Erweiterung beschreibt:

Der Baum wird automatisch unter dem Fokus-Knoten erweitert, indem der Knoten in der Ebene darunter mit den meisten Abkömmlingen ausgewählt wird. Die nächste Ebene unter diesem Knoten wird auf die gleiche Weise erweitert, bis die gesamte Tiefe des Baums gezeigt wird oder die vom Benutzer spezifizierte Anzahl von Ebenen erreicht wird. Dies ist der Fall, sobald der Benutzer einen neuen Knoten, auf den er sich konzentriert, auswählt, der die Erweiterung des Zweigs des Baums mit dem aktuellen Knoten zeigt. Die auf jeder Ebene für die Erweiterung ausgewählten Knoten bilden ein "Rückgrat" von Knoten, die in der ungefähr doppelt so großen Größe wie ihre mittelgroß dimensionierten Geschwister-Knoten dargestellt werden. Dies sorgt für Raum für die Anzeige der Baumstruktur unter den Geschwister-Knoten unter Verwendung der Knoten mit der kleinsten Größe. Da die Größe der Knoten in dem Rückgrat dieser Erweiterung nahezu die gleiche ist, wird ein "Ausblend"-Wert verwendet, um alle Knoten auf jeder vom aktuellen Fokus-Knoten entfernten Ebene kleiner zu machen. Damit wird verhindert, dass die automatische Skalierung alle Knoten für sehr tiefe Bäume zu klein macht.

Die Knoten in der Nähe des Fokus-Knotens werden somit immer in einer relativ großen Größe angezeigt.

Es gibt mehrere Möglichkeiten zum Bestimmen oder anderweitigen Identifizieren des "interessantesten Knotens", der erweitert werden soll. Dies kann ein automatisierter Prozess sein oder einer, der auf einer Benutzer-Eingabe basiert. Einige Beispiele sind: (1) Dies könnte der Knoten mit dem höchsten DOI auf einer Ebene sein, oder (2) es könnte ein Knoten sein, der auf Basis von Suchbegriffen, die vom Benutzer vorgegeben werden, identifiziert wird.

7 und 6 stellen den Baum von 2 gemäß dem Zweig dar, der die meisten Knoten aufweist. Unter Bezugnahme auf 7 nimmt der Baum nicht den gesamten Anzeigebereich ein, wie durch den nicht genutzten Bereich 701 dargestellt wird. Unter Bezugnahme auf 8 umfassen der Knoten 801 und die Abkömmlinge den Zweig mit der höchsten Anzahl von untergeordneten Knoten. Auf der Ebene 802 sind der Knoten 801 und sein Zweig erweitert worden. Dies wird auf Ebene 804 so fortgeführt, der Knoten 803 und sein Zweig werden erweitert, und auf Ebene 806 werden der Knoten 805 und sein Zweig erweitert. Wie dargestellt, wird die Knoten-Erweiterung fortgesetzt, bis die untersten Knoten oder "Astknoten" des Baums erreicht sind.

Eine solche Knoten-Erweiterung hat sich insofern als sehr nützlich erwiesen, als sie oft Einsichten in Suchebenen über das normale bereitgestellte Maß hinaus gestattet, (bis zu 6 Ebenen). Dies könnte Suchzeiten für bestimmte Informationen drastisch reduzieren.

Jeder Knoten weist typischerweise eine Anzahl von Datenelementen auf, die angezeigt werden sollen. Zum Beispiel könnten für ein Organigramm die anzuzeigenden Datenelemente Felder umfassen wie beispielsweise Dienststelle, die Dienststelle, an die berichtet wird, Name, Titel, Büro-Durchwahl, E-Mail, Bilddatei-Verknüpfung, Homepage-Verknüpfung usw. Je größer die Anzahl von anzuzeigenden Datenelementen ist, um so größer ist der Anzeigenoberfläche-Bereich, der für einen Knoten benötigt wird. Für den Fokus-Knoten kann der größte Teil der Informationen angezeigt werden.

Wie oben erläutert, weisen die Knoten typischerweise verschiedene Größen auf. Wenn die Knoten kleiner werden, ist weniger Platz vorhanden, um diese Informationen anzuzeigen. Informationen, die auf den Knoten angezeigt werden, sind nach Prioritäten geordnet, und da die Knoten weniger Raum zur Verfügung haben, werden die Elemente mit der höheren Priorität angezeigt. Die vorliegende Erfindung stellt mehrere Techniken bereit, um zu gestatten, dass Informationen auf einen Knoten passen:

• 1. Datenlöschung. Kleinere Knoten zeigen nur einige der Datenelemente an.
• 2. Wortabkürzung. Wörter und Sätze werden abgekürzt, wenn auf der Zeile, auf der sie angezeigt werden, kein Platz ist. Es werden verschiedene Textabkürzungsregeln je nach Typ der Informationen (Namen, Telefonnummern, E-Mail-Adressen) angewendet. Aus einer Datei wird auch eine Substitutionstabelle ausgelesen, um im Bedarfsfall übliche Wörter durch Abkürzungen zu ersetzen. Zum Beispiel wird Vize-Präsident zu V.P.
• 3. Knoten-Rotation. Die normale Ansicht von Knoten zeigt sie als 3-D-Boxen (dargestellt in 10). Unter Verwendung eines Vorgangs, wie beispielsweise den Cursor auf einer Box nach links oder rechts zu ziehen, wird der Anschein erzeugt, als drehten sich die Boxen, so dass jetzt eine andere Seite der Boxen nach vorne zeigt. Dies ermöglicht die Darstellung weiterer Datenelemente. Softwarebasierte Programmiertechniken zum Durchführen einer solchen Knoten-Rotation zum Darstellen verschiedener Informationen sind im Fachgebiet bekannt.

Es sollte des Weiteren angemerkt werden, dass alle oder einige dieser Techniken verwendet werden könnten. Alternativ könnte ein anderes Fenster entlang der Struktur angezeigt werden, um alle Informationen anzuzeigen.

Die Benutzer-Ausrichtung im Baum wird beibehalten, indem die Ansichten des Baums in Animation ineinander übergehen (animate into each other). Die Animationszeit wird auf einen wünschenswerten Bereich eingestellt, für gewöhnlich im Bereich von (0,7–1,0 Sek.). Die durchschnittliche Zeichenzeit pro Rahmen für die letzten Rahmen wird verwendet, um die Anzahl von Animationsrahmen einzustellen, die dieses Mal gezeichnet werden können. Dies wird zum Berechnen der Zwischenpositionen der Boxen verwendet.

Ein Baum-Übergang wird basierend auf einem Anfangszustand und einem Endzustand des Baums berechnet. Das Generieren eines Endzustands wird zum Beispiel durch einen Benutzer initiiert, der einen neuen Fokus-Knoten auswählt.

Die vorliegende Erfindung ist zum Bereitstellen eines interaktiven Browsers für Knoten-Verknüpfungsstrukturen angewendet worden. Die Erfindung könnte auf eine Reihe von Kontexten angewendet werden, in denen Knoten-Verknüpfungs-Strukturen visualisiert werden. Insbesondere könnte die Erfindung beim Visualisieren von webbezogenen Strukturen angewendet werden, wie beispielsweise die Struktur, die durch eine cachegespeicherte Gruppe von Web-Seiten oder anderen Web-Objekten ausgebildet wird.

Allgemeiner ausgedrückt, die Erfindung könnte angewendet werden, um einen Browser für Organigramme, Dateisystem-Hierarchien, Hypertext-Hierarchien, WorldWideWeb-Konnektivitätsstrukturen, Stücklisten, SGML-Strukturen oder irgendwelche anderen großen Knoten-Verknüpfungs-Strukturen bereitzustellen. Der Browser könnte zum Bearbeiten von Strukturen oder ihren Inhalten verwendet werden.

Elemente in dem Baum können zu frei wählbaren Internetadressen- (Uniform Resource Locator – URL) Seiten oder zu Programmen verknüpft werden, wie beispielsweise einem E-Mail-Programm. Somit kann der Baum als ein Browser zum Initiieren der Anzeige von Web-Daten agieren. Der Baum als Browser arbeitet schneller als ein herkömmlicher Web-Browser, weil eine Gruppe der Seiten zusammen auf dem Bildschirm betrachtet werden kann und ihre Beziehung zu anderen Seiten gezeigt wird.

Im Folgenden werden mögliche Anwendungen beschrieben.

• (1) Organigramm. Eine Einsatzmöglichkeit besteht für Organigramme, in denen die Knoten als Verknüpfungen zu unterstützenden Daten dienen, wie in 9. Dieses Organigramm weist über 400 Knoten auf, ist über das Web zugänglich und kombiniert alle Informationen, die in 12 getrennten Organigrammen enthalten sind, (von denen jedes eine Seite füllt). Indem nach einem Namen gesucht oder das Diagramm durchsucht wird, werden die Details der einzelnen Organisationen aufgedeckt. Des Weiteren dient das Diagramm als Schnittstelle in die Organisations-Homepages der verschiedenen Organisationen, (auf die durch Anklicken der entsprechenden Verknüpfung in dem Knoten zugegriffen wird). Es kann ferner verwendet werden, um auf die E-Mail jeder Einzelperson zuzugreifen, deren E-Mail auf dem Diagramm angegeben ist, indem einfach auf die Verknüpfung geklickt wird.
• (2) Web-Sites. Eine weitere Verwendungsmöglichkeit ist die Ansicht von Web-Sites, die in Baum-Form gezwungen oder anderweitig dazu reduziert wurden. Miniaturisierte Bildvorschauen von Seiten können in den Knoten angezeigt werden. Ganzseiten-Anzeigen der Seiten können neben dem Baum unter Verwendung einer geeigneten Web-Browser-Anwendung angezeigt werden.
• (3) Web-Site-Statistiken. Der DOI von einzelnen Seiten in einer Web-Site kann auf eine Abhängigkeit von der Anzahl der Treffer eingestellt werden, welche die Seite in einem vorgegebenen Zeitraum erhalten hat, wie beispielsweise dem vergangenen Monat oder der letzten Woche oder Stunde oder einer anderen Zeitspanne. Oder es könnte eine Funktion, welche eine Art Gewichtungs-Zugangszeitraum darstellt, verwendet werden, (zum Beispiel die Gewichtung von Treffern als eine abnehmende Exponentialfunktion (declining exponential) von Tagen vor dem gegenwärtigen). Somit können Site-Sponsoren die Aktivität auf ihren Web-Sites überwachen. Der Gewichtungs-Zeitraum könnte sogar auf Minuten reduziert werden, so dass Sponsoren die unmittelbare Aktivität auf ihren Sites überwachen könnten.
• (4) Datenbanken. Datenbanken, die sich durch Bäume ausdrücken lassen, können angezeigt und durchsucht werden. Als Beispiel wird die 7000 Knoten umfassende Taxonomie-Datenbank, die von ACM/SIGCHI für Wettbewerbstests (competitive tests) verwendet wird, in 10 gezeigt. In diesem Wettbewerbstest stellen die Kandidaten Visualisierungen der Datenbank dar, die dann durchsucht werden, um bestimmte Datenelemente zu finden. Indem er den Gruppierungen höherer Ebenen gefolgt ist, hat der Benutzer den Knoten 1001 mit dem Titel "Ebola-Virus" gefunden. Ein Vorteil des Einsatzes des DOI-Baums zum Durchsuchen besteht darin, dass der gesamte Baum immer sichtbar ist, was dem Benutzer dabei hilft, den Kontext der einzelnen Knoten beizubehalten. Weiteren relevanten Knoten in der Standard-Anordnung wird immer mehr Platz eingeräumt, während der Benutzer den Baum durchsucht. Die automatische Erweiterung unter dem Fokus-Knoten kann dabei helfen, den Zweig des Baums zu verstehen, der den neuen Fokus enthält.
• (5) Mehrfach verknüpfte Datenbanken. Die Knoten können Elemente in einer Datenbank sein, wie in 11. Die Elemente in der Datenbank sind in eine Baum-Form gezwungen oder wurden anderweitig dazu umgewandelt. Die Elemente in der Datenbank weisen jedoch mehrfache Verknüpfungen zu anderen Elementen in der Datenbank auf. Eine Gruppe oder Klasse von Verknüpfungen wird zum Erstellen der Baumstruktur verwendet. Typischerweise ist diese Klasse von Verknüpfungen indikativ für eine Beziehung zwischen diesen Elementen. In dieser Anwendung können zusätzliche Verknüpfungen zu anderen Elementen angezeigt werden, wenn eine vorgegebene Benutzertätigkeit ausgeführt wird, z.B. der Benutzer einen Cursor über irgendein Element bewegt. Dies wird durch die Verknüpfungen 1101 auf Element 1101 dargestellt.
  
  In einer anderen Möglichkeit zum Darstellen eines allgemeinen Diagramms mit mehrfachen Verknüpfungen können mehrfache Instances eines Knotens in der Struktur dargestellt werden. Dies kann auf einer bestimmten Art und Weise der Erstellung der Struktur aus der Datenbank basieren. In diesem Fall können die angezeigten Verknüpfungen auf andere Instances des Knotens verweisen. Solche duplizierten Knoten können so angezeigt werden, dass sie sich optisch von anderen Knoten unterscheiden, (z. B. durch verschiedene Farbe, Form usw.).
  
  Unter Verwendung dieser Techniken werden komplexe Strukturen, die als verallgemeinerte Diagramme schwierig zu zeichnen wären, als Bäume gezeichnet, doch können die anderen Verknüpfungen immer noch untersucht werden. In diesem Fall, in dem einige der Knoten mit einem Dreieck unter einem Knoten zusammengefasst worden sind, wird eine Linie zu dem Dreieck gezeichnet.
• (6) Bibliografien. Ein Biblioplex ist eine Gruppe von Dokumenten, die generiert werden, indem nacheinander Generationen von Zitationen durchquert werden, wie in 12. Dies kann als ein DOI-Baum angezeigt werden. Der DOI für einzelne Knoten kann durch Verteilen der Aktivierung unter den Verknüpfungen oder durch Kozitations-Analyse berechnet werden.
• (7) E-Mail-Strom-Visualisierung. E-Mail-Ströme können als Bäume dargestellt werden. Der DOI für diese Ströme könnte auf Basis der Inhaltsähnlichkeit und Baum-Nähe generiert werden.

13 stellt ein Bedienfeld 1301 dar, das für einen Benutzer bereitgestellt wird und zur Bereitstellung von Visualisierungs-Präferenzen sowie zum Angeben eines Suchbegriffs (Feld 1302) verwendet werden kann. In der gegenwärtig bevorzugten Ausführungsform der vorliegenden Erfindung kann mehr als ein Fokus-Knoten vorhanden sein. Dieser Fall würde typischerweise eintreten, wenn irgendein Typ von Suche für die Daten in den Elementen der Visualisierungsstruktur durchgeführt wird.

Unter erneuter Bezugnahme auf 13 umfassen die verschiedenen anderen Steuervorrichtungen Felder und Kontrollkästchen zum Angeben von Parameter für die Visualisierung und Befehls-Schaltflächen, um zu veranlassen, dass spezifische Befehle ausgeführt werden. Das Feld 1303 dient zum Spezifizieren der Größe des Anzeigebereichs, das Feld 1304 dient zum Spezifizieren der Anzahl von abgeleiteten Knoten, die vor der Faltung angezeigt werden sollen, das Feld 1305 spezifiziert ein Bild, das für die "Box", die einen Knoten darstellt, verwendet werden soll, das Feld 1306 wird zum Spezifizieren der Farbe der Box verwendet, das Feld 1307 wird zum Spezifizieren einer Übergangszeit für Animationszwecke verwendet, das Feld 1308 dient zum Spezifizieren des "Ausblend"-Werts zum Bestimmen des endgültigen DOI-Werts, der bei der Wiedergabe eines Knotens verwendet wird, das Feld 1309 wird verwendet, um einen maximalen DOI-Wert vor der Übergehung zu spezifizieren, das Feld 1310 wird zum Spezifizieren eines Hintergrundbilds für die Visualisierung verwendet, das Feld 1311 wird verwendet, um die Farbe für Linien und Text zu spezifizieren, das Feld 1312 wird verwendet, um die Spezifikation eines neuen Stammknotens zu aktivieren, das Kontrollkästchen 1313 wird verwendet, um zu spezifizieren, dass die Knoten-Erweiterung erfolgen soll, das Kontrollkästchen 1314 wird verwendet, um zu spezifizieren, dass Fotos angezeigt werden können, das Kontrollkästchen 1316 wird verwendet, um zu spezifizieren, dass der DOI-Wert für die Knoten angezeigt werden soll, das Kontrollkästchen 1315 wird verwendet, um zu spezifizieren, dass ausgewählte Knoten unterdrückt werden sollen, Kontrollkästchen 1317 wird verwendet, um zu spezifizieren, dass nichtausgewählte Knoten unterdrückt werden sollen, das Kontrollkästchen 1318 wird verwendet, um eine Abfrage zuzulassen, das Kontrollkästchen 1319 wird verwendet, um die Unterdrückung von unteren mittleren (low medium) Knoten zu spezifizieren, das Kontrollkästchen 1320 wird verwendet, um Ton ein- oder auszuschalten, das Kontrollkästchen 1321 dient zum Aktivieren der Benutzer-Zuweisung von DOI-Werten.

Die Schaltfläche 1322 dient zum Durchqueren des Baums in Vorwärtsrichtung basierend auf vorherigen Befehlen, die Schaltfläche 1323 dient zum Durchqueren des Baums in Rückwärtsrichtung basierend auf vorherigen Befehlen, die Schaltfläche 1324 dient zum Anzeigen aller Knoten, die bisher ausgewählt worden sind, die Schaltfläche 1325 dient zum Löschen des Speichers für vorher ausgewählte Knoten, die Schaltfläche 1326 dient zum Veranlassen der Auswahl aller Knoten, die Schaltfläche 1327 dient zum Zurücksetzen jedes Speichers für bisher eingegebene Befehle, die Schaltfläche 1328 dient zum Veranlassen, dass der Baum erneut gezeichnet wird, die Schaltfläche 1329 dient zum Veranlassen, dass der Baum mit größeren Blöcken gezeichnet wird, die Schaltfläche 1330 dient zum Veranlassen, dass der Baum mit kleineren Blöcken gezeichnet wird, die Schaltfläche 1331 dient zum Veranlassen, dass der Baum mit breiteren Boxen gezeichnet wird, die Schaltfläche 1332 dient zum Veranlassen, dass der Baum mit schmaleren Boxen gezeichnet wird, die Schaltfläche 1333 dient zum Veranlassen, dass der Baum mit höheren Boxen gezeichnet wird, die Schaltfläche 1334 dient zum Veranlassen, dass der Baum mit kürzeren Boxen gezeichnet wird, die Schaltfläche dient zum Veranlassen, dass der gegenwärtige Fokus-Knoten der Stammknoten wird, die Schaltfläche 1336 dient zum Veranlassen einer Visualisierung eines Zweigs auf Basis des anzuzeigenden gegenwärtigen Fokus-Knoten, und die Schaltfläche 1337 dient zum Veranlassen, dass ausgewählte Knoten gelöscht werden.

Eine alternative Implementierung würde bestimmte, häufig verwendete Steuerfunktionen bereitstellen, die auf einer Symbolleiste angegeben werden, die in dem Fenster oder Anzeigebereich positioniert ist. Der Einsatz von Symbolleisten ist im Fachgebiet von Benutzerschnittstellen für rechnerbasierte Systeme bekannt.

14 ist ein Blockschaltbild, das die Funktionskomponenten und den Datenfluss der gegenwärtig bevorzugten Ausführungsform der vorliegenden Erfindung veranschaulicht. Unter Bezugnahme auf 14 ist das DOITreeApp 1405 das Hauptprogramm. Es kann entweder als ein Java-Programm implementiert werden oder kann ein Applet sein. Ein Applet ist ein Teil von Software-Code, der typischerweise für die Ausführung in einern Web-Browser vorgesehen ist. Wie oben erwähnt, wird die gegenwärtig bevorzugte Ausführungsform der vorliegenden Erfindung unter Verwendung der Java^®-Programmiersprache zum Betrieb auf einem Java^®-fähigen Web-Browser implementiert. Somit ist die gegenwärtig bevorzugte Ausführungsform als ein Applet implementiert. Die DOITreeApplet-Schnittstelle 1410 definiert eine Schnittstelle für weitere üblicherweise verwendete und öffentlich verfügbare Applet-Funktionen, die verwendet werden, um das DOITree-System zu implementieren, wie beispielsweise playAudioClip, showDocument, getImage usw.

DOITreeApp 1405 startet DOITree 1406 und stellt dafür ein DOITreeModel 1407 bereit. Das DOITree-Modell 1407 definiert die Daten, die zum Erstellen des Baums verwendet werden sollen. Das Modell enthält eine Gruppe von DOITreeNodes 1408 in einer hierarchischen Struktur. Die Daten für jeden Knoten werden aus einer Datendatei 1401 unter Verwendung eines Dienstprogramms, wie beispielsweise loadData 1404, ausgelesen, das abhängig vom Datenformat ReadSpreadsheet 1402, ReadDS 1403 oder andere Eingabe-Routinen verwendet. Die Art und Weise, in welcher die Datendatei 1401 erstellt wird, wird im Folgenden ausführlicher beschrieben. ReadSpreadsheet 1402 verwendet ein Eingabeformat, bei dem die Daten für jeden Knoten sich auf einer Zeile in einer Textdatei befinden und Datenfelder tabulatorbegrenzt sind. Dies ist ein Format, das von im Handel erhältlicher Tabellenkalkulations- oder Datenbank-Software erzeugt werden kann.

Sobald DOITree 1406 gestartet ist, empfängt es Eingaben vom Benutzer über Maus- oder Tastatur-Steuervorrichtungen. DOITree 1406 bestimmt die Anordnung, Größe und Position von Knoten in den Baum-Anzeigen. DOITree 1406 ruft DOITreeCellRenderer 1409 auf, um jeden Knoten auf der Anzeige 1411 zu zeichnen und auch Linien, Bilder und anderen Text oder Grafik auf der Anzeigevorrichtung 1411 zu verbinden.

In der gegenwärtig bevorzugten Ausführungsform ist die Software so organisiert, dass das hauptsächliche Anordnungsprogrammelement und die Bildaufbereitungsvorrichtung (DOITree 1406 und DOITreeCellRenderer 1409) in andere Software eingebettet und als Maschinencodeleser (viewer) für Baum-Daten behandelt werden können. Programmieren in der Java-Umgebung ist dem Fachmann bekannt, und daher wird eine weitere Erörterung oder Beschreibung der Programmiertechniken, die zum Implementieren der gegenwärtig bevorzugten Ausführungsform verwendet werden, nicht als notwendig erachtet.

Wie oben angemerkt, werden die zu Grunde liegenden Daten in der Datendatei 1401 gespeichert. In der gegenwärtig bevorzugten Ausführungsform stellen diese Daten die grundlegende Struktur dar, die zum Anzeigen der Visualisierung eingesetzt wird. Solche Daten können statisch sein oder ganz oder teilweise dynamisch generiert werden. Die Daten für DOI-Bäume können in einer Datenbank gespeichert oder daraus abgeleitet werden, oder sie können aus tabulatorbegrenzten Dateien ausgelesen werden. Benutzer können somit Bäume für die DOI-Baum-Anzeige unter Verwendung einer Tabellenkalkulations-Anwendung, wie beispielsweise Microsoft Excel^®, vorbereiten und bearbeiten und die eingegebenen Daten als eine tabulatorbegrenzte Datei speichern. In einer tabulatorbegrenzten Datei geben die Tabulatoren eine Trennung von Datenelementen und Knoten-Informationen an.

Es ist ebenfalls anzumerken, dass der Baum interaktiv aufgebaut werden kann, so dass Knoten dynamisch zu der Baumstruktur hinzugefügt oder daraus entfernt werden können. Des Weiteren kann eine solche Baumstruktur interaktiv aufgebaut werden, indem Informationen in Reaktion auf Benutzer-Anfragen aus einer Datenbank extrahiert werden.

Ein rechnerbasiertes System, auf dem die gegenwärtig bevorzugte Ausführungsform der vorliegenden Erfindung implementiert werden kann, wird unter Bezugnahme auf 15 beschrieben. Die gegenwärtige bevorzugte Ausführungsform der vorliegenden Erfindung wurde auf einem rechnerbasierten System unter Verwendung des Windows^®-Betriebssystems und der Internet Explorer^®-Browser-Anwendung implementiert, (die beide Warenzeichen der Microsoft Corporation in Redmond, Washington, sind). Wie oben angemerkt, wird die vorliegende Erfindung unter Verwendung von Software-Programmieranweisungen, die in der Java^®-Programmiersprache geschrieben sind, zur Ausführung auf einem rechnerbasierten System implementiert. Java ist ein Warenzeichen von Sun Microsystems in Mountain View, Kalifornien. Es wird somit erwartet, dass die gegenwärtig bevorzugte Ausführungsform der vorliegenden Erfindung auf jedem rechnerbasierten System betrieben werden kann, das eine grafische Benutzeroberfläche und die Java-Betriebsumgebung unterstützt. Unter Bezugnahme auf 15 besteht das rechnerbasierte System in jedem Fall aus einer Vielzahl von Komponenten, die über einen Bus 1501 gekoppelt sind. Der Bus 1501 kann aus einer Vielzahl von parallelen Bussen, (z. B. Adress-, Daten- und Status-Busse), sowie einer Hierarchie von Bussen bestehen, (z.B. einem Prozessor-Bus, einem lokalen Bus und einem I/O-Bus). In jedem Fall besteht das Rechnersystem des Weiteren aus einem Prozessor 1502 zum Ausführen von Anweisungen, die Ober den Bus 1501 vom inneren Speicher 1503 bereitgestellt werden, (es ist anzumerken, dass der interne Speicher 1503 typischerweise eine Kombination aus Direktzugriffs- und Festwertspeicher ist). Anweisungen zum Ausführen solcher Abläufe werden aus dem internen Speicher 1503 abgerufen. Solche Abläufe, die vom Prozessor 1502 durchgeführt würden, würden die Verarbeitungsschritte umfassen, die im Ablaufdiagramm von 1 und den begleitenden Ausführungen beschrieben worden sind. Die Abläufe würden typischerweise in der Form von codierten Anweisungen in einer geeigneten Programmiersprache unter Verwendung bekannter Programmiertechniken bereitgestellt werden. Der Prozessor 1502 und der interne Speicher 1503 können diskrete Komponenten oder eine einzelne integrierte Vorrichtung sein, wie beispielsweise ein anwendungsspezifischer integrierter Schaltungs-(Application Specification Integrated Circuit)(ASIC)Chip.

Des Weiteren sind mit dem Bus 1501 eine Tastatur 1403 für alphanumerische Eingaben, ein externer Speicher 1505 zum Speichern von Daten, eine Cursor-Steuervorrichtung 1507 zum Anzeigen visueller Ausgaben und eine Netzwerkverbindung 1508 gekoppelt. Die Tastatur 1504 wäre typischerweise eine Standard-QWERTY-Tastatur, kann aber auch ein Tastenblock ähnlich wie beim Telefon sein. Der externe Speicher 1505 kann ein festes oder entfernbares Magnet- oder Bildplattenlaufwerk sein. Die Cursor-Steuervorrichtung 1506, z.B. eine Maus oder Rollkugel, weist typischerweise eine damit verbundene Taste bzw. einen Schalter auf, auf welche die Durchführung bestimmter Funktionen programmiert werden kann. Die Anzeigevorrichtung 1507 kann einen oder mehrere physikalische Anzeigemonitore umfassen. Die Netzwerkverbindung 1508 stellt Mittel zum Verbinden mit einem Netzwerk bereit, z.B. eine Lokalnetz-(Local Area Network – LAN)Karte oder Modemkarte mit entsprechender Software. Abgesehen vom Kommunikationszugriff kann die Netzwerkverbindung 1508 für den Zugriff auf verschiedene Ressourcen, (d.h. Server) verwendet werden, wie beispielsweise gemeinsam genutzte Rechen-, Speicher- oder Druck-Ressourcen.

Die Erfindung wurde in Bezug auf Software-Implementierungen beschrieben, doch könnte die Erfindung mit spezieller Hardware implementiert werden, die für den Betrieb in einer Systemarchitektur, wie oben beschrieben, ausgelegt ist.