O projektu

Projekt OpenStreetMap.org byl inspirován úspěchem projektu Wikipedie, kdy množství jednotlivců bylo často i po malých příspěvcích a bez direktivního řízení a plánu schopné vytvořit ucelené dílo srovnatelné s největšími placenými encyklopediemi světa. Projekt OpenStreetMap umožňuje každému zájemci přispět k tvorbě mapy světa. Přitom data jsou publikována pod licencí ODbL, která je umožňuje využívat i pro komerční účely a kombinovat mapový podklad i s vrstvami, které není povoleno kopírovat. V podmínkách použití je pouze vyžadováno, aby byl každý uživatel mapy (papírové nebo mapového portálu) informován o tom, že data (určitá vrstva) pochází z projektu OpenStreetMap.org a dále, pokud je ve vrstvě mapy získané z projektu provedena úprava/oprava, musí být příslušná změna poskytnutá i do původního otevřeného projektu.

Motivace úkolu

Hlavní motivací této úlohy je seznámit studenty i s jinými otevřenými projekty, než je open source software. Přitom úloha umožňuje využít programátorské dovednosti a libovolné technologie a vyzkoušet je při práci s velkými objemy dat. S výhodou lze použít otevřených knihoven a nástrojů, které komunita vytvořila. Práce se středně velkým objemem dat také studentům přinese zkušenost s tím, jak se jejich oblíbené/jimi vybrané technologie se zpracováním dat vyrovnají.

Zadání úkolu

Vytvořte aplikaci, která dokáže spočítat součet délek všech úseků určitého typu liniových staveb, vodních toků nebo železnic na území České republiky v databázi OpenStreetMap uložené k určitému datu na disk počítače.

Data vztahující se k území České republiky naleznete uložená v adresáři /opt/osm/data síťové instalace systému GNU/Linux na počítačích v laboratoři. Snímek dat je k dispozici ve dvou formátech. Jedná se o soubory:

• czech-republic-snapshot.osm.bz2 – data v textovém formátu XML, která jsou poté komprimovaná kompresí BZip2 (900MB, 13 GB před kompresí)
• czech-republic-snapshot.osm.pbf – data v binárním formátu Protocol Buffers (552MB)

Vytvořená aplikace musí umožnit zadat typ hledaných elementů omezených kombinací jednoho klíče a jeho požadované hodnoty. Například pro vyhledání všech úseků dálnic bude vstupním parametrem klíč highway a jeho hodnota motorway. Pro délku vodních toků waterway=river, atd. Výstupem programu bude součet délek všech úseků daného typu.

Program může parametry přijímat na příkazovém řádku nebo s využitím grafického rozhraní. Výstup může být také pouze číslo vytisknuté na terminál.

Požadavkem je, že hodnota bude spočtena z předložených dat. S daty je možné pracovat a program předvést i na svém počítači nebo vzdáleném systému. K výpočtu však nesmí být použité online služby nad aktuálními daty projektu OpneStreetMap.org. Odůvodnění:

1. docházelo by ke zbytečné zátěži komunitních serverů,
2. výsledky pro novější, průběžně editovaná data nebudou odpovídat referenčním hodnotám,
3. cílem je si vyzkoušet práci s velkými daty a ne jen zasílat dotazy do cizích služeb.

Pokud budete ke zpracování používat infrastrukturu laboratoří, nekopírujte prosím data ani meziprodukty zpracování do svého domovského adresáře. Došlo by k překročení limitů přidělené kapacity na uživatele. Pokud budete potřebovat dočasné výsledky ukládat do souboru, použijte adresář /tmp. Do něj uložená data se ukládají pouze do paměti RAM na dané stanici. Velikost je pak omezena přibližně na polovinu fyzické paměti stanice.

Podpůrné informace pro řešení úkolu

Struktura dat

Struktura dat projektu OpenStreetMap.org je ve své podstatě velmi jednoduchá. Svět je popsaný s využitím následujících třech elementů:

• uzel (node) – definuje bod v prostoru (jeho zeměpisnou délku a šířku)
• cesta (way) – popisuje liniové objekty a hranice ploch/oblastí (cesta přímo nedefinuje polohu, pouze se odkazuje na uzly, kterými prochází)
• relace (relation) – seskupuje uzly a cesty podle určitého kritéria/příslušnosti.

Ke každému elementu pak mohou být přiřazeny vlastnosti. Vlastnosti se definují dvojicemi klíč, hodnota. Přitom pořadí klíčů nenese žádnou informaci, není součástí databáze. Často se vlastnosti přiřazené k relaci týkají i všech do ní zahrnutých cest a bodů.

Pro jednoduchost nebude brán na tento přenos vlastností zřetel. Úkolem je opravdu pouze vyhledat všechny cesty, které mají přímo nastavený daný klíč s požadovanou hodnotou. Délka se pak spočítá z rozdílů poloh všech bodů v rámci daného úseku.

Výpočet vzdálenosti

K výpočtu rozdílu poloh, které jsou v databázi uloženy ve formě zeměpisných souřadnic, je potřeba provést přepočet na vzdálenost mezi body pro nejkratší spojnici po zemském povrchu. Pro tento výpočet použijte některou vhodnou knihovnu.

Protocol Buffers

Formát Protocol Buffers byl vytvořený firmou Google jako základní mechanizmus pro předávání dat a požadavků mezi jejími službami. Jedná se o formát, který umožňuje serializovat datové struktury existující v paměti nějakého procesu do binární podoby (sekvence bytů), která je nezávislá na konkrétní procesorové platformě a tak umožňuje data přeposlat nebo načíst ze souboru jinému procesu (programu) a zde je rozbalit do jím používaných datových struktur. Pro efektivní uložení dat formát přímo s daty nepřenáší pojmenování a popis struktury dat. Proto, aby data mohla být uložena a poté správně interpretovaná musí obě strany znát schéma/strukturu datového modelu.

Více o vlastním formátu na Wikipedii.

Použití formátu Protocol Bufferes pro data projektu OpenSteerMap.org je popsané na wiki projektu OpenSteerMap.

Strojově čitelné schéma popisující konkrétní strukturu dat OSM je spravované v rámci projektu OSM-binary na serveru GitHub.

XML

K dispozici jsou i data ve formátu XML. Zpracování/načtení přibližně 20× většího objemu dat a převod z textové reprezentace do interní reprezentace může práci s daty v tomto formátu výrazně prodloužit. Limit pro získání výsledku od zadání požadavku během cvičení bude omezený na cca půl hodiny.