DE69528896T2

DE69528896T2 - Verfahren zur clusterbildung in multidimensional voneinander abhangigen daten

Info

Publication number: DE69528896T2
Application number: DE69528896T
Authority: DE
Inventors: Frank J Derose; Linnea A Dunn; Richard F Poppen; Brian E Smartt
Original assignee: Tele Atlas North America Inc
Current assignee: TomTom North America Inc
Priority date: 1994-05-18
Filing date: 1995-05-17
Publication date: 2003-09-04
Anticipated expiration: 2015-05-18
Also published as: EP0765504A1; EP0765504A4; JP3637971B2; AU2552495A; ATE228256T1; AU696058B2; MX9605656A; WO1995031788A1; US5706503A; EP0765504B1; JPH10500511A; CA2190486A1; DE69528896D1; CA2190486C

Description

HINTERGRUND DER ERFINDUNG

Gebiet der Erfindung

Die vorliegende Erfindung betrifft allgemein Verfahren zum Speichern von Daten in einer Datenbank und insbesondere ein Verfahren zum Gruppieren mehrdimensionaler, verwandter Daten, beispielsweise in der Art geographischer Kartendaten, in einer Datenbank auf eine Weise, die hinsichtlich der für das Gruppieren erforderlichen Betriebsmittel und des dafür erforderlichen Platzes wirksam ist, und die zum Verringern der zum Auffinden ausgewählter Datenblöcke oder Daten aus der Datenbank erforderlichen Zeit führt.

Beschreibung des Stands der Technik

