Gebiet der Erfindung

Die Erfindung betrifft ein Verfahren und ein System zum Bestimmen einer Ähnlichkeit von zumindest zwei Objekten, welche von zumindest einer Baumdatenstruktur referenziert werden.

Stand der Technik

Es sind Verfahren bekannt, um die Ähnlichkeit von beispielsweise Dokumenten zu ermitteln. Ein aus dem Stand der Technik bekanntes Verfahren ist die so genannte Inhaltsanalyse. Bei der Inhaltsanalyse wird geprüft, ob zwei Dokumente die gleichen Wörter enthalten. Je mehr gleiche Wörter sie enthalten, desto ähnlicher sind sie sich. Nachteilig hierbei ist, dass Dokumente inhaltlich sehr ähnlich sein können, die Autoren aber das Thema mit verschiedenen Wörtern beschreiben - sei es, dass die jeweiligen Autoren unterschiedliche Sprachen nutzen oder unterschiedliche Terminologien. Ähnliche Dokumente können so fälschlicherweise als nicht ähnlich eingestuft werden. Ein weiterer erheblicher Nachteil besteht darin, dass für eine effiziente Ähnlichkeitssuche von Dokumenten sog. Volltextindizes erzeugt werden müssen, welche einen erheblichen Speicherplatz benötigen. Bei der Inhaltsanalyse von anderen Objekten, wie etwa Musik oder Filmen, gibt es zwar auch Verfahren, um die Ähnlichkeit zu bestimmen, diese Verfahren sind aber sehr ungenau, da es sehr schwer ist Musik oder sogar bewegende Bilder gut auf Ähnlichkeiten zu analysieren. So werden Musikstücke häufig manuell klassifiziert, da eine automatische Klassifizierung nahezu unmöglich ist. Ein weiteres aus dem Stand der Technik bekanntes Verfahren ist das so genannte "Collaborative Filtering". Hier bewerten Anwender Objekte z.B. auf einer Skala von 1 bis 5. Dann werden die Anwender entsprechend ihrer abgegebenen Bewertungen geclustert. Haben nun zwei Anwender A und B die gleichen Objekte gleich (bzw. ähnlich) bewertet, werden z.B. dem Anwender A jene Objekte empfohlen, die B positiv bewertet hat und A noch nicht kennt. Problem hierbei ist, dass die kritische Masse oft nicht erreicht wird. Viele Leute wollen keine Objekte bewerten und dann diese Daten auch noch mit Dritten teilen. Des Weiteren ist bekannt, Objekte als ähnlich einzustufen, wenn sie z.B. oft gemeinsam genutzt oder zusammen gekauft werden. Kaufen beispielsweise viele Personen in einem Internet-Shop eine Kamera und kaufen diese Personen dort auch eine Kameratasche, so werden die Kamera und die Kameratasche als ähnlich eingestuft. Zukünftig kann dann einer Person, die eine Kamera kauft empfohlen werden, auch noch eine Kameratasche zu kaufen. Nachteilig hierbei ist, dass grundsätzlich verschiedene Objekte als ähnlich eingestuft werden könnten.

Aufgabe der Erfindung

Aufgabe der vorliegenden Erfindung ist es, ein Verfahren und ein System bereitzustellen, mit welchen die Ähnlichkeit von Objekten besonders zuverlässig und mit hoher Qualität bestimmt werden kann, ohne die aus dem Stand der Technik bekannten Nachteile aufzuweisen.

Erfindungsgemäße Lösung

Diese Aufgabe wird durch ein Verfahren mit den Merkmalen des Anspruches 1 und ein System mit den Merkmalen des Anspruches 14 gelöst. Vorteilhafte Ausgestaltungen der Erfindung sind in der nachfolgenden Beschreibung sowie den weiteren Ansprüchen angegeben. Demnach wird Verfahren zum Bestimmen einer Ähnlichkeit von zumindest zwei Objekten bereitgestellt, wobei die zumindest zwei Objekte von mindestens einer Baumdatenstruktur referenziert werden, welche eine Anzahl von Knoten aufweist, die durch Kanten verbunden sind, wobei zumindest zwei Knoten jeweils eine Referenz auf jeweils eines der zumindest zwei Objekte repräsentieren, wobei die Baumdatenstrulctur in einer Speichereinrichtung speicherbar ist und wobei das Verfahren zumindest folgende Schritte umfasst:

- Ermitteln der Knoten der mindestens einen Baumdatenstruktur, welche die zumindest zwei Objekte referenzieren;

- Bestimmen der Distanz zwischen jeweils zwei Objekten, welche von den ermittelten Knoten jeweils einer Baumdatenstruktur referenziert werden, wobei für jeweils zwei Objekte mehrere Distanzen bestimmt werden, wenn zumindest eines der beiden Objekte von mehreren Knoten einer Baumdatenstruktur referenziert wird und/oder wenn die beiden Objekte jeweils von Knoten zumindest zweier verschiedener Baumdatenstrukturen referenziert werden; und

- Bestimmen eines Ähnlichkeitswertes für jedes Paar von Objekten unter Verwendung der für die Objekte eines Paares bestimmten Distanzen.

Als Datenquelle für das Bestimmen der Ähnlichkeit von Objekten wird eine Baumdatenstruktur verwendet, in welcher die Objekte referenziert werden. Im Folgenden wird der Begriff Baumdatenstruktur bzw. Baumdatenstrukturen verkürzt mit BDS bezeichnet.

Gemäß der Erfindung können Baumdatenstrukturen sein: Verzeichnisstrukturen (z.B. Dateisysteme), Mind Maps oder sonstige hierarchische Strukturen, welche geeignet sind Referenzen zu Objekten zu speichern. Eine Baumdatenstruktur kann auch ein Computernetzwerk sein, wobei die Objekte auf unterschiedlichen Computern gespeichert sind und wobei die Objekte in einer hierarchischen Beziehung zueinander stehen. Als Objekt wir beispielsweise eine elektronische Datei in einem Verzeichnis einer Verzeichnisstruktur bezeichnet oder ein Dokument welches aus einer Mind Map heraus referenziert oder verlinkt wird.

Ähnlichkeit zwischen zwei Objekten kann auch bedeuten: Beziehung zwischen zwei Objekten oder Verwandtschaft zwischen zwei Objekten. Die Ähnlichkeit von zwei Objekten wird durch den so genannten "Tree Proximity Index TPI" ausgedrückt, der einen Wert zwischen 0 und 1 annehmen kann (0=keine Ähnlichkeit, l=hohe Ähnlichkeit). Selbstverständlich können auch andere Wertebereich für den TPI vorgesehen werden, z.B. 0% bis 100%. Der Begriff "Ähnlichkeitswert" wird nachfolgend verkürzt auch als "TPI" bezeichnet. Die Begriffe "Referenzieren" und "Verlinken" bzw. die Begriffe "Referenz" und "Link" werden nachfolgend jeweils synonym verwendet.

Ein Wesentlicher Vorteil von BDS ist, dass sie direkt und schnell analysiert werden können. Es müssen z.B. nicht erst hunderte Produkte verkauft werden, um die notwendige kritische Masse für eine Ähnlichkeitsbestimmung zu erreichen. In dem Moment, wo eine BDS bei einem Anwender erstellt wird, kann sie sofort analysiert werden. Außerdem werden BDS normalerweise nicht veröffentlicht. Das heißt, man kann davon ausgehen, dass die Autoren der BDS im Regelfall sehr ehrlich sind, da sie die BDS so erstellen, wie es für ihren Anwendungszweck am besten geeignet ist. Ein weitere Vorteil ist, dass die Ähnlichkeit zwischen zwei Objekten nahezu in Echtzeit ermittelt werden kann, was besonders dann vorteilhaft ist, wenn ein Benutzer beispielsweise eine Dokument aus einem Verzeichnis in ein anderes Verzeichnis verschiebt, was eine Änderung der Ähnlichkeit zwischen dem verschobenen Objekt und weiteren Objekten zur Folge haben kann. Ein weiterer Vorteil besteht darin, dass der Speicherplatzbedarf, um eine effiziente Recherche nach ähnlichen Dokumenten durchzuführen, erheblich reduziert werden kann, im Vergleich zu den aus dem Stand der Technik bekannten Volltextindizes, da lediglich ein einziger Ähnlichkeitswert für zwei Dokumente abgespeichert werden muss.

Das Bestimmen des Ähnlichkeitswertes kann einen Schritt zum Ermitteln eines Gewichtungsfaktors umfassen, mit dem der bestimmte Ähnlichkeitswert angepasst wird. Damit kann in vorteilhafter Weise ein berechneter Ähnlichkeitswert von zwei Objekten angepasst werden, wenn zusätzlich Voraussetzungen für einen höheren bzw. geringeren Ähnlichkeitswert sprechen.

Die Ähnlichkeits werte könne für jedes Paar von Objekten in einer Speichereinrichtung gespeichert werden.

Vor dem Ermitteln der Knoten der mindestens einen Baumdatenstruktur kann ein Schritt zum Reduzieren der Baumdatenstruktur ausgeführt wird. Dadurch kann das Ermitteln bzw. Bestimmen von Ahnlichkeitswerten zwischen Objekten beschleunigt werden, was insbesondere dann vorteilhaft ist, wenn eine sehr große Anzahl von BDS analysiert werden muss. Zudem kann durch das Reduzieren die Qualität der Ähnlichkeitsberechnung erhöht werden, da durch das Reduzieren Knoten entfernt werden, die irrelevant für die Ähnlichkeitsberechnung sind.

