Indexstruktur für höherdimensionale objekte

Hallo zusammen,

ich habe datenobjekte, die aus intervallen und punkten bestehen. ein objekt kann also z.B. wie folgt aufgebaut sein:
höhe: 1-3cm
breite: 2-6cm
ort: panama
gewicht: 2g

nun möchte ich suchanfragen bestehend aus punkten stellen, also z.B. "gib mir alle objekte mit höhe=2cm, breite=3cm, ort=panama, gewicht=2g".

Welche datenstruktur ist hierfür am besten geeignet (für mich hauptsächlich nur suchanfragen wichtig)? gibt es evtl. sogar schon fertige implementierung (c++ oder java)?

Danke im Voraus!

Ben04

Was willst du genau machen?

Was können deine 4 Schlüssel für Werte annehmen?
Was ist bei deiner Anfrage gegeben und was soll bestimmt werden?
Werden oft Datensätze hinzugefügt oder wird die Struktur einmal initialisiert und dann kommen nur noch Anfragen?

Wenn es nur darum geht fest zu stellen ob ein Punkt in einer Menge enthalten ist dann ist es einfach. Entweder eine Hashfunktion definieren oder die Punkte lexikographisch ordnen.

beispiel für 3 objekte mit jeweils 4 dimensionen (3 intervalle und 1 punkt):
objekt1: [1-3], [5-6], 1, [2-4]
objekt2: [2-4], [5-8], 1, [3-6]
objekt3: [1-3], [6-8], 5, [3-6]
...

nun stelle ich eine suchanfrage: (2, 5, 1, 3)
ergebnis: objekt1 und objekt2.

in meinem programm habe ich ca. 100 objekte mit ca. 10 dimensionen und es werden mehrere millionen solcher suchanfragen gestellt, deshalb muss das möglichst effizient sein (am besten wie bei binären bäumen in der größenordnung O(logn)).

welche Datenstruktur eignet sich dafür am besten? interval trees sollen z.b. nur für eine dimension funktionen...

Ben04 schrieb:

Wenn es nur darum geht fest zu stellen ob ein Punkt in einer Menge enthalten ist dann ist es einfach. Entweder eine Hashfunktion definieren oder die Punkte lexikographisch ordnen.

so einfach ist das leider nicht

nman

Vielleicht hilft Dir sowas weiter:
http://en.wikipedia.org/wiki/R-tree

volkard

ein beliebter trick für zwei dimensionen ist, daß man map<ersteDim,map<zweiteDim,data>> macht. geht natürlich auch mit mehr dimensionen. und kannst natürlich auch intervallbäume verschachteln.
aber irgendwie hab ich da ein schlechtes gefühl sowas würde ich bei zehntausenden von objekten anstrengen. aber bei nur 100?
wenn die höhe nur werte zwischwen 0 und 1000 annehmen kann, die breite auch und das gewicht nur werte zwischen 0 und 10000. dann würde ich bei nur 100 objekten vielleicht für jede dimension die möglichen ergebnisse auf eine suchanfrage als fixes sortiertes array of data* speichern und als 4-dimensionale suchanfrage dann nur 4 sortierten arrays in ein ergebnissarray mergen (mergen im sinne von mergen im merge-sort).

Einfach mal mit ner kleinen Datenbank veruschen z.B. http://hsqldb.org/ , die macht viel im Speicher. Bei 100 Objekten wahrscheinlich etwas übertrieben, aber vielleicht werden ja noch mehr.

nman schrieb:

Vielleicht hilft Dir sowas weiter:
http://en.wikipedia.org/wiki/R-tree

danke!
so ein r-tree schein die richtige struktur zu sein.

kennt jemand von euch fertige implementierungen in java?
die meisten, die ich gefunden habe, sind für viele objekte ausgelegt und bieten gleich die option mit die ganzen objekte auf platte auszulagern.

lediglich http://jsi.sourceforge.net/ scheint das nicht zu machen, kann aber nur 2-dimensionale objekte. allerdings könnte man das relativ einfach auf mehrere dimensionen anpassen, man müsste aber hierfür den source ändern.
die lib steht unter der LGPL. kann ich das einfach machen? würde das in einer kommerziellen anwendung verwenden....

Ben04

indexer schrieb:

in meinem programm habe ich ca. 100 objekte mit ca. 10 dimensionen und es werden mehrere millionen solcher suchanfragen gestellt, deshalb muss das möglichst effizient sein (am besten wie bei binären bäumen in der größenordnung O(logn)).

Bei nur 100 Objekten ist die Sache klar: nach Punkt in einem Array sortieren und dann per binäre Suche nach dem Suchen. Die restlichen Bedingungen dann sequentiell abprüfen. Wenn die möglichen Punkte auch nur wenige Werte annehmen können, dann kannst du alle möglichen Anfragen nach Punkten in einer Tabelle vorberechnen. Bei komplexeren Punkten kann eine Hashfunktion was bringen.

Von Bäumen kann ich nur abraten. Die sind schwer zu implementieren und es ist noch viel schwerer dies effizient zu tun und selbst dann schneiden die bei kleinen Datenmengen schlecht ab.

Wenn es wirklich nur um 100 Objekte geht und auch nicht tausende solcher Abfrage pro Sekunde gemacht werden, sondern nur ein User was eingibt und dann wird einmal gesucht, dann mach eine for-Schleife die alle Objekte einmal durchgeht und jeweils die 10 if-Abfragen macht. 100 mal 10 if macht dir heute jeder normale Rechner in ein paar Millisekunden.