Seit ihrer Erfindung wurden Computer zum Durchsuchen oder auf andere Weise erfolgenden Verarbeiten von Datenansammlungen verwendet, die zu groß sind, um in ihrer Gesamtheit auf einmal im Hauptspeicher gehalten zu werden. Programme haben daher lange Zeit große Datenmengen behandelt, indem sie die Dateneinheiten in einer Datei nacheinander blockweise gelesen haben. Wenn eine Datei nacheinander durch getrenntes Handhaben jedes Datenblocks zu verarbeiten ist, ist die Organisation einer Datei nicht sehr wichtig. Wenn eine Datei durch wiederholtes Auffinden einer angegebenen interessierenden Dateneinheit und durch Bearbeiten von ihr verwendet werden soll, kann die Organisation der Datei sehr wichtig sein, um diesen Vorgang wirksam auszuführen.
Zu diesem Zweck werden die Datenblöcke in einer Datei häufig in einer speziellen Reihenfolge sortiert, so daß bestimmte Datenblöcke gefunden werden können, indem nach ihnen entsprechend ihrer Position in dieser Reihenfolge gesucht wird. Beispielsweise kann eine Bank eine Datei von Informationen über ihre Kontoinhaber nach der Kontonummer sortieren. Daraufhin kann der Datenblock für ein bestimmtes Konto leicht anhand seiner Nummer gefunden werden. Eine Datei kann nach mehr als einer Folge indexiert werden, so daß Datenblöcke anhand mehr als eines Attributs gefunden werden können. Es gibt einen sehr großen Literaturumfang, der sich mit dem Indexieren, Sortieren und Suchen von Daten beschäftigt.
Bei den meisten Dateiorganisationsverfahren werden Daten nach irgendeinem Attribut, wie ein Kundenname sortiert. Verbindungen in der Sortierungsreihenfolge könnten unter Verwendung anderer Ordnungskriterien unterbrochen werden, die Sortierung erfolgt jedoch weiterhin im wesentlichen eindimensional. Die Organisation ist derart, daß für jeweils zwei Datenblöcke einer dem anderen vorhergeht. Dies ist für das Speichern von Daten in einem Computer zweckmäßig, weil die Speichervorrichtungen von Computern auch im wesentlichen eindimensional sind. Die Datenblöcke kommen in einer festgelegten Folge an, und es ist bei vielen Speichervorrichtungen eine erhebliche Zeit erforderlich, um sich von einem Punkt in einer Dateifolge zu einem anderen zu bewegen (selbst wenn die Oberfläche einer Platte zweidimensional ist, werden die Daten auf der Platte in einer eindimensionalen Folge gespeichert).
Wenn die gespeicherten Daten im wesentlichen zweidimensional sind (oder eine beliebige Dimension größer als 1 aufweisen), wie es beispielsweise bei geographischen Kartendaten der Fall ist, ist diese Organisation nicht sehr zweckmäßig. Man möchte häufig Datenblöcke für Objekte eingeben, die sich im entsprechenden mehrdimensionalen Raum in der Datei nahe zueinander befinden, weil die Datei so verwendet wird, daß häufig vom Datenblock für ein Objekt zum Datenblock für ein nahegelegenes Objekt übergegangen wird. Das Organisieren der Datei auf eine Weise, die dies unterstützt, ist jedoch nicht leicht. Falls jemand beispielsweise eine Liste beliebig gewählter Orte in einer Stadt hat, gibt es kein Verfahren, um sie anzuordnen, das die Datenblöcke für Punkte, die auf dem Boden nahe beieinander liegen, in der Datei nahe beieinander anordnet. Das Beste, was erhofft werden kann, ist daß so viele verwandte Datenblöcke wie möglich in der Datei nahe beieinander angeordnet werden.
Sicherlich ist das Sortieren nach einer Koordinate und das Unterbrechen von Verbindungen mit der anderen kein sehr gutes Verfahren. Man stelle sich vor, daß Punkte in einer Stadt der Länge nach sortiert sind, wobei die Verbindungen durch Sortieren nach der Breite unterbrochen sind. Dann könnten beispielsweise die Datenblöcke für interessierende Punkte, die auf dem Boden nahe beieinander liegen, in der Datei durch die Datenblöcke für viele Punkte getrennt sein, die in der Länge zwischen den interessierenden Punkten liegen, jedoch in der Breite am anderen Ende der Stadt liegen.
Dementsprechend wurden verschiedene Techniken entwickelt, um Datenblöcke, die Objekte aus einem Raum darstellen, der im wesentlichen mehrdimensional ist, in Gruppen zu sammeln. Viele von ihnen sind rein geographisch (oder geometrisch) und sammeln Datenblöcke für Objekte, die nahe beieinander liegen, jedoch nicht verwandt sind. Viele andere sind hinsichtlich der beim Gruppieren verwendeten Betriebsmittel oder hinsichtlich der Platzverwendung in der Datendatei unwirksam. Die vorliegende Erfindung betrifft ein neues Verfahren zum Gruppieren verwandter Daten aus einem mehrdimensionalen Raum.
Es gibt in der Literatur viele Verfahren zum Gruppieren mehrdimensionaler Daten, insbesondere zweidimensionaler Daten in der Art von Kartendaten. Die meisten sind von oben nach unten ablaufende Verfahren, wie das Verfahren der Viererbäume, bei dem die zu gruppierenden Daten aufeinanderfolgend unterteilt werden, bis die sich ergebenden Gruppen so klein wie nötig sind. Diese Verfahren neigen dazu, Gruppen mit einer erheblichen Größenschwankung oder Unterteilungen, die in unterschiedlichen Bereichen der Daten verschiedene Anzahlen von Ebenen aufweisen, oder beides zu erzeugen. Andere von unten nach oben ablaufende Verfahren neigen dazu, lokal zu arbeiten, wobei eine Gruppe gefüllt wird, bevor fortgefahren wird, um die nächste aufzubauen. Dies führt gewöhnlich auch zu erheblichen Ungleichgewichten der Gruppengrößen und zu unregelmäßigen Formen. Das erfindungsgemäße Verfahren verläuft von unten nach oben, ist jedoch global, was über die ganze Datenbank zu gut ausgeglichenen und wohlgeformten Gruppen führt.
In DE-A-3 744 531 ist ein Verfahren zum Gruppieren geographischer Kartendaten offenbart, wobei Scheitelpunkte für ausgewählte interessierende Objekte eingerichtet werden, wobei die ausgewählten Paare von Scheitelpunkten durch einen Rand verbunden werden. Die Ränder werden mit einem Bewertungsmaß versehen. Die zwei Scheitelpunkte, die mit dem Rand verbunden sind, der das beste Bewertungsmaß aufweist, werden ausgewählt und kombiniert.
In DUDA, R. O., HART, P. E.: "Pattern classification and scene analysis", 1973, John Wiley & Sons, Inc., ISBN: 0 471-22361-1, S. 211-260 ist das Gruppieren als ein Prozeß zum Finden natürlicher Gruppierungen in einem Datensatz erörtert. In dem Artikel sind verschiedene mögliche Maße der Ähnlichkeit zwischen Proben, viele Kriteriumsfunktionen, die zum Finden optimaler Partitionen verwendet werden können, sowie hierarchische Gruppierungsprozeduren erörtert.
In US-A-5 212 794 ist ein Verfahren zum Anordnen von Codedatenblöcken offenbart, wobei eine Aufrufgraphik eingerichtet wird, bei der jeder Knoten einer einzigen Prozedur entspricht. Ihre Ränder entsprechen Aufrufen zwischen den Prozeduren und sind mit der Häufigkeit gewichtet, mit der die Aufrufe tatsächlich erfolgt sind. Es wird der Rand mit dem größten Gewicht ausgewählt, und die mit diesem Rand verbundenen Knoten werden nebeneinander angeordnet, um eine neue Gruppe zu bilden.
Angesichts des vorhergehend Erwähnten ist eine Hauptaufgabe der vorliegenden Erfindung ein Verfahren zum Gruppieren mehrdimensionaler, verwandter Daten, wie beispielsweise geographischer Kartendaten, in einer Computerdatenbank, das hinsichtlich der Datenwiederauffindung und der Datenspeicherung schneller und wirksamer ist als bekannte Verfahren aus dem Stand der Technik.
Die vorliegende Erfindung sieht ein Verfahren zum Gruppieren mehrdimensionaler, verwandter Daten in einer Computerdatenbank, die einen Satz von Datenblöcken aufweist, wobei jeder Datenblock Informationen über ein interessierendes Objekt speichert, vor, wobei das Verfahren die folgenden Schritte aufweist:
a) Einrichten eines Scheitelpunkts für jedes interessierende Objekt in der Computerdatenbank, um eine graphische Darstellung bereitzustellen, die mehrere in einer zweidimensionalen Fläche beabstandete Scheitelpunkte aufweist,
b) Identifizieren von Strukturmerkmalen, die Bereichen und Liniensegmenten in der zweidimensionalen Fläche entsprechen,
c) Erzeugen eines getrennten Scheitelpunkts für jeden identifizierten Bereich und jedes identifizierte Liniensegment,
d) Erzeugen eines Rands von dem Scheitelpunkt, der jedem identifizierten Bereich entspricht, zu dem Scheitelpunkt, der jedem den Bereich begrenzenden identifizierten Liniensegment entspricht,
e) Berechnen eines Bewertungsmaßes für jeden der die Scheitelpunkte verbindenden Ränder nach einer vorgegebenen Formel auf einem Computer,
f) Auswählen der zwei Scheitelpunkte, die mit dem Rand verbunden sind, der das beste Bewertungsmaß aufweist,
g) Kombinieren der zwei Scheitelpunkte durch Kombinieren der von den zwei Scheitelpunkten dargestellten Gruppen,
h) Erzeugen eines neuen verschmolzenen Scheitelpunkts und von Rändern zwischen dem neuen Scheitelpunkt und den zuvor mit den verschmolzenen Scheitelpunkten verbundenen Scheitelpunkten und Berechnen eines neuen Bewertungsmaßes für die neuen Ränder auf einem Computer,
i) Wiederholen der Schritte (f) bis (h), bis eine vorgegebene Endbedingung erreicht wurde, und
j) Speichern der restlichen Gruppen in einem von einem Computer lesbaren Medium.
Gemäß einer anderen Ausführungsform der vorliegenden Erfindung weist das vorstehend beschriebene Verfahren weiterhin den Schritt des Erzeugens und Aufrechterhaltens einer Liste von Scheitelpunkten, in der für jeden Scheitelpunkt das Bewertungsmaß des besten Rands und der andere Scheitelpunkt, mit dem dieser beste Rand verbunden ist, angeführt sind, auf.
Gemäß einer weiteren Ausführungsform der vorliegenden Erfindung weist der vorstehend beschriebene Schritt des Erzeugens und Aufrechterhaltens einer Liste von Scheitelpunkten den Schritt des Sortierens der Liste nach dem besten Bewertungsmaß auf.
Zum Erleichtern der verschiedenen vorstehend beschriebenen Verfahren werden die folgenden Prozeduren manchmal, wenn nicht immer verwendet:
a. Listen von Scheitelpunkten und ihrer zugeordneten Bewertungsmaße werden zusammengestellt, wobei die höchsten Bewertungsmaße oben in der Liste angeordnet werden.
b. Gruppen werden selbst in einem iterativen Prozeß gruppiert, wobei ihre kombinierten Größen nach jeder Iteration mit zunehmend größerer Größenbeschränkungen versehen werden, so daß ein bestimmtes Maß an Gleichmäßigkeit der Größe der Datensätze aufrechterhalten werden kann.
Gemäß einer anderen Ausführungsform der vorliegenden Erfindung ist ein Verfahren zum Kombinieren von Gruppen vorgesehen, wobei das Bewertungsmaß jedes neu erzeugten Rands der Anzahl der Ränder entspricht, die durch den neu erzeugten Rand ersetzt werden. Beginnend mit dem Kombinieren von Gruppen, die durch Ränder mit dem höchsten Wert verbunden sind, wird das Kombinieren fortgesetzt, bis die kombinierten Gruppen eine vorgegebene Größe erreichen.

KURZBESCHREIBUNG DER ZEICHNUNG

Die vorstehend erwähnten und andere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden anhand der folgenden detaillierten Beschreibung der anliegenden Zeichnung verständlich werden, wobei:
Fig. 1 eine Darstellung eines Abschnitts einer Stadtkarte ist,
Fig. 2 eine Graphik ist, in der Scheitelpunkte für jeden Bereich und für jedes Liniensegment dargestellt sind, die Strukturmerkmalen auf der Karte aus Fig. 1 entsprechen,
Fig. 3 eine Reproduktion der Graphik aus Fig. 2 ist, wobei Ränder hinzugefügt wurden, die den Scheitelpunkt für jeden Bereich mit dem Scheitelpunkt für jedes den Bereich begrenzende Liniensegment verbinden,
die Fig. 4-6 eine Reihe von Darstellungen sind, in denen das Unterdrücken eines ausgewählten Scheitelpunkts erläutert wird,
Fig. 7 eine Reproduktion der Graphik aus Fig. 3 ist, nachdem ausgewählte Scheitelpunkte unterdrückt worden sind,
Fig. 8 eine Reproduktion von Fig. 7 ist, wobei ein anderer Scheitelpunkt unterdrückt worden ist,
Fig. 9 ein Diagramm ist, in dem die Begrenzungskästen eines Bereichs und eines Liniensegments gemäß der vorliegenden Erfindung dargestellt sind,
Fig. 10 ein Diagramm ist, in dem die Begrenzungskästen von zwei Liniensegmenten gemäß der vorliegenden Erfindung dargestellt sind,
Fig. 11 ein Diagramm ist, in dem der Begrenzungskasten eines diagonalen Liniensegments gemäß der vorliegenden Erfindung dargestellt ist,
Fig. 12 eine Reproduktion der Graphik aus Fig. 8 ist, wobei Bewertungsmaße zu ausgewählten Rändern gemäß der vorliegenden Erfindung hinzugefügt wurden,
Fig. 13 ein Diagramm ist, in dem eine Verschmelzung von zwei der Scheitelpunkte aus Fig. 12 gemäß der vorliegenden Erfindung dargestellt ist,
Fig. 14 eine Graphik ist, die mehrere Scheitelpunkte mit beliebigen Bewertungsmaßen neben den verschiedenen Paare der Scheitelpunkte verbindenden Rändern enthält,
Fig. 15 eine Reproduktion der Graphik aus Fig. 14 ist, wobei zwei der Scheitelpunkte aus Fig. 14 verschmolzen wurden und ihnen zugeordnete neue Ränder erzeugt wurden,
Fig. 16 eine Daten- und Gruppengraphik gemäß einer anderen Ausführungsform der vorliegenden Erfindung ist,
Fig. 17 eine Gruppengraphik ist, die eine Reproduktion der Graphik aus Fig. 16 nach der Verschmelzung eines Paars von Scheitelpunkten und ihrer zugeordneten Ränder ist,
Fig. 18 eine Reproduktion der Graphik aus Fig. 17 nach der Verschmelzung eines Paars von Scheitelpunkten und ihrer zugeordneten Ränder ist und
Fig. 19 eine Reproduktion der Graphik aus Fig. 18 nach der Verschmelzung eines Paars von Scheitelpunkten und ihrer zugeordneten Ränder ist.

BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

Der Begriff "Strukturmerkmal" bezeichnet hier ein einziges unteilbares, von einer Datenbank beschriebenes Objekt, beispielsweise einen Abschnitt eines Flusses, einen Straßenblock, einen See, ein Segment einer politischen Grenze usw.
Die Bergriffe "Gruppe" und "Scheitelpunkt" bezeichnen jeweils eine Sammlung von einem oder mehreren Strukturmerkmalen. Der Begriff "Scheitelpunkt" wird hier mit Bezug auf eine Ansammlung von einem oder mehreren Strukturmerkmalen verwendet, wenn diese Ansammlung von Strukturmerkmalen als ein Element in einer Graphik verwendet wird. Der Begriff "Gruppe" wird hier in bezug auf eine Ansammlung von einem oder mehreren Strukturmerkmalen verwendet, wenn diese Ansammlung als eine Ansammlung von in einer Datendatei zu speichernden Strukturmerkmalen verwendet wird. Es gibt hier keine Unterscheidung zwischen einer Gruppe und einem Scheitelpunkt.
In Fig. 1 ist ein Abschnitt einer zweidimensionalen Fläche, d. h. einer allgemein mit 100 bezeichneten Stadtkarte dargestellt, die mehrere Liniensegmente 1-16, welche Wege bzw. Straßen darstellen, und fünf mit 17-21 bezeichnete Bereiche, welche von den Liniensegmenten 1-16 begrenzt sind, aufweist. Einige oder alle Liniensegmente könnten Strukturmerkmale, die zum nachfolgenden Abrufen in der Datenbank darzustellen sind, wie beispielsweise Straßen, politische Grenzen, Flüsse usw., darstellen. In diesem Beispiel stellt jedes dieser Liniensegmente ein Segment einer Straße dar. Weiterhin könnten einige oder alle der Bereiche Strukturmerkmale, die zum nachfolgenden Abrufen in der Datenbank darzustellen sind, wie beispielsweise einen Park, einen See, einen Bürokomplex usw., darstellen. In diesem Beispiel stellt der Bereich 18 einen Park dar, während die restlichen Bereiche 17, 19, 20 und 21 keine in der Datenbank zu speichernde Strukturmerkmale darstellen.
In Fig. 2 ist eine allgemein als 110 bezeichnete Graphik von Objekten auf der Karte 100 dargestellt. Die Objekte können beispielsweise einen Abschnitt bzw. ein Stück einer Straße, eines Gebäudes, eines Parks, eines Sees, einer Grenze eines Bereichs usw., umfassen. In der Graphik 110 ist ein durch einen Punkt dargestellter Scheitelpunkt für jedes Objekt, also jedes Liniensegment 1-16 und jeden Bereich 17-21, bereitgestellt. Beispielsweise sind für die Liniensegmente 8, 5, 1 und 4, die den Bereich 17 begrenzen, jeweilige Scheitelpunkte 31-34 bereitgestellt und ist für den Bereich 17 ein Scheitelpunkt 35 bereitgestellt. Es sei bemerkt, daß die horizontalen und die vertikalen Linien 8, 5, 1 und 4 und dergleichen, die in der Graphik 110 und den folgenden Graphiken vorhanden sind, Konstruktionslinien sind, die im Unterschied zu den nachstehend beschriebenen Rändern keine Bedeutung haben und lediglich bereitgestellt sind, um das relative Anordnen der Scheitelpunkte in der Graphik 110 zu erleichtern.
Wie in Fig. 3 dargestellt ist, ist der Scheitelpunkt für jeden Bereich mit dem Scheitelpunkt für jedes den Bereich begrenzende Liniensegment verbunden und diesem daher zugeordnet. Die Verbindung wird als "Rand" bezeichnet. Entgegen dem Uhrzeigersinn gezählt, gibt es beispielsweise vier Ränder 40-43, die den Scheitelpunkt 35 für den Bereich 17 mit den Scheitelpunkten 31-34 für die jeweiligen Liniensegmente 8, 5, 1 und 4 aus Fig. 1 verbinden.
Der nächste Schritt beim Verfahren zum Gruppieren von Daten gemäß der vorliegenden Erfindung besteht darin, den Scheitelpunkt für jeden Bereich und jedes Liniensegment zu unterdrücken, das nicht in der Datenbank erscheinen soll, der also keinen Daten entspricht, die nachfolgend aus der Datenbank abgerufen werden sollen. Unter Berücksichtigung, daß die Bereiche 17, 19, 20 und 21 keine in der Datenbank zu speichernde Strukturmerkmale sind, werden demgemäß zum Unterdrücken der diesen Bereichen entsprechenden Scheitelpunkte die Ränder, die die Scheitelpunkte in jedem dieser Bereiche mit ihren benachbarten Scheitelpunkten auf den Liniensegmenten verbinden, welche den Bereich begrenzen, entfernt und durch Ränder ersetzt, die die benachbarten Scheitelpunkte auf jedem der begrenzenden Liniensegmente miteinander verbinden, so daß die nicht unterdrückten benachbarten Scheitelpunkte, die durch angrenzende unterdrückte Ränder mit dem unterdrückten Scheitelpunkt verbunden sind, selbst mit einem neu konstruierten Rand verbunden werden. Wie in den Fig. 3 und 4 dargestellt ist, ist der Scheitelpunkt 35 beispielsweise durch die Ränder 40 -43 mit den benachbarten Scheitelpunkten 31-34 verbunden. Wie in Fig. 5 durch unterbrochene Linien und einen hohlen Punkt dargestellt ist, werden der Scheitelpunkt 35 und die Ränder 40-43 in den Fig. 3 und 4 unterdrückt, indem sie entfernt werden und die Scheitelpunkte 31-34 durch jeweilige Ränder 50-53 verbunden werden, woraus sich das in Fig. 6 dargestellte Graphikfragment ergibt. Die sich aus dem Unterdrücken der Scheitelpunkte in den anderen Bereichen 19, 20 und 21 unter Verwendung derselben Technik ergebende Graphik ist in Fig. 7 dargestellt. Es sei bemerkt, daß manche Ränder als gekrümmte Linien eingezeichnet sind und andere als gerade Linien eingezeichnet sind. Die Zeichnung ist lediglich als eine Hilfe beim Veranschaulichen der Verbindungen zwischen Scheitelpunkten vorgesehen. Der tatsächliche Weg der gezeichneten Linie hat keine Folgen.
Wie in Fig. 7 dargestellt ist, ist ein Scheitelpunkt 64, der den Bereich 18 darstellt, durch Ränder 54-58 mit jeweiligen Scheitelpunkten 62, 63, 32, 60 und 61 verbunden. Der dem Bereich 19 entsprechende Scheitelpunkt wurde unterdrückt, die den Bereich 19 begrenzenden Liniensegmente sind jedoch durch Scheitelpunkte 62, 65, 66 und 67 dargestellt. Der Scheitelpunkt 62 ist wie dargestellt durch jeweilige Ränder 54, 70 und 69 mit seinen benachbarten Scheitelpunkten 64, 65 und 67 verbunden.
Mit Bezug auf Fig. 8 sei bemerkt, daß, wenn es gewünscht ist, den Scheitelpunkt 62 und seine zugeordneten Ränder 54, 69 und 70 zu unterdrücken, wie in Fig. 7 dargestellt ist, der Scheitelpunkt 62 und die Ränder 54, 69 und 70 entfernt werden und die benachbarten Scheitelpunkte 64, 65 und 67, mit denen sie verbunden waren, nun durch Ränder 71, 72 und 73 verbunden werden.
Es wird verständlich geworden sein, daß jedes Strukturmerkmal in der Karte, das nachfolgend aus der Datenbank abgerufen werden soll, einen Scheitelpunkt aufweist, und daß jeder Scheitelpunkt ein Strukturmerkmal in der Karte darstellt. Weiterhin grenzen Strukturmerkmale, die in der Karte aneinander angrenzen, auch in der Graphik aneinander an, sie sind also durch einen Rand verbunden.
In der folgenden Erörterung der vorliegenden Erfindung stellt jeder Scheitelpunkt eine Gruppe dar, die ein oder mehrere Strukturmerkmale aufweist. Zunächst enthält jede Gruppe vor dem Kombinieren der Grippen nur ein Strukturmerkmal.
Wenn das Kombinieren von zwei Gruppen, beispielsweise einer ersten und einer zweiten Gruppe, erwogen wird, wird der Kombination ein Bewertungsmaß (eine Maßzahl oder ein anderer, nicht unbedingt numerischer, Wert) gegeben. Das Bewertungsmaß ist ein Maß dafür, wie gut oder wünschenswert es ist, die betrachteten Gruppen miteinander zu kombinieren.
Gemäß einer ersten Ausführungsform der vorliegenden Erfindung, bei der die Daten geographische Daten sind, gleicht das Bewertungsmaß der Fläche des Begrenzungskastens der ersten Gruppe zuzüglich der Fläche des Begrenzungskastens der zweiten Gruppe minus der Fläche des Begrenzungskastens der kombinierten Gruppen.
Es sei bemerkt, daß gemäß dieser Ausführungsform der vorliegenden Erfindung die Fläche eines Begrenzungskastens einer Gruppe die Fläche des kleinsten Rechtecks ist, dessen Grenzen von Nord nach Süd und von Ost nach West verlaufen und die Gruppe, also das eigentliche Strukturmerkmal oder die eigentlichen Strukturmerkmale, die durch einen Scheitelpunkt dargestellt werden, einschließt.
Mit Bezug auf Fig. 9 und unter Betrachtung einer Verschmelzung der Parkgruppe bzw. des Parkscheitelpunkts mit der Straßengruppe bzw. dem Straßenscheitelpunkt auf der östlichen Seite des Parks (wobei Norden am Oberteil der Seite liegt) sei bemerkt, daß die Fläche des Begrenzungskastens der Parkgruppe AB gleicht, während die Fläche des Begrenzungskastens der Straßengruppe östlich des Parks null ist. Die Fläche des Begrenzungskastens der Straßengruppe ist null, weil die Breite des Begrenzungskastens null ist, während seine Länge gleich der Länge des Straßensegments, also B, ist. Demgemäß ergibt sich beim Anwenden der vorstehenden Gleichung, daß das Bewertungsmaß für die Verschmelzung AB + 0 - AB = 0 ist. Es sei bemerkt, daß die unterbrochenen Linien in der Figur, die die Begrenzungskästen definieren, aus Gründen der Sichtbarkeit etwas gegenüber ihren wahren Positionen versetzt sind.
Mit Bezug auf Fig. 10 sei bemerkt, daß neben jedem Liniensegment ein seiner Länge entsprechender Wert angeordnet ist. Beispielsweise ist dem Liniensegment C östlich des Parks ein Wert von 2 zugeordnet und ist einem Liniensegment D, das davon ausgeht, ein Wert von 4 zugeordnet. Falls erwogen wird, die dem Liniensegment C und dem Liniensegment D zugeordneten Gruppen zu kombinieren oder zu verschmelzen, wird unter Verwendung der vorstehend beschriebenen Gleichung berechnet, daß die Fläche des Begrenzungskastens der ersten Gruppe, die aus Zweckmäßigkeitsgründen mit C bezeichnet ist, null ist und daß die Fläche des Begrenzungskastens der zweiten Gruppe, die aus Zweckmäßigkeitsgründen mit D bezeichnet ist, null ist, daß jedoch die Fläche des beide Gruppen einschließenden Begrenzungskastens CD ist. Unter Berücksichtigung, daß das Bewertungsmaß für den sich aus einer Verschmelzung ergebenden Rand die Fläche des Begrenzungskastens der ersten Gruppe zuzüglich der Fläche des Begrenzungskastens der zweiten Gruppe minus der Fläche des Begrenzungskastens der kombinierten Gruppen ist, ist ersichtlich, daß das Bewertungsmaß für das Verschmelzen der den Liniensegmenten C und D entsprechenden Gruppen C und D folgendermaßen berechnet wird:
0 + 0 - CD = -CD oder
0 + 0 - (2 · 4) = -8
Es sei bemerkt, daß der Begrenzungskasten einer Gruppe für ein Liniensegment nicht immer null ist. Beispielsweise ist in Fig. 11 ein diagonales Segment 80 mit einem Scheitelpunkt 81 dargestellt. Weil die Grenzen des Begrenzungskastens in nördlicher und südlicher sowie in östlicher und westlicher Richtung eine von Null verschiedene Erstreckung haben, ist ersichtlich, daß die Fläche des Begrenzungskastens des Scheitelpunkts 81 GH ist.
Wie in Fig. 12 dargestellt ist, wird unter Verwendung der vorstehend beschriebenen Technik für jeden Rand, der ein Paar von Gruppen der Graphik verbindet, ein Bewertungsmaß berechnet. Beispielsweise ist das Bewertungsmaß für den Rand, der die Gruppe W und die Gruppe M1 verbindet, die sich aus der Verschmelzung der Gruppen C und D ergibt, wie vorstehend berechnet -8.
Sobald jeder der Ränder in der Graphik mit einem Bewertungsmaß versehen wurde, wird der Rand mit dem größten Bewertungsmaß ausgewählt. Unter den in Fig. 12 dargestellten Rändern ist das größte Bewertungsmaß null, und alle anderen haben einen negativen Wert, sind also kleiner als null. Es sei bemerkt, daß jeder beliebige dieser Ränder ausgewählt werden kann, wenn mehr als ein Rand das gleiche größte Bewertungsmaß aufweist.
Gemäß der vorstehenden Ausführungsform läuft das Verfahren des Versehens mit einem Bewertungsmaß so ab, daß der beste Rand, also der Rand, der die Gruppen verbindet, die er am vorteilhaftesten kombiniert, das größte Bewertungsmaß aufweist. Es ist möglich, andere Verfahren zum Versehen mit einem Bewertungsmaß zu verwenden, beispielsweise eines, bei dem der beste Rand das niedrigste Bewertungsmaß aufweist.
Nachdem ein Rand ausgewählt wurde, der das größte Bewertungsmaß aufweist, beginnt die Aufgabe des Kombinierens der durch den Rand verbundenen Gruppen. Beim Kombinieren der Gruppen werden die Scheitelpunkte verschmolzen und die Listen von Strukturmerkmalen kombiniert, die jedem der Scheitelpunkte zugeordnet sind. Beispielsweise sei wiederum mit Bezug auf Fig. 12 angenommen, daß es erwünscht ist, die mit V und W bezeichneten Gruppen zu verschmelzen, die durch den mit 90 bezeichneten Rand verbunden sind.
Aus Zweckmäßigkeitsgründen sind die mit der Gruppe V verbundenen Scheitelpunkte entgegen dem Uhrzeigersinn mit den alphanumerischen Bezeichnungen W, N&sub1;, N&sub2;, N&sub3; und N&sub4; bezeichnet. Die mit dem Scheitelpunkt W verbundenen Gruppen sind entgegen dem Uhrzeigersinn mit den alphanumerischen Bezeichnungen V, M&sub1; und M&sub2; bezeichnet.
In Fig. 13 ist das Ergebnis des Kombinierens der Gruppen, also des Verschmelzens der Scheitelpunkte V und W dargestellt, wobei ein neuer Scheitelpunkt X erzeugt wird und alle Ränder, die die Scheitelpunkte N&sub1;-N&sub4; mit dem Scheitelpunkt V verbunden haben und alle Ränder, die die Scheitelpunkte M&sub1; und M&sub2; mit dem Scheitelpunkt W verbunden haben, nun mit dem neu erzeugten Scheitelpunkt X verbunden sind. Es sei bemerkt, daß die Ränder des neuen Scheitelpunkts X in derselben Reihenfolge wie die alten Scheitelpunkte V und W verbunden sind. Entgegen dem Uhrzeigersinn gelesen, verbinden die Ränder wie dargestellt mit den mit V verbundenen Scheitelpunkten, und zwar in der gleichen Reihenfolge, nämlich N&sub1;, N&sub2;, N&sub3;, N&sub4;, und dann mit den mit W verbundenen Scheitelpunkten, und zwar in der gleichen Reihenfolge, nämlich M&sub1; und M&sub2;. Alle anderen Ränder und Scheitelpunkte in der Graphik bleiben ungestört.
Nach dem wie vorstehend beschrieben erfolgten Verschmelzen der zwei Scheitelpunkte werden die neu erzeugten Ränder mit Bewertungsmaßen versehen. In dieser Hinsicht wird verständlich sein, daß nur die mit dem neuen Scheitelpunkt X verbundenen Ränder mit einem neuen Bewertungsmaß versehen werden müssen. Nachdem die Ränder mit einem neuen Bewertungsmaß versehen worden sind, wird wiederum einer der Ränder mit dem höchsten Bewertungsmaß ausgewählt. Die dadurch verbundenen Gruppen werden kombiniert, und ihre jeweiligen Scheitelpunkte werden verschmolzen, wie vorstehend mit Bezug auf die Fig. 12 und 13 beschrieben wurde.
Die Gruppenbildung und das Verschmelzen der Scheitelpunkte wird auf diese Weise fortgesetzt, bis es nicht mehr möglich ist, zwei Gruppen zu verschmelzen. Dies tritt beispielsweise dann auf, wenn die Liste der den Gruppen zugeordneten Strukturmerkmale für einen Datenblock zu groß wird und der die Strukturmerkmale der kombinierten Gruppen enthaltende Datenblock beispielsweise eine vorgegebene Anzahl von Bytes, beispielsweise 8192 Bytes, übersteigt, und bzw. oder wenn die kombinierten Gruppen einen vorgegebenen geographischen Bereich, die Anzahl der darin enthaltenen Dateneinheiten oder dergleichen übersteigen. Wenn dies auftritt, wird dem Rand zwischen den Gruppen, von denen bestimmt wurde, daß sie nicht kombiniert werden können, ein Bewertungsmaß minus unendlich (-∞) gegeben, statt daß die vorstehend beschriebene Technik zum Versehen mit einem Bewertungsmaß verwendet wird. Es wird minus unendlich verwendet, weil dies das niedrigstmögliche Bewertungsmaß ist. Das Kombinieren der Gruppen wird dementsprechend abgeschlossen, wenn jedem Rand ein Bewertungsmaß gegeben wurde.
In der Praxis läuft der Prozeß des Versehens aller Ränder mit einem Bewertungsmaß und des Findens des Rands mit dem höchsten Bewertungsmaß langsam ab. Zum Begrenzen des erneuten Versehens mit einem Bewertungsmaß und damit zum Beschleunigen des Prozesses wird eine Liste von Scheitelpunkten erzeugt. Für jeden Scheitelpunkt in der Liste sind das Bewertungsmaß des Scheitelpunkts (also das Bewertungsmaß des mit dem höchsten Bewertungsmaß versehenen Rands, der diesem Scheitelpunkt zugeordnet ist) und der benachbarte Scheitelpunkt, womit dieser das höchste Bewertungsmaß aufweisende Rand verbunden ist, aufgeführt. Falls mehr als ein Rand dasselbe höchste Bewertungsmaß aufweist, wird ein solcher benachbarter Scheitelpunkt beliebig gewählt. Die Liste der Scheitelpunkte wird entsprechend den Bewertungsmaßen der Scheitelpunkte sortiert. Beispielsweise ist in Fig. 14 eine Graphik mehrerer Scheitelpunkte A-H dargestellt, wobei beliebige Bewertungsmaße neben den verschiedenen Rändern angeordnet sind, die Paare der Scheitelpunkte miteinander verbinden. Es sei bemerkt, daß der das höchste Bewertungsmaß aufweisende Rand vom Scheitelpunkt C das Bewertungsmaß 2 hat. Es gibt zwei dieser Ränder. Einer ist mit dem Scheitelpunkt A verbunden, und der andere ist mit dem Scheitelpunkt D verbunden. In der folgenden Liste ist der Scheitelpunkt D gewählt. Danach werden die Scheitelpunkte sortiert, wobei die Scheitelpunkte, die die höchsten Bewertungsmaße aufweisen, oben in der Liste angeordnet sind und die Scheitelpunkte, die die niedrigsten Bewertungsmaße aufweisen, unten in der Liste auftreten.
Es ist in der Liste, in der der Scheitelpunkt mit dem höchsten Bewertungsmaß oben in der Liste angetroffen wird, ersichtlich, daß die nächste Verschmelzung die Scheitelpunkte E und F aufweist.
Nachdem die Scheitelpunkte E und F so verschmolzen worden sind, daß ein neuer Scheitelpunkt Z erzeugt wurde, wie in Fig. 15 dargestellt ist, werden die neu erzeugten Ränder mit Bewertungsmaßen versehen. Es sei bemerkt, daß das Bewertungsmaß für die neu erzeugten Ränder, die mit dem Scheitelpunkt Z verbunden sind, für die Zwecke dieses Beispiels beliebig sind. Es sei wiederum bemerkt, daß die Bewertungsmaße der nicht betroffenen Ränder die gleichen bleiben und daß nur die Ränder, die mit dem Scheitelpunkt Z verbunden sind, mit einem Bewertungsmaß versehen werden müssen. Es wird zu Darstellungszwecken angenommen, daß die Bewertungsmaße für die mit dem neuen Scheitelpunkt Z verbundenen Ränder die folgenden sind:
B-Z 3
D-Z 2
H-Z ∞
In der vorstehend beschriebenen Liste der Scheitelpunkte sind die Anführungen für E und F gelöscht, weil die Scheitelpunkte E und F verschwunden sind.
Als nächstes wird eine Anführung für Z hinzugefügt, und seine Position und die Positionen der zu Z benachbarten Scheitelpunkte, also B, D und H, werden so angepaßt, wie es entsprechend dem Betrag ihrer Bewertungsmaße erforderlich ist. Es ist ersichtlich, daß sich die folgende neue Liste ergibt:
Bei manchen Anwendungen besteht die vorgesehene Verwendung der in Gruppen angeordneten Daten darin, daß Sätze von Gruppen angesammelt werden sollen, um größere Gruppen hierarchisch zu bilden. Das heißt, daß ein Satz von Gruppen gebildet werden soll und dann ein anderer Satz von Gruppen gebildet werden soll, so daß der Satz von Elementen jeder Gruppe in der zweiten Gruppierung die Vereinigung der Sätze von Elementen einer Ansammlung von Gruppen der ersten Gruppierung ist. In diesem Fall wird der zweite Gruppierungsvorgang begonnen, wobei sich die Graphik in dem Zustand befindet, in dem sie vom ersten Gruppierungsvorgang zurückgelassen wurde, und nicht ein Datenelement je Scheitelpunkt aufweist, und es wird die Prioritätswarteschlange der Ränder nach Bedarf rekonstruiert, wenn der Mechanismus zum Versehen der Ränder mit Bewertungsmaßen geändert wurde.
Alternativ besteht bei manchen Anwendungen die vorgesehene Verwendung der in Gruppen angeordneten Daten darin, daß Gruppen einer höheren Ebene gebildet werden sollen, deren Elemente selbst Gruppen einer niedrigeren Ebene sind. In diesem Fall wird die vorliegende Erfindung einfach wieder verwendet. Beim zweiten Gruppierungsprozeß sind die Datenelemente die Gruppen des ersten Gruppierungsprozesses und nicht die beim ersten Gruppierungsprozeß gruppierten Datenelemente.
Beim manchen Anwendungen ist die Natur der in Gruppen angeordneten Daten derart, daß das vorstehend beschriebene Verfahren Gruppen erzeugen kann, deren Größe sich zu sehr ändert. Es kann dann nützlich sein, die Technik iterativ mit zunehmend größeren Grenzen anzuwenden. Es sei beispielsweise angenommen, daß eine Gruppe höchstens N Bytes enthalten darf. Die Daten könnten einmal gruppiert werden, wobei die Größe jeder Gruppe auf N/16 Bytes begrenzt ist, und diese Gruppen könnten dann erneut angesammelt werden, um größere Gruppen zu bilden, deren Größe auf N/4 Bytes begrenzt ist, und es könnten dann diese größeren Gruppen erneut angesammelt werden, um noch größere Gruppen zu bilden, deren Größe auf N Bytes begrenzt ist. Die Erfahrung hat gezeigt, daß dieser iterative Prozeß zu Gruppen gleichmäßigerer Größe führt.
Wie vorstehend erörtert wurde, hängt die Bestimmung, ob zwei Gruppen kombiniert werden können, häufig davon ab, ob die Größe des Ergebnisses zu hoch ist. In diesen Fällen ist das Format, in dem die Daten gespeichert sind, häufig derart, daß das Kombinieren von zwei Gruppen zu einer neuen Gruppe führt, deren Größe von der Summe der Größen der zwei ursprünglichen Gruppen verschieden ist. Es kann recht aufwendig sein, die genaue Größe der kombinierten Gruppe zu berechnen, jedoch viel einfacher sein, eine geschätzte Obergrenze für die Größe der kombinierten Gruppe zu berechnen. In diesen Fällen kann mit jedem Scheitelpunkt eine geschätzte Obergrenze der Größe seiner Gruppe gespeichert werden, welche dann verwendet wird, um die Kombinierbarkeit von Gruppen konservativ zu beurteilen, wobei manchmal die Kombination von zwei Gruppen abgelehnt wird, weil die Größenschätzungen fälschlicherweise angeben, daß das Ergebnis zu groß sein kann. Dies kann zu einer erheblichen Einsparung an Rechenaufwand führen. Dieses Verfahren kann mit der gelegentlichen Berechnung der wahren, genauen Größe jeder Gruppe kombiniert werden, wobei diese beispielsweise einmal zu Beginn jedes iterativen oder hierarchischen Schritts oder zu beliebig gewählten Zeiten während des Gruppierungsprozesses erfolgt.
Bei wieder anderen Anwendungen ist die Natur der in Gruppen angeordneten Daten derart, daß Gruppen entdeckt werden, deren Kombination während des Ablaufs des Gruppierungsprozesses wünschenswert ist. Falls es sich bei den in Gruppen angeordneten Daten beispielsweise um geographische Daten handelt und das Minimieren des Ausmaßes der Überlappung der Gruppen erwünscht ist, kann nach dem Stattfinden einer gewissen Ansammlung herausgefunden werden, daß es zwei Gruppen gibt, deren Scheitelpunkte nicht durch einen Rand verbunden sind, so daß das geographische Ausmaß der einen das geographische Ausmaß der anderen vollständig enthält. Es wird dann wünschenswert, einen Rand zwischen den Scheitelpunkten der Gruppen hinzuzufügen.
Es kann ein Schritt hinzugefügt werden, in dem ein solches Paar von Gruppen gesucht wird. Leider kann dieser Vorgang ziemlich rechenaufwendig sein, wenn jedes Paar von Scheitelpunkten in der ganzen Gruppengraphik geprüft wird. Falls die Gruppengraphik jedoch als eine ebene Graphik beibehalten wird, können viele solche Paare von Scheitelpunkten schnell gefunden werden, indem jeder Flächenteil der Graphik untersucht wird (ein Flächenteil einer ebenen Graphik ist ein Gebiet der Ebene, das von Rändern der Graphik begrenzt wird) und jedes Paar nicht benachbarter Scheitelpunkte in dem Flächenteil geprüft wird. Falls dann weiterhin ein Rand hinzugefügt wird, bleibt die Ebenheit der Gruppengraphik bewahrt.
Gemäß einer anderen Ausführungsform der Erfindung stellen die in Gruppen anzuordnenden Daten selbst die Scheitelpunkte einer Graphik dar. Die Scheitelpunkte, deren Anordnung in Gruppen wünschenswert ist, sind jene, die in der ursprünglichen Graphik durch einen Rand verbunden sind. In diesem Fall kann die ursprüngliche Graphik selbst als der Anfangszustand der Gruppengraphik verwendet werden.
Bei dieser Ausführungsform besteht der Zweck der Gruppierung darin, die Gesamtzahl der Ränder der ursprünglichen Graphik zu minimieren, die Scheitelpunkte in verschiedenen Gruppen verbinden. Um dies zu erreichen, ist jedem Rand in der Gruppengraphik die Anzahl der Ränder in der durch diesen Rand dargestellten ursprünglichen Graphik zugeordnet. Diese Anzahl wird als das "Gewicht" des Rands bezeichnet. Das Mittel zum Speichern der Gruppengraphik wird so modifiziert, daß dieses Gewicht zusammen mit jedem Rand gespeichert werden kann. Nun besteht der Zweck darin, das Gesamtgewicht aller Ränder in der Gruppengraphik zu minimieren, wenn die Gruppierung abgeschlossen ist.
Zuerst wird das Bewertungsmaß jedes Rands in der Gruppengraphik seinem Gewicht gleichgesetzt. Daraufhin werden zwei Gruppen kombiniert. Die Ränder der ursprünglichen Graphik, die zuvor zwischen den zwei Gruppen verlaufen sind, bleiben nun innerhalb einer einzigen Gruppe. Es sind keine anderen Ränder zwischen Gruppen betroffen. Wenn zwei Gruppen miteinander kombiniert werden, die einen gemeinsamen Nachbarn haben, wird das Gewicht des Rands des neuen Scheitelpunkts, der zu diesem Nachbarn verläuft, der Summe der Gewichte der vorhergehenden Ränder gleichgesetzt. Daher bleiben die Randgewichte und die Anzahl der ursprünglichen Ränder zwischen den Gruppen in jedem Schritt synchronisiert.
Weil der Begriff der geographischen Kompaktheit bei dieser Ausführungsform nicht auftritt, ist es nicht erforderlich, die Gruppengraphik als eine ebene Graphik beizubehalten.
In den Fig. 16-19 ist eine Kombination aus einer Datengraphik und einer Gruppengraphik mit sechs Scheitelpunkten 1-6 dargestellt, die durch mehrere horizontale, vertikale und diagonale Linien, also Ränder, miteinander verbunden sind. Zu Darstellungszwecken werden die Scheitelpunkte 1 und 2 verschmolzen, wie durch die von Scheitelpunkten 1 und 2 umgebenen unterbrochenen Linien dargestellt ist.
Wie in Fig. 17 dargestellt ist, wird nach dem Verschmelzen der Scheitelpunkte 1 und 2 ein mit 1,2 bezeichneter neuer Scheitelpunkt zusammen mit neuen Rändern, die sich daraus ergeben, erzeugt. Gemäß dieser Ausführungsform gleicht das Bewertungsmaß für den neu erzeugten Rand der Summe der Bewertungsmaße der durch den neu erzeugten Rand ersetzten Ränder. Zum Bestimmen dieser Summe ist es erforderlich, die vorhergehende Graphik zu betrachten. Dort ist ersichtlich, daß die zwischen 1,2 und 5 und zwischen 1,2 und 6 verlaufenden neu erzeugten Ränder das Bewertungsmaß 2 bzw. 1 aufweisen. Der Grund, aus dem der von 1,2 nach 5 verlaufende Rand das Bewertungsmaß 2 aufweist, kann Fig. 16 entnommen werden, wo ein Rand mit einem Bewertungsmaß von 1 von 2 nach 5 verlaufen ist und ein anderer Rand, der auch ein Bewertungsmaß von 1 aufweist, von 1 nach 5 verlaufen ist, woraus sich die Summe 2 ergibt. In den anderen Fällen, nämlich 1,2 nach 4 und 1,2 nach 3 verlief zwischen den jeweiligen Scheitelpunkten nur ein Rand mit einem Bewertungsmaß von 1.
Der nächste Schritt des Verfahrens gemäß dieser Ausführungsform der vorliegenden Erfindung besteht darin, diese Gruppen, die durch einen Rand mit dem größten Bewertungsmaß, also den 1,2 und 5 verbindenden Rand, verbunden sind, wieder zu verschmelzen.
Wie in Fig. 18 dargestellt ist, wird beim Prozeß des Verschmelzens der Scheitelpunkte 1,2 und 5 ein mit 1,2,5 bezeichneter neuer Scheitelpunkt erzeugt, was zur Erzeugung eines neuen Rands zwischen 1,2,5 und dem Scheitelpunkt 6 führt.
Anhand Fig. 17 ist ersichtlich, daß sich beim Berechnen der neuen Bewertungsmaße für die Ränder in der Gruppengraphik aus Fig. 18 ergibt, daß der Rand zwischen dem Scheitelpunkt 1,2,5 und dem Scheitelpunkt 4 das Bewertungsmaß 2 ergibt. Dies liegt daran, daß vor dem Verschmelzen zwei Ränder den Scheitelpunkt 4 mit dem Scheitelpunkt 1,2 und dem Scheitelpunkt 5 verbunden haben. In ähnlicher. Weise weist der neu erzeugte Rand zwischen dem Scheitelpunkt 1,2,5 und dem Scheitelpunkt 6 ein Bewertungsmaß von 2 auf, weil, wie in Fig. 17 dargestellt ist, der Scheitelpunkt 6 durch einen Rand mit einem Bewertungsmaß von 1 und durch einen anderen Rand mit einem Bewertungsmaß von 1 mit 5 verbunden war. Das Bewertungsmaß der den Scheitelpunkt 1,2,5 und den Scheitelpunkt 3 verbindenden Ränder und des den Scheitelpunkt 3 und den Scheitelpunkt 6 verbindenden Rands bleibt gleich 1.
Es sei zu Darstellungszwecken angenommen, daß die kombinierten Scheitelpunkte 1,2,5 die größtmögliche Gruppe erzeugen, so daß kein anderer Scheitelpunkt mit der Gruppe 1,2,5 kombiniert werden kann. In diesem Fall wird, wie vorstehend beschrieben wurde, jedem der den Scheitelpunkt 1,2,5 mit anderen Scheitelpunkten verbindenden Ränder das Bewertungsmaß minus unendlich (-∞) gegeben, um diese Tatsache auszudrücken. In diesem Fall sind die einzigen Scheitelpunkte, die weiter kombiniert werden können, die Scheitelpunkte 3 und 6.
Anhand Fig. 19 ist ersichtlich, daß das Verschmelzen der Scheitelpunkte 3 und 6 zu drei Scheitelpunkten führt, die den Scheitelpunkt 1,2,5, den Scheitelpunkt 4 und den Scheitelpunkt 3,6 aufweisen. Weil, wie vorstehend angegeben wurde, der Scheitelpunkt 1,2,5 eine Gruppe maximaler Größe aufweist, sind keine weiteren Kombinationen zulässig. Demgemäß wird jedem der Ränder, die vom Scheitelpunkt 1,2,5 ausgehen, das Bewertungsmaß -∞ gegeben, wodurch die Gruppierung der Daten abgeschlossen wird.
Wenngleich vorstehend bevorzugte Ausführungsformen der vorliegenden Erfindung beschrieben worden sind, ist vorgesehen, daß daran in Hinblick auf bestimmte Anwendungen zahlreiche Modifikationen vorgenommen werden können, ohne vom Schutzumfang der vorliegenden Erfindung abzuweichen. Die vorliegende Erfindung ist beispielsweise nicht auf die Gruppierung von Karten-Strukturmerkmalen beschränkt, sondern sie kann auch zum Gruppieren beliebiger Gegebenheiten verwendet werden, die in zwei oder mehr Dimensionen verteilt sind, wie beispielsweise Komponenten auf einer gedruckten Leiterplatte, Knoten in einer Graphik, Personen mit gemeinsamen Interessen, Sterne im Weltraum usw. Die beschriebenen Ausführungsformen sollen dementsprechend nur als die vorliegende Erfindung erläuternd angesehen werden, und ihr Schutzumfang sollte nicht als darauf beschränkt angesehen werden, sondern anhand der nachstehend angegebenen Ansprüche bestimmt werden.

Claims

1. Verfahren zum Gruppieren mehrdimensionaler, verwandter Daten in einer Computerdatenbank, die einen Satz von Datenblöcken aufweist, wobei jeder Datenblock Informationen über ein interessierendes Objekt speichert, wobei das Verfahren die folgenden Schritte aufweist:

a) Einrichten eines Scheitelpunkts (31-35) für jedes interessierende Objekt in der Computerdatenbank, um eine graphische Darstellung bereitzustellen, die mehrere in einer zweidimensionalen Fläche beabstandete Scheitelpunkte aufweist,

b) Identifizieren von Strukturmerkmalen, die Bereichen und Liniensegmenten in der zweidimensionalen Fläche entsprechen,

c) Erzeugen eines getrennten Scheitelpunkts für jeden identifizierten Bereich und jedes identifizierte Liniensegment,

d) Erzeugen eines Rands (40-43) von dem Scheitelpunkt, der jedem identifizierten Bereich entspricht, zu dem Scheitelpunkt, der jedem den Bereich begrenzenden identifizierten Liniensegment entspricht,

e) Berechnen eines Bewertungsmaßes für jeden der die Scheitelpunkte verbindenden Ränder (40-43) nach einer vorgegebenen Formel auf einem Computer,

f) Auswählen der zwei Scheitelpunkte, die mit dem Rand verbunden sind, der das beste Bewertungsmaß aufweist,

