Jelen szakdolgozatban egy új, többdimenziós pontokat tároló adatstruktúra definícióját, implementációját és kísérleti úton történő elemzését mutatom be. Ezt az adatstruktúrát q-kd fának neveztem el.

A dolgozat első része háttér információkat tartalmaz az asszociatív lekérdezési problémáról és két ismert többdimenziós adatstruktúráról: a k-d fáról és a quad-fáról. (Ez utóbbit négyfának, vagy négyágú fának is említi a magyar szakirodalom.) Ez utóbbiak speciális esetei az új adatstruktúrának. Ezt követi a q-kd fák definíciója és egy javaslat két különböző faépítési heurisztikára: az úgynevezett Split Tendency-re és az úgynevezett Prob-of-1-ra. Az ezek segítségével épített fákat kvázi-optimális q-kd fáknak és véletlenül hasított q-kd fáknak nevezem.

Ezek után a fejlesztési módszertanát mutatom be egy olyan szoftvernek, melynek segítségével kísérleti úton elemezhető az új adatstruktúra memóriafoglalási és futtatási időbeli hatékonysága. A szoftverben két fajta q-kd fát implementáltam, a véletlen k-d fával és a véletlen quad-fával egyetemben.

A kísérleti eredmények azt mutatják, hogy a tesztelt esetekben egyrészt a k-d fák sokkal hatékonyabbak a quad-fáknál a memóriafoglalást tekintve, másrészt a quad-fák sokkal hatékonyabbak a k-d fáknál az IPL (Internal Path Length, belső úthossz) tekintetében.

Ezek a kísérletek azt mutatják, hogy a mi q-kd fa változataink a quad-fák és a k-d fák között vannak a memóriafoglalás és az IPL tekintetében, továbbá, hogy megfelelő paraméterbeállításokkal lehetséges a rendelkezésre álló memóriaterület és futtatási idő megkötésekhez alkalmazkodva q-kd fákat építeni. Összességében megállapíthatjuk, hogy a q-kd fa egy új, ígéretes adatstruktúra.