Die Baumdatenstruktur kann über ein Kommunikationsnetzwerk von einer Clienteinrichtung an eine Servereinrichtung übertragen wird, wobei das Übertragen vor dem Ermitteln der Knoten der Baumdatenstruktur ausgeführt werden kann.

Vor dem Übertragen oder nach dem Übertragen kann die Baumdatenstruktur in ein normiertes Baumdatenstruktur-Format konvertiert werden. Damit kann auf sämtliche BDS auf die gleiche Weise zugegriffen werden. Das normierte Baumdatenstruktur- Format kann dabei eine Baumdatenstruktur im XML-Format sein.

Ein Objekt kann zumindest eines aus Dokument, Bild, Musik, Film, Internetseite und elektronisch speicherbare Datei sein. Ein Objekt kann aber auch ein physisches Objekt, z.B. ein Buch sein, welches von einer BDS anhand z.B. des Titels referenziert wird. Bereitgestellt durch die Erfindung und zur Lösung der technischen Aufgabe wird auch ein System zum Bestimmen einer Ähnlichkeit von zumindest zwei Objekten, wobei das System ausgestaltet ist, das erfindungsgemäße Verfahren auszuführen.

Kurzbeschreibung der Figuren

Die weitere Erläuterung der Erfindung erfolgt anhand der Zeichnung. In der Zeichnung zeigt:

Fig. 1 bis 3 Beispiele von Baumdatenstrukturen in Nicht-reduzierter Form und reduzierter Form;

Fig. 4 ein Beispiel einer Baumdatenstruktur zur Erläuterung der

Distanzberechnung; und

Fig. 5 bis 8 Beispiele von Baumdatenstrukturen zur Erläuterung der Anpassung der

Ähnlichkeitswerte anhand von Gewichtungsfaktoren.

Beschreibung bevorzugter Ausführungsformen

Das Verfahren zur Berechnung des Ähnlichkeitswertes bzw. TPI zwischen zwei Objekten kann durch eine Software implementiert werden, welche z.B. eine Client-Software und eine Server-Software umfassen kann.

1. Softwareinstallation und Datenübertragung an Server

Ein Benutzer kann eine Client-Software installieren, um das erfindungsgemäße Verfahren auszuführen. Die Software identifiziert alle relevanten BDS auf dem Computer des Anwenders. Eine BDS wird z.B. über die Dateiendung identifiziert oder über den Header von Dateien oder indem sie explizit durch den Anwender ausgewählt wird. Die Software startet entweder automatisch im Hintergrund beim Hochfahren des Computers, durch explizites Starten durch den Anwender oder durch den Aufruf einer dritten Applikation. Die Software kann alle Speichermedien (Festplatte, DVDs, Netzwerk, etc.) durchsuchen oder nur den Arbeitsspeicher beachten, d.h. nur die BDS analysieren die gerade geöffnet sind oder anderweitig verarbeitet werden.

Die BDS werden bei Bedarf gefiltert nach Faktoren, z.B.

Größe (Dateigröße, oder Anzahl der Knoten bzw. referenzierten Objekte in der BDS)

- Letztes Änderungsdatum oder Erstelldatum

- Änderungsfrequenz (Anzahl Änderungen geteilt durch einen Zeitraum)

- Anzahl der Links auf Objekte in einer BDS (z.B. dass eine Mind Map mindestens 20 Links zu Webseiten beinhalten muss, bevor sie berücksichtigt wird)

Speicherort (nur die BDS aus bestimmten Verzeichnissen)

- BDS-Typ (nur Mind Maps einer bestimmten Software, oder nur das Dateisystem, etc) Autor (nur die BDS des Anwenders werden berücksichtigt).

Die Faktoren können beliebig eingestellt oder miteinander kombiniert werden. So könnten beispielsweise nur BDS berücksichtigt werden die in den letzten 2 Monaten erstellt wurden, mindestens 10 Links zu Objekten enthalten aber in den letzten 3 Tagen nicht mehr geändert wurden und vom Benutzer explizit dafür gekennzeichnet wurden, an den Server übertragen zu werden. Bei Bedarf werden die BDS in ein anderes Format konvertiert. Zum Beispiel könnten proprietäre Mind Map Dateien in XML konvertiert werden. Die BDS werden dann an einen Server übermittelt, wobei die Server-Software ggf. auf dem Computer des Anwenders laufen kann auf dem sich auch die BDS befinden.

2. Speichern der Daten auf Server