g) Kombinieren der zwei Scheitelpunkte durch Kombinieren der von den zwei Scheitelpunkten dargestellten Gruppen,

h) Erzeugen eines neuen verschmolzenen Scheitelpunkts (60-64) und von Rändern (54-58, 69-70) zwischen dem neuen Scheitelpunkt und den zuvor mit den verschmolzenen Scheitelpunkten verbundenen Scheitelpunkten und Berechnen eines neuen Bewertungsmaßes für die neuen Ränder auf einem Computer,

i) Wiederholen der Schritte (f) bis (h), bis eine vorgegebene Endbedingung erreicht wurde, und

j) Speichern der restlichen Gruppen in einem von einem Computer lesbaren Medium.

2. Verfahren nach Anspruch 1, wobei der Schritt des Berechnens eines Bewertungsmaßes den Schritt des Zuweisens eines Bewertungsmaßes aufweist, das

i) gleich der Fläche eines die erste Gruppe begrenzenden Begrenzungskastens zuzüglich der Fläche eines die zweite Gruppe begrenzenden Begrenzungskastens minus der Fläche eines die kombinierten Gruppen begrenzenden Begrenzungskastens ist, falls die Größe des Datenblocks der kombinierten Gruppe unterhalb einer vorgegebenen maximalen Größe liegt, oder

