Effiziente Textsuche in OpenStreetMap-Daten auf mobilen Geräten

Abstract

In dieser Arbeit sollen mehrere Möglichkeiten zur effizienten Textsuche in OpenStreetMap- Daten vorgestellt werden. Das Ziel ist ein Androidprogramm, mit welchem nach Zeichenketten in OpenStreetMap-Daten gesucht werden kann. Zur effizienten Suche bieten sich hier Hash-Verfahren und vor allem Baumstrukturen, wie Patrica- oder HAT-Tries, an. Für die Suche auf Mobilgeräten kann eine Datenstruktur verwendet werden, die nur Lesezugriffe, jedoch keine Veränderungen ermöglicht. Neben einem auf minimalen Hash-Funktionen basierenden Verfahren wurde ein Patricia-Trie in serialisierter Form in einem Byte-Feld abgelegt. Die Datenstruktur ermöglicht so eine Suche nach Präfixen in O (k ), mit k der Länge des gesuchten Präfixes, bei guter Cache-Nutzung. Die Baumstruktur erwies sich dabei dem Hash-Verfahren überlegen. Eine potentielle Erweiterung, die Schnittoperationen und die Suche nach mehreren Zeichenketten ermöglicht, soll im Abschnitt Ausblick kurz umrissen werden.