Bei Bedarf werden die BDS in ein anderes Format konvertiert (zum Beispiel von einem proprietären Format in XML). Der Server speichert die Daten auf der Festplatte, im Arbeitsspeicher, in einer Datenbank oder einem anderen geeigneten Medium. Ggf. werden die BDS wieder gefiltert nach bereits genannten Faktoren.

3. Reduzieren der Baumdatenstruktur In manchen Fällen ist es vorteilhaft, die BDS zu vereinfachen, bevor Ahnliclikeitswerte zu den Objekten ermittelt werden, welche in der BDS referenziert werden. Das Reduzieren der BDS kann wie folgt erfolgen:

- Löschen aller Endknoten die keine Links auf Objekte haben. Fig. 1 zeigt links eine BDS in Nicht-reduzierter Form und rechts eine BDS in reduzierter Form, bei der alle Endknoten, die keine Links auf Objekte enthalten, gelöscht worden sind.

- Reduzieren der Linkknoten, die keine Geschwisterknoten haben auf die nächstmögliche Ebene, sodass Geschwister entstehen. Ein Beispiel hierfür ist in Fig. 2 angegeben.

- Zusammenfassen von Knoten, die ein Objekt verlinken ohne aussagekräftige Beschreibung. In diesem Fall wird der Linkknoten mit dem Elternknoten zusammengefasst. Eine nicht aussagekräftige Beschreibung ist beispielsweise wenn der Knotenname gleich dem Dateinamen des verlinkten Objektes oder eine Zahl ist. Ein Beispiel hierfür ist in Fig. 3 angegeben.

- Filtern nach Benutzerangaben oder bestimmten Texten, etwa Links die in der BDS als „privat" oder ähnlichem gekennzeichnet sind, werden ignoriert und/oder Knoten deren Elternknoten„temp",„todo",„noch einsortieren",„xxx" etc. heißen werden ignoriert bzw. gelöscht. Die Wörter können vom Nutzer oder dem Programmierer vorgegeben werden.

- Kombination der vorstehenden Verfahren zum Reduzieren von BDS. 4. Analysieren der Baumdatenstruktur

In der BDS werden jene Knoten gesucht, die auf ein Objekt verlinken bzw. die ein Objekt referenzieren. Zum Beispiel wird nach Hyperlinks, Dateinamen und/oder Pfade, Verknüpfungen und/oder nach indirekten Verweisen auf Objekte, wie etwa BibTeX Keys, Aktenzeichen, und ähnliche eindeutige Schlüssel oder Dokumentennamen (oder Titel) gesucht. Nachdem alle Knoten gefunden wurden, die auf Objekte verlinken bzw. referenzieren, müssen diese Objekte identifiziert werden, damit klar ist, worum es sich handelt. Dies kann in einer Ausführungsform wie folgt erfolgen: a. Wurde ein Hyperlink gefunden kann

i. der Hyperlink selbst als Identifikator dienen

ii. im Falle einer Webseite (z.B. im HTML bzw. xHTML Format) der Titel aus der verlinkten Webseite ausgelesen werden (im Fall von HTML den Text zwischen den Tags <title> und </title> )

iii. im Falle, dass eine Datei verlinkt wurde (PDF, Movie, ...) wie im nächsten Schritt verfahren werden

b. Wurde eine Datei verlinkt wird der Objekttyp über die Dateiendung oder den Header der Datei identifiziert. Je nach Dateityp können dann weitere Verfahren angewandt werden. Zum Beispiel

i. Auslesen der Dateimetadaten (Titel oder Autor, sofern vorhanden), abhängig vom Betriebssystem und Dateityp.

ii. im Falle eines formatierten Textdokumentes (z.B. Word Dokument oder PDF):

Auslesen des Titels indem der Text mit der größten Schrift auf der ersten Seite im oberen Drittel bestimmt wird und der über weniger als vier Zeilen geht und ggf. zentriert ist. Dieser Text wird dann als Titel angenommen (die Zahlenwerte hier können natürlich beliebig ausgetauscht werden, sodass z.B. nicht im oberen Drittel sondern im oberen Viertel gesucht wird).

iii. im Falle eines JPEG: Auslesen der EXIF oder IPTC Metadaten.

iv. sonst: Hashwert erzeugen (z.B. MD5) oder Dateiname und Pfad der Datei.

c. Wurde ein indirekter Verweis auf ein Objekt gefunden, zum Beispiel ein BibTeX key, wird auf allen zugänglichen Speichermedien nach der entsprechenden BibTeX Datei gesucht und dort die Metadaten des Objektes ausgelesen.

d. Die Daten (z.B. Titel, Hashwert,...) die bestimmt wurden, können mit vorhandenen Daten in einer Datenbank (Wissensbasis) abgeglichen werden. Wurde Beispielsweise aus einem Objekt als Dokumententitel„Der Tree Proximity Index - wofür ist er gut?" extrahiert und in der Datenbank ist bereits ein Objekt mit dem Titel„Der Tree Proximity Index: wofür ist er gut?" vorhanden, ist es vermutlich das gleiche Objekt trotz des kleinen Unterschiedes.

Nachdem ein Objekt identifiziert wurde, werden seine Metadaten (Titel, Autor, URL, Hash...) zusammen mit einer eindeutigen ID in einer Datenbank gespeichert, damit später die Distanzwerte von diesem Objekt zu anderen Objekten berechnet werden können und auch die zukünftige Identifizierung des gleichen Objektes, welches in anderen BDS verlinkt wird, erleichtert wird.

5. Distanzberechnung

Nachdem alle Knoten mit Links identifiziert wurden, wird die Distanz zwischen diesen Knoten berechnet. Das heißt, es wird eine Matrix gebildet in der die Distanz von jedem Objekt zu jedem anderen Objekt eingetragen wird. Das Bestimmen der Distanz kann auf unterschiedliche Weise erfolgen, z.B. (aber nicht abschließend):

a. mit allen gängigen Verfahren der Graphen, Baum bzw. Netzwerktheorie;

b. oder über eine visuelle Auswertung, indem z.B. gemessen wird, wie viele cm, mm etc. Distanz zwischen den verlinkenden Knoten ist;

c. durch zählen der Kanten zwischen zwei Linkknoten.

Anhand der Fig. 4 wird die Variante, bei welcher die Distanz anhand der Knoten bestimmt wird erläutert. In Fig. 4 sind die Distanzen wie folgt:

Distanz (Linkl |Link2)-2

Distanz (Linkl |Link3)=2

Distanz (Linkl |Link4)=4

Distanz (Linkl |Link6)=5

Die Distanzwerte können gespeichert werden oder es wird gleich mit dem nächsten Schritt fortgefahren, in welchem die Ähnlichkeitswerte ermittelt bzw. berechnet werden.

6. Berechnen des Ähnlichkeitswertes (TPI) Der TPI von zwei Objekten berechnet sich anhand der Distanz der Objekte zueinander und wird durch gewisse Faktoren geschwächt. Der grundsätzliche Ablauf ist wie folgt:

51 Für jede vorhandene BDS werden die TPIs aller möglichen Objekte berechnet.

52 Diese TPIs werden gespeichert.

53 Nun werden zu einigen Objektpaaren verschiedene TPI vorliegen.

54 Diese verschiedenen TPI werden dann im nächsten Schritt zu einem Gesamt-TPI vereint.

55 Für eine weitere bzw. neue BDS werden die Schritte Sl und S2 wiederholt und dann wieder im Schritt S4 der Gesamt-TPI berechnet

Im Folgenden wird ein Beispiel angegeben, wie ein TPI berechnet wird, wenn zwei Objekte nur einmal innerhalb einer einzigen BDS referenziert werden. In diesem Fall berechnet sich der TPI der zwei Objekte nur basierend auf deren Distanz zueinander in dieser einzigen BDS. Der TPI von zwei verlinkten Objekten kann berechnet werden als

TPI(Objl|Obj2) = 1 / (Distanz/2) ^A 2

Für obiges Beispiel zu den Distanzen aus Fig. 4 würden sich folgenden TPI ergeben: TPI(Linkl |Link2) - 1 / (2/2) ^A 2 = 1

TPI(Linkl|Link3) - 1 / (2/2) ^A 2 = 1

TPI(Linkl|Link4) = 1 / (4/2) ^A 2 = 1/4

TPI(Linkl|Link6) = 1 / (5/2) ^A 2 = 0,16

Es können auch beliebige andere Berechnungsvorschriften verwendet werden. Der berechnete Wert ist ein temporärer Wert, welcher durch die folgenden Faktoren verändert bzw. angepasst werden kann, wobei das Anpassen optional vorgesehen werden kann: a) Anzahl der Knoten in einer Ebene

Je mehr Knoten (unabhängig davon, ob mit oder ohne referenziertes Objekt) sich in einer Ebene befinden, desto geringer ist die Älinlichkeit der referenzierten Objekte. Das heißt, Linkl und Link2 oder Link5 und Link6 haben tendenziell eine niedrige Verwandtschaft bzw. Ähnlichkeit zueinander als Link 9 und LinklO. Befinden sich zwei Links in verschiedenen Ebenen, werden alle Knoten beider Ebenen zusammengezählt. Anhand des Beispiels in Fig. 5 könnte Anpassung wie folgt vorgenommen werden:

TPIneu = TPIalt falls Anzahl Knoten = 2