ii) gleich negativ unendlich (-∞) ist, falls die Größe des Datenblocks der kombinierten Gruppe gleich der vorgegebenen maximalen Größe ist oder diese übersteigt.

3. Verfahren nach Anspruch 1 oder 2, wobei der Schritt des Berechnens eines Bewertungsmaßes für die in Schritt (h) erzeugten Ränder den Schritt des Zuweisens eines Bewertungsmaßes aufweist, das gleich der Summe der Bewertungsmaße der Ränder ist, die ein neu erzeugter Rand ersetzt.

4. Verfahren nach Anspruch 1, 2 oder 3, mit dem weiteren Schritt des Erzeugens und Aufrechterhaltens einer Liste von Scheitelpunkten, in der für jeden Scheitelpunkt das Bewertungsmaß eines mit diesem Scheitelpunkt verbundenen besten Rands und der andere Scheitelpunkt, mit dem dieser beste Rand verbunden ist, angeführt sind.

5. Verfahren nach Anspruch 4, wobei der Schritt des Erzeugens und Aufrechterhaltens einer Liste von Scheitelpunkten den Schritt des Sortierens der Liste nach dem Bewertungsmaß aufweist.

6. Verfahren nach einem der Ansprüche 1 bis 5, welches weiter die Schritte des Wiederholens der Schritte (e) bis (i) , bis eine vorgegebene Endbedingung erreicht wurde, aufweist.

7. Verfahren nach Anspruch 6, wobei jede Wiederholung der Schritte (e) und (h) die Verwendung eines anderen Verfahrens zum Versehen der Ränder mit Bewertungsmaßen aufweist.

8. Verfahren nach Anspruch 7, wobei der Schritt (i) bei jeder Wiederholung der Schritte (e) bis (i) eine andere und größere vorgegebene Endbedingung aufweist.

9. Verfahren nach einem der vorhergehenden Ansprüche, welches weiter den Schritt des Identifizierens von Paaren von Scheitelpunkten aufweist, die noch nicht durch einen Rand verbunden sind und deren entsprechenden interessierenden Objekte zusammen gruppiert werden sollten, und des Verbindens jedes derartigen Paars von Scheitelpunkten mit einem Rand während jeder Wiederholung der Schritte (f) bis (h) aufweist.

10. Verfahren nach einem der Ansprüche 1 bis 9, wobei die gruppierten Daten geographische Kartendaten sind.

11. Verfahren nach einem der vorhergehenden Ansprüche, welches weiter den Schritt des Unterdrückens von Scheitelpunkten und zugeordneten Rändern aufweist, die Objekte darstellen, für die es nicht gewünscht ist, Daten in der Datenbank aufrechtzuerhalten, um mehrere Scheitelpunkte zu belassen, die Strukturmerkmale darstellen, für die Daten in der Datenbank vorhanden sind.

12. Verfahren nach einem der vorhergehenden Ansprüche, wobei die vorgegebene Endbedingung des Schritts (i) erreicht wird, wenn ein weiteres Kombinieren von Gruppen eine vordefinierte Grenze überschreiten würde.