Prostorový index

Prostorový index je speciálním typem indexu, který slouží k indexaci prostorových dat. Kromě běžných funkcí, jako je optimalizace vyhledávání aj., slouží též k optimalizaci operace prostorového spojení.

Typy prostorových indexů

Prostorové indexy lze dělit na dva základní typy podle způsobu práce s výchozím prostorem P, ve kterém se nacházejí indexované objekty:^[1]^[2]

transformační přístup
- snížení dimenze
- zvýšení dimenze
rozdělení na podprostory
- nepřekrývající se oblasti
- pokrývající oblasti

Typickým zástupcem transformačního přístupu je linearizace, při které dojde ke snížení dimenze prostoru na 1.^[3] Mezi indexační struktury, které rozdělují prostor na podprostory, patří zejména dlaždicový index, a dále různé stromové struktury, např. k-d-stromy, čtyřstromy, R-stromy a jejich modifikace.

Reference

↑ JANEČKA, Karel. Prostorové datové struktury a jejich použití k indexaci prostorových objektu [online]. Západočeská univerzita v Plzni [cit. 2016-01-22]. Dostupné online.
↑ POKORNÝ, Jaroslav. Prostorové datové struktury a jejich použití pro indexaci prostorových objektů. In: Proceedings of GIS Ostrava 2000. Ostrava: [s.n.], 2000. Dostupné online.
↑ ŽEMLIČKA, Michal. Prostorové databáze [online]. Univerzita Karlova, rev. 2005-02-22 [cit. 2016-01-22]. Kapitola Prostorové databáze: Organizace prostoru. Dostupné v archivu pořízeném dne 2009-03-27.

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[janecka-pdb3-1] JANEČKA, Karel. Prostorové datové struktury a jejich použití k indexaci prostorových objektu [online]. Západočeská univerzita v Plzni [cit. 2016-01-22]. Dostupné online.

[gis_ostrava2000-2] POKORNÝ, Jaroslav. Prostorové datové struktury a jejich použití pro indexaci prostorových objektů. In: Proceedings of GIS Ostrava 2000. Ostrava: [s.n.], 2000. Dostupné online.

[3] ŽEMLIČKA, Michal. Prostorové databáze [online]. Univerzita Karlova, rev. 2005-02-22 [cit. 2016-01-22]. Kapitola Prostorové databáze: Organizace prostoru. Dostupné v archivu pořízeném dne 2009-03-27.

[1]

[2]

[3]

Stromové datové struktury

Vyhledávací stromy (dynamické množiny/ asociativní pole)	2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • B^x • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])

Haldy	Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá

Trie	Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast

Prostorové indexační stromy	Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X

Jiné stromy	Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)

Kategorie:Stromy (dat. strukt.)