TPIneu = TPIalt * 0,8 falls Anzahl Knoten zwischen 3 und 5 einschließlich TPIneu = TPIalt * 0,5 falls Anzahl Knoten größer 5

Diese Berechnungsvorschriften sind lediglich beispielhaft und k nnen je nach Anforderung durch andere Vorschriften ersetzt werden. Wichtig ist letztlich, dass die Anzahl der Knoten als Gewichtungsfaktor herangezogen wird.

b) Tiefe der Ebene

Je tiefer die Ebene von zwei Links bzw. zwei Referenzen auf Objekte, desto stärker ist ihre Verwandtschaft bzw. Ähnlichkeit. Im Beispiel nach Fig. 6 wären Linkl und Link2 tendenziell weniger stark verwandt bzw. weniger ähnlich als Link3 und Link4. Dies beruht auf der Annahme, dass desto tiefer die Ebene desto spezialisierter das Thema.

Der neue TPI berechnet sich aus dem alten TPI mal der Wurzel der relativen Tiefe der Knoten, also

TPIneu = TPIalt * Wurzel(aktuelle Tiefe / maximale Linktiefe in der BDS) Im Beispiel nach Fig. 6 wäre die Tiefe von Linkl und Link2 jeweils 2 (Anzahl der Kanten bis zur Wurzel). Die Tiefe von Link3 und Link4 wäre vier. Das heißt, die relative Tiefe von Link3 und Link4 ist 1 (4/4), die maximal mögliche Tiefe. Die relative Tiefe von Linkl und Link2 ist 2/4 bzw. ^l A. Als Tiefe für ungleiche Paare wie Linkl und Link3 wird der niedrigere Wert genommen (also Vi).

c) Selbstverlinkungen

Verlinkt der Anwender in seiner BDS Objekte die er selbst erstellt hat bzw. die ihm gehören, können die hieraus errechneten Ähnlichkeitswerte optional ignoriert oder abgeschwächt werden. Das gleiche gilt für BDS von Anwendern die in enger Beziehung zu den Herstellern von verlinkten Objekten stehen. In Beziehung stehen Anwender die zum Beispiel bei der gleichen Organisation arbeiten, gemeinsam an Projekten gearbeitet haben oder zusammen wissenschaftliche Arbeiten veröffentlicht haben. Beispiel: Ein Wissenschaftler referenziert in seiner Arbeit sich selbst oder einen guten Kollegen mit dem er schon einmal zusammen ein Paper veröffentlicht hat. Dann wird diese Referenz nicht beachtet,

d) Mehrfaches Verlinken eines Objektes in einer BDS

Es kann vorkommen, dass in einer BDS das gleiche Objekt mehrfach verlinkt ist (im Beispiel nach Fig.2 etwa Link2). In diesem Fall können zwei verschiedene TPIs für das Paar Linkl und Link2 sowie für das Paar Link2 und Link3 berechnet werden. Der Ablauf für das Berechnen des (gewichteten bzw. angepassten) TPI kann folgender sein:

i. Der TPI wird für alle möglichen Kombinationen berechnet;

ii. Der niedrigere TPI wird verworfen - es wird nur der stärkere TPI verwendet; iii. Transitivität: Wurde für Linkl und Link2 der TPI X und für Link2 und Link3 der TPI Y berechnet, kann davon ausgegangen werden, dass sich Linkl und Link3 ebenfalls ähnlich sind (Transitivitätsprinzip, d.h. wenn A=B und B=C, dann A=C oder wenn A>B und B>C dann A>C). Darum gilt erfindungsgemäß: Wurde innerhalb einer BDS für die Objekte A und B der TPI X und für die Objekte B und C der TPI Y berechnet, erhalten die Objekte A und C den TPI X * Y sofern der Wert höher ist als die direkt berechnete Ähnlichkeit von A und C. Optional kann der endgültige Wert noch um einen Faktor eingeschränkt werden, also z.B. X* 7*0,9.

Die so angepassten TPIs können wiederum in einem Speichermedium gespeichert werden.

Im Folgenden wird nun beispielhaft erläutert, wie Ähnlichkeiten zwischen Objekten berechnet werden, die in verschiedenen BDS referenziert werden. Der Grundgedanke hierbei ist, dass der höchste TPI übernommen wird. Falls es aber viele niedrigere TPIs gibt, kann dies den Gesamt-TPI abschwächen. Der Gesamt-TPI errechnet sich dann wie folgt: Gesamt-TPI = (Summe der höchsten Ähnlichkeitswerte + Summe (Wurzel der restlichen Ähnlichkeitswerte) ) / Anzahl Ähnlichkeitswerte

Beispiel: Für das Paar Objek X und ObjektY werden aus fünf BDS die fünf TPIs 0,8; 0,8; 0.5; 0.5; 0,3 errechnet. Dann ist der Gesamt-TPI = (0,8+0,8+Wurzel(0,5)+Wurzel(0,5)+ Wurzel(0,3)) / 5 = (0,8 + 0,8 + 0,71 + 0,71 + 0,54 ) / 5 = 0,712. Ist der Endwert größer als der größte Einzelwert (0,8 im Beispiel), dann wird der größte Einzelwert als Gesamt-TPI genommen. Alternativ zu diesem Verfahren kann auch der Mittelwert gebildet werden, nur der höchste Wert übernommen werden, etc.

Manche Objekte werden sehr häufig referenziert, z.B. Bücher die zur Standardliteratur in einem bestimmten Bereich gehören. Hier sagt es wenig aus, wenn ein solches Standardwerk mit einem anderen Buch dicht beieinander verlinkt wird. Beispiele hierzu sind:

- Die Objekte A und B wurden von drei verschiedenen BDS verlinkt und weder A noch B wurden in irgendeiner anderen BDS verlinkt.

- Die Objekte C und D wurden von vier verschiedenen BDS verlinkt aber Objekt C wurde noch von 10 anderen BDS verlinkt (die nicht Objekt D verlinkt haben) und Objekt D wurde ebenfalls in anderen BDS verlinkt, die nicht Objekt C verlinkt haben.

- Dann sind A und B stärker verwandt bzw. ähnlicher als C und D.

Eine mögliche Berechnungsvorschrift hierzu wäre:

TPIneu = TPIalt * (Anzahl zusammen referenziert / Summe (Anzahl einzeln referenziert))

Zum Beispiel. Objekt A und B wurden in 3 BDS zusammen verlinkt und haben bisher einen TPI von 0,7. Objekt A wurde außerdem in 2 weiteren BDS verlinkt und Objekt B in einer weiteren. Dann ist der neue TPI = 0,7 * 3 / (2+3) = 0,7*3/5 = 0,42. Möglich sind auch Berechnungen, die den endgültigen TPI weniger stark abschwächen.

Es kann auch angenommen werden, dass in Texten zu erst etwas allgemein beschrieben ist und dann konkreter wird. Zwei Referenzen bzw. Links am Anfang wären vermutlich nicht so sehr am gleichen Thema, während zwei Links gegen Ende näher am gleichen Thema wären. Daher kann gelten: Je später zwei Links bzw. Referenzen vorkommen, desto stärker ihre Beziehung bzw. der von diesen Referenzen referenzierten Objekte. Im Beispiel nach Fig. 8 wäre die Beziehung zwischen Link3 und Link4 vermutlich ein ganz klein wenig stärker als zwischen Linkl und Link2.

In einer weiteren Ausführungsform der Erfindung kann die Anzahl der Editierungen einer BDS berücksichtigt werden. Das bedeutet, je öfter eine BDS bzw. ihre Einträge editiert wurden, umso zuverlässiger sind die Informationen die man daraus erhält. Wurde beispielsweise ein Link bzw. eine Referenz zu einem Objekt erzeugt und eine Woche später editiert (z.B. innerhalb der BDS verschoben), kann davon ausgegangen werden, dass die Einordnung dann von höherer Güte ist.

In einer noch weiteren Ausfuhrungsform kann die Kompetenz des Anwenders berücksichtigt werden. Wird der Ersteller einer BDS als besonders kompetent erachtet, wird den Ähnlichkeitswerten, die basierend auf dieser BDS errechnet werden, mehr Gewicht gegeben. Kompetenz kann mit aus dem Stand der Technik bekannten Verfahren bestimmt werden. Wird ein Anwender vom System als besonders kompetent erachtet, werden die Ähnlichkeitswerte, die basierend auf seinen BDS errechnet werden, bei der Berechnung eines endgültigen TPI doppelt (oder dreifach) gewichtet. Im obigen Beispiel, in welchem die Ähnlichkeitswerte 0,8; 0,8; 0.5; 0.5; 0,3 waren, und angenommen der erste Wert (0,8) war von einem besonders kompetenten User, dann würden folgende Werte als Grundlage dienen: 0,8; 0,8; 0,8; 0.5; 0.5; 0,3; (d.h. eine zusätzliche 0,8 - der erste Wert wird doppelt berücksichtigt).

In einer noch weiteren Ausführungsform kann die Anzahl der BDS vom gleichen Anwender berücksichtigt werden. Ein Anwender könnte sehr viele BDS erstellen, die alle das gleiche Paar von Objekten referenzieren. In diesem Fall würde die Meinung eines Anwenders die Gesamtbewertung der Ähnlichkeit von zwei Objekten ungewollt stark beeinflussen. Um diese zu vermeiden, werden diese Werte genommen und als „eigenständiges System" betrachtet, sodass aus den mehreren Werten mit dem erfindungsgemäßen Verfahren ein Gesamtwert berechnet wird. Dieser Gesamtwert fließt dann in die Endberechnung mit den Werten anderer Anwender bzw. anderer BDS mit ein. Ein Beispiel hierfür ist: Wir haben die Werte 0,8; 0,8; 0.5; 0.5; 0,3 (vgl. oben). Eine 0,8 und die 0,3 stammen vom gleichen Anwender. Dann wird aus einer 0,8 und der 0,3 ein vorläufiger Ähnlichkeitswert berechnet: (0,8+Wurzel(0,3)) / 2 = (0,8 + 0,54) / 2 = 0,67. Anschließend wird der endgültige Ähnlichkeitswert berechnet aus der 0,67 und den verbleibenden Werten, also 0,8; 0,67; 0.5; 0.5. Alternativ kann auch nur der höchste Wert oder normale Mittelwert des Anwenders übernommen werden.

Auch bei der Berechnung von Ähnlichkeiten zwischen Objekten, die in verschiedenen BDS referenziert werden, kann Selbstverlinkung berücksichtigt werden (vgl. oben)

Beispielsweise kann der höchste TPI verwendet werden und mit der Hälfte gewichtet. Die anderen TPI können ignoriert werden. Im Beispiel 0,8; 0.5; 0,3 und der Annahme, dass

0.8 vom Anwender selbst sind, wäre der TPI:

0,5 * 0,8 + Wurzel(0,5) + Wurzel(0,3) / 2,5 = (0,4 + 0,71 + 0,55 ) / 2,5 = 0,66 Ebenso kann auch die bereits oben beschriebene Transitivität berücksichtigt werden.

Gewerbliche Anwendbarkeit der Erfindung

Mit dem erfindungsgemäßen Verfahren und dem System können beispielsweise Empfehlungsdienste realisiert werden oder auch Suchmaschinenergebnisse verbessert werden.

1. Realisierung eines Empfehlungsdienstes

Ein Benutzer gibt ein Objekt an, welches ihm gefällt und zu welchem er relevante Objekte erhalten möchte. Dies kann er bewerkstelligen, indem er etwa:

i. den Namen des Objektes angibt; und/oder

ii. einen anderen Identifikator angibt (z.B. Titel, Autor, Hashwert, etc.); und/oder iii. das Objekt an den Server überträgt, auf dem der Empfehlungsdienst ausgeführt wird; und/oder

iv. eine URI zu dem Objekt angibt.

Alternativ kann automatisch bestimmt werden, welches Objekt der Nutzer mag. Dies kann mit gängigen Verfahren (z.B. implizite und/oder explizite Bewertungen) realisiert werden. Anschließend werden aus der Datenbank Objekte gesucht die möglichst ähnlich zu dem Objekt sind, welches der Nutzer mag. Diese Suche kann unter Einbeziehung der mit dem erfindungsgemäßen Verfahren berechneten Ähnlichkeitswerte erfolgen. Die ermittelten (ähnlichen) Objekte bzw. Informationen zu den Objekten werden angezeigt (z.B. auf einer Website oder in einer Software). Verbessern von Suchergebnisseiten

Im Allgemeinen werden auf einer Suchergebnisseite die Dokumente die das Suchwort enthalten angezeigt. Die relevantesten werden dabei zuerst angezeigt. Die Relevanz kann über verschiedene Verfahren berechnet werden. Es kann dabei durchaus vorkommen, dass in einer kleinen Trefferliste das passendste Dokument A eine sehr hohe Relevanz hat (z.B. 0,90) und das nächstbeste Dokument B eine recht niedrige Relevanz (z.B. 0,40). Das Suchergebnis wird deutlich verbessert indem, Objekte angezeigt werden, die zu den relevanten Dokumenten sehr ähnlich sind aber mit dem ursprünglichen Verfahren nicht berücksichtigt würden (da z.B. das Suchwort nicht im Dokument vorkommt).

Für ein Dokument A und ein Dokument X wird mit dem erfindungsgemäßen Verfahren eine starke Verwandtschaft errechnet (z.B. 1). Für eine textbasierte Suche, welche das Dokument A als relevant einstuft, wird nun Dokument X ebenfalls in der Ergebnisliste angezeigt werden. Die Relevanz für Dokument X für jede beliebige Suche, welche Dokument A als relevant betrachtet, errechnet sich als Relevanz von A * Ähnlichkeit von A und X, unter der Annahme, dass beide Werte zwischen 0 und 1 sind. Anderenfalls müssten die Werte anders kombiniert werden.