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

  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. 
  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. 
Pahýl
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.
Stromové datové struktury
Vyhledávací stromy
(dynamické množiny/ asociativní pole)
2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (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.)