The ``crowd'' has become a very important geospatial data provider. Subsumed under the term Volunteered Geographic Information (VGI), non-expert users have been providing a wealth of quantitative geospatial data online. With spatial reasoning being a basic form of human cognition, narratives expressing geospatial experiences, e.g., travel blogs, would provide an even bigger source of geospatial data. Textual narratives typically contain qualitative data in the form of objects and spatial relationships. The scope of this work is (i) to extract these relationships from user-generated texts, (ii) to quantify them and (iii) to reason about object locations based only on this qualitative data. We use information extraction methods to identify toponyms and spatial relationships and we formulate a quantitative approach based on distance and orientation features to represent the latter. Positional probability distributions for spatial relationships are determined by means of a greedy Expectation Maximization-based (EM) algorithm. These estimates are then used to ``triangulate'' the positions of unknown object locations. Experiments using a text corpus harvested from travel blog sites establish the considerable location estimation accuracy of the proposed approach on synthetic and real world scenarios.
Protecting Against Velocity-based, Proximity-based and External Event Attacks in Location-Centric Social Networks
This paper presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too large for internal memory, even over 100000x100000 points. It subdivides the terrain into tiles, that are stored compressed on disk and then paged into memory with a custom cache data structure and LRU algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TiledVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all the terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TiledVS is very fast, for instance, processing a 104000x104000 terrain on a modest computer with only 512MB of RAM took only 1.5 hours. On large datasets, TiledVS was several times faster than competing algorithms such as are in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. An earlier version of this algorithm was published in a 4-page ACM SIGSPATIAL 2012 conference paper. This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons.