Datenstruktur für Netze gesucht

Status
Nicht offen für weitere Antworten.
N

Neo.P5

Gast
Hallo,

ich suche eine Datenstruktur um ein Netz von gleichrangigen Objekten darzustellen.
Als Beispiel das Netz der Webseiten des Internets.

Jedes Objekt kann Referenzen auf andere (gleiche) Objekte haben. Diese haben wiederum Referenzen auf andere (gleiche) Objekte und/oder auf das vorherige Element zurück.

Zum Beispiel: Eine Webseite hat eine Referenz auf eine andere Seite. Diese wiederum kann wieder auf mehrere weitere Seiten zeigen. (natürlich auch wieder zurück). Andere Webseiten verweisen auchauf die erste Webseite, usw...


Mein Problem besteht nun darin, dass ich nicht einfach eine Baumstruktur verwenden kann, da es ja keinen Wurzelknoten gibt und somit auch keine Hirarchie der Knoten untereinander (eben ein Netz :).

Zudem habe ich noch die Anforderung, dass diese Struktur u.U. sehr sehr viele Elemente erfassen muss, schnell durchsucht werden sollte und auf eine Datenbank abgebildet werden soll (vorzugsweise mit Hibernate).

Ich hoffe ihr habt eine Idee oder Ansatz für mich...

viele Grüße...

Neo
 
N

Neo.P5

Gast
Du meinst sowas wie..


Code:
public class IndexNode {

    private Domain domain;

    private ArrayList<IndexNode> externalReferenzes = new ArrayList< IndexNode >();

    /**
     * Konstruktor
     */
    public QSearchIndexNode(Domain domain) {
        this.domain = domain;
    }

}

Da hab ich irgendwie ein Problem mit dem Einfügen. Jedes Objekt darf nur einmal vorkommen, obwohl mehrere verschiedene Knoten darauf zeigen können und es selbst wiederum auf mehrere Objekte zeigt.
Ich bekomme das mit der Datenkonsitenz nicht hin. Außerdem weis ich nicht wie ich die Suche gestalten soll (ja: rekursiv).
Allerdings komme ich bei rekursiver Suche niemals zum Ende; es sein denn ich merke mir wo ich schon war.
Dann bekomme ich aber das Problem, dass die Datenstruktur mehrere Millionen Einträge enthalten kann und mehrere Suchen in der Sekunde durchgeführt werden müssen.

Ich dachte also an etwas optimierteres...

Trotzdem vielen Dank schonmal...

Ein Guter Anfang ist der erste Schritt des Weges...


Neo
 
N

Neo.P5

Gast
Danke auch dir.

Der Tipp mit den gerichteten Graphen ist super. Da hab ich natürlich mal wieder nicht dran gedacht.
Leider hab ich sowas bis jetzt noch nicht implementiert. Hat da evtl. jemand Praxiserfahrung mit, oder ein Beispiel?

Weiß evtl. jemand wie sich eine Suche auf so einem Graphen in der Praxis verhällt bzw. wie schnell so was ist?

vielen vielen Dank für den nützlichen Hinweis...

Gruß Neo
 

0x7F800000

Top Contributor
1) Was heißt "problem mit dem Einfügen"? Wenn du alle Knoten erstmal in irgendeiner HashTable abspeicherst, und dann mit irgendsoeiner methode wie "addConnections(Node[] nodes)" die gerichteten Kanten einfügst, dann hast du doch stets nur eine einzige lange Collection, in der alle Knoten genau einmal vorkommen, und die untereinander verbunden sind.

2) Was heißt "Suche auf einem Graphen"? Was willst du da "suchen"? Knoten? Wege zwischen den Knoten?
 
G

Guest

Gast
@Andrey: ich glaube du beziehst dich noch auf mein Beispiel mit der "stinknormale relation" (oder Irre ich mich?). Diese Idee wurde mittlerweile verworfen und durch den gerichteten Grafen ersetzt.

Suchen bedeutet in diesem Falle eine bestimmte Menge an Knoten zu ermitteln auf die ein bestimmtes Suchkriterium (z.B. Name des Knotens enthällt ein "A") zutrifft und diese Menge sortiert nach deren Trefferwahrscheinlichkeit zurück zu geben.

Die Kanten unter den Knoten sind für die Suche vorerst nur zweitrangig; die Beziehung der Knoten untereinander wird später in einem anderen Programmschritt ausgewertet und wird für das Ranking der Knoten/Suchergebnisse verwendet (Wie viele ausgehende/Eingehende verbindungen,...).

Viele Grüße Neo...
 

0x7F800000

Top Contributor
Anonymous hat gesagt.:
@Andrey: ich glaube du beziehst dich noch auf mein Beispiel mit der "stinknormale relation" (oder Irre ich mich?). Diese Idee wurde mittlerweile verworfen und durch den gerichteten Grafen ersetzt.
Aaaaha^^ klingt einleuchtend. Würdest du aber vielleicht doch nochmal erläutern, was deiner meinung nach der Unterschied zwischen einem "gerichteten Graph" und einer "stinknormalen Relation" sein soll? ???:L

Suchen bedeutet in diesem Falle eine bestimmte Menge an Knoten zu ermitteln auf die ein bestimmtes Suchkriterium (z.B. Name des Knotens enthällt ein "A") zutrifft und diese Menge sortiert nach deren Trefferwahrscheinlichkeit zurück zu geben.
Nja, für solche Kriterien ist es erstmal egal, ob das jetzt ein Teil eines Netzes ist oder sonstwas. Im schlimmsten Fall musst du einfach alle abgespeicherten Knoten durchgehen, schauen ob die das Kriterium erfüllen.
Etwas schöner wäre es, wenn die Kriterien nicht zu allgemein wären, sodass du die Knoten schon vorher einmal ordnen könntest, um später nicht alle Knoten durchgehen zu müssen. Irgendeine Sortierung wäre ganz toll.
 
N

Neo.P5

Gast
ja eine sortierung wäre sinnvoll. da hst du recht.

ich habe mich jetzt dazu entschluss lucene von apache zu verwenden um einen entsprechenden suchindex aufzubauen. die reladion wollte ich versuchen mit der hinterlegungn von id´s zu berücksichtigen...

ich meld mich nochmal wenn ich soweit bin.

p.s.: bitte entschlusdigt, dass ich so lange nicht geantwortet habe. ich war leider verhindert...
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Datenstruktur für eine Map erstellen Allgemeine Java-Themen 2
B Suche passende Datenstruktur für 2 Einträge Allgemeine Java-Themen 19
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
S Welche Datenstruktur für verschiedene Sprachen sinnvoll? Allgemeine Java-Themen 2
T Datenstruktur für großes Netz Allgemeine Java-Themen 2
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
T Datenstruktur für Straße ! Allgemeine Java-Themen 5
M Eigene Datenstruktur um eine Menge zu speichern Allgemeine Java-Themen 3
Kirby.exe Union Find Datenstruktur Allgemeine Java-Themen 27
U Klassen Komplexe Datenstruktur in Java Allgemeine Java-Themen 4
B Suche geeignete Datenstruktur Allgemeine Java-Themen 5
ruutaiokwu datenstruktur welche sich "im kreis" dreht Allgemeine Java-Themen 26
P Große Datenstruktur im Speicher halten Allgemeine Java-Themen 13
G Welche Datenstruktur? Allgemeine Java-Themen 19
R Collections Datenstruktur gesucht Allgemeine Java-Themen 12
D Datenstruktur .. BlockingQueue (LIFO) Allgemeine Java-Themen 3
P Suche Datenstruktur Allgemeine Java-Themen 2
ruutaiokwu schnelle datenstruktur... Allgemeine Java-Themen 13
S Baumstruktur/Datenstruktur in Datei speichern Allgemeine Java-Themen 23
D Datenstruktur Allgemeine Java-Themen 2
B Datenstruktur: Liste Allgemeine Java-Themen 5
A Thread sichere Datenstruktur Allgemeine Java-Themen 5
J Arrayähnliche Datenstruktur Allgemeine Java-Themen 4
B Script Problem "Dynamische Datenstruktur" Allgemeine Java-Themen 13
S Frage zum Design der Datenstruktur Allgemeine Java-Themen 10
G Datenstruktur: LISTEN Allgemeine Java-Themen 7
D Suche nach passender Datenstruktur Allgemeine Java-Themen 4
G Daten von Excel kopieren - sinnvolle Datenstruktur? Allgemeine Java-Themen 3
U eigene Datenstruktur ArrayList<String> nach Object [][ Allgemeine Java-Themen 2
F welche Datenstruktur? Allgemeine Java-Themen 9
F Welche Datenstruktur Allgemeine Java-Themen 2
T Datenstruktur gesucht Allgemeine Java-Themen 18
Z Welche Datenstruktur verwende ich h_ier bloss ? Allgemeine Java-Themen 14
G NullPointer. in einer Datenstruktur Allgemeine Java-Themen 2
S Welche Datenstruktur passt bei mir? Allgemeine Java-Themen 6
H Speicheverbrauch einer Datenstruktur ermitteln Allgemeine Java-Themen 29
S Suche geeignete Datenstruktur Allgemeine Java-Themen 27
D Welche Datenstruktur? Allgemeine Java-Themen 2
B Datenstruktur elegant zerlegen Allgemeine Java-Themen 6
G Datenstruktur gesucht: Allgemeine Java-Themen 3
A Datenstruktur und Sortierung Allgemeine Java-Themen 12
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
R 11 GB File lesen ohne zu extrahieren Filedaten Bereich für Bereich adressieren dann mit Multi-Thread id die DB importieren Allgemeine Java-Themen 3
G KeyListener für JTextField Allgemeine Java-Themen 5
webracer999 Library für Textsuche (z. B. include/exclude, and/or)? Allgemeine Java-Themen 5
I Module-Info für Jar erzeugen Allgemeine Java-Themen 7
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
B Simpler Eventlistener für Tastaturtaste bauen? Allgemeine Java-Themen 13
_user_q Eingegebenen Text Zeile für Zeile ausgeben lassen Allgemeine Java-Themen 11
E Key für TOTP Algorythmus(Google Authentificator) Allgemeine Java-Themen 0
S Formel für Sonnenwinkel in ein Programm überführen Allgemeine Java-Themen 11
M pfx-Zertifikat in Tomcat für SSL-Verschlüsselung nutzen Allgemeine Java-Themen 14
R Best Practice Erfahrungswerte für eine Migration von JSF nach Angular (oder anderes JS-Framework) Allgemeine Java-Themen 1
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
jhCDtGVjcZGcfzug Klassen Was genau passiert hier? Kann mir das jemand bitte Zeile für Zeile erklären? Allgemeine Java-Themen 1
rosima26 Bester Sortieralgorithmus für kurze Arrays Allgemeine Java-Themen 40
S Mit Methoden kann man definieren für was <T> steht. Geht das auch irgendwie für Variablen? Allgemeine Java-Themen 12
MangoTango Operatoren while-Schleife für Potenz Allgemeine Java-Themen 3
B Lottospiel, genug Reihen tippen für 3 Richtige (Spaß mit Arrays)? Allgemeine Java-Themen 46
B Mit welchen Datentypen und Strukturierung am Besten dutzende Baccaratspiele Shcritt für Schritt durchsimulieren? Allgemeine Java-Themen 26
D Klassendesign für einen Pascal Interpreter Allgemeine Java-Themen 6
I OCR Library für Belegerkennung Allgemeine Java-Themen 7
farah GetterMathod für Farbkanäle Allgemeine Java-Themen 6
B Welcher Datentyp für sehr große Zahlenbereiche? Allgemeine Java-Themen 1
S Webservices für binäre Daten? Allgemeine Java-Themen 5
G Licence-Header für InHouse entwickelten Source Allgemeine Java-Themen 8
M Schleife für einen TicTacToe Computer Allgemeine Java-Themen 5
O git ignore für Intellji braucht es die .idea Dateien? Allgemeine Java-Themen 8
F Java Script für das Vorhaben das richtige? Allgemeine Java-Themen 9
M wiviel Java muss ich für die Berufswelt können ? Allgemeine Java-Themen 5
Robertop Datumsformat für GB ab Java 16 Allgemeine Java-Themen 1
Thallius Verschiedene entities für gleichen Code…. Allgemeine Java-Themen 8
OnDemand Zentrale "Drehscheibe" für verschiedene APIs Allgemeine Java-Themen 14
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
F Streams als Alternative für dieses Problem ? Allgemeine Java-Themen 15
D SHA-3 für Java-version 1.8 Allgemeine Java-Themen 1
N Validator für einen SQL-Befehl Allgemeine Java-Themen 22
Muatasem Hammud Erstellung von Testdaten für Arrays Allgemeine Java-Themen 6
B Logikfehlersuche, das perfekte Lottosystem für 3 Richtige mit Arraylists? Allgemeine Java-Themen 61
G Methoden für die Zukunft sinnvoll? Allgemeine Java-Themen 4
M API für PLZ Umkreissuche Allgemeine Java-Themen 3
1Spinne JDK 8 für Eclipse installieren Allgemeine Java-Themen 5
Tobero Meine Funktion für das beinhalten eines Punktes in einem Kreis funktioniert nicht Allgemeine Java-Themen 5
L Methoden Parser für gängige Datumsformate? Allgemeine Java-Themen 1
H Interface PluginSystem ClassNotFound exception für library Klassen Allgemeine Java-Themen 10
N relativier Pfad für sqlite-Datenbank in Gradle/IntelliJ Allgemeine Java-Themen 2
buchfrau Anagram für beliebiges Wort Allgemeine Java-Themen 2
TonioTec Api für Datenaustausch zwischen Client und Server Allgemeine Java-Themen 0
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
Kirby.exe Distanz Map für die Distanztransformation erstellen Allgemeine Java-Themen 1
F PI Regler für Heizung Allgemeine Java-Themen 7
8u3631984 Generelle Log4j.xml für alle Module Allgemeine Java-Themen 5
M Wie übergebe ich den Zähler für die Anzahl Rekursionsschritte korrekt? Allgemeine Java-Themen 2
B Login für User, der im Hintergrund Schedules ausführt Allgemeine Java-Themen 16
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11
N fixed-keyword von C# für Java Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben