Analyzing time series data is crucial for many applications. In particular, subsequence search refers to finding subsequences within an input time series T that are similar to a query sequence Q. Existing subsequence search approaches typically employ Euclidean distance or Dynamic Time Warping as similarity measures and address range queries. In this paper, we focus on Chebyshev distance, which is the largest difference between each individual pair of points across the entire length of two compared subsequences. We call such similar pairstwins. We first show how existing time series indices can be extended to perform twin subsequence search. Then, we introduce TS-Index, a novel index tailored to the computation of twin subsequence search queries. Moreover, given that specifying a distance threshold is often not straightforward, we show how TS-Index can also be used to evaluate kNN queries. Our extensive experimental evaluation compares these approaches using real time series datasets. The results demonstrate that TS-Index can retrieve twin subsequences faster than all other methods under various conditions.

Given a collection of geospatial points of different types, mixture-based best region search aims at discovering spatial regions exhibiting either very high or very low mixture with respect to the types of enclosed points. Existing works detect fixed-shape regions, such as circles or rectangles, thus often missing interesting regions occurring in real-world data that may have arbitrary shapes. In this paper, we formulate the problem of mixture-based best region search for arbitrarily shaped regions, introducing certain desired properties to ensure their cohesiveness and completeness. Since computing exact solutions to this problem has exponential cost with respect to the number of points, we propose anytime algorithms that efficiently search the space of candidate solutions to produce high-scoring regions under any given time budget. Our experiments on several real-world datasets show that our algorithms can produce high-quality results even within tight time constraints.

In the maritime domain, vessels typically maintain straight, predictable routes at open sea, except in the rare cases of adverse weather conditions, accidents and traffic restrictions. Consequently, large amounts of streaming positional updates from vessels can hardly contribute additional knowledge about their actual motion patterns. We have been developing a system for vessel trajectory compression discarding a significant part of the original positional updates, with minimal trajectory reconstruction error. In this work, we present an extension of this system, that allows the user to fine-tune trajectory compression according to the requirements of a given application. The extended system avoids the issues of hyper-parameter tuning, supports incremental optimization and facilitates composite maritime event recognition. Finally, we report empirical results from a comprehensive empirical evaluation against two real-world datasets of vessel positions.

We present spaTScope, a web application for visual exploration of geolocated time series. Analyzing such data is becoming increasingly important in many domains, such as energy demand management, geomarketing and geosocial networks. spaTScope allows users to visually explore large collections of geolocated time series and obtain insights about trends and patterns in their area of interest. The provided functionalities leverage a hybrid index that allows to navigate and group the available time series based not only on their similarity but also on spatial proximity. The results are visualized using linked plots combining maps and timelines.

In previous work we introduced a trajectory detection module that can provide summarized representations of vessel trajectories by consuming AIS positional messages online. This methodology can provide reliable trajectory synopses with little deviations from the original course by discarding at least 70% of the raw data as redundant. However, such trajectory compression is very sensitive to parametrization. In this paper, our goal is to fine-tune the selection of these parameter values. We take into account the type of each vessel in order to provide a suitable configuration that can yield improved trajectory synopses, both in terms of approximation error and compression ratio. Furthermore, we employ a genetic algorithm converging to a suitable configuration per vessel type. Our tests against a publicly available AIS dataset have shown that compression efficiency is comparable or even better than the one with default parametrization without resorting to a laborious data inspection.

We present SPHINX, a system for metapath-based entity exploration in Heterogeneous Information Networks (HINs). SPHINX allows users to define different views over a HIN based on both automatically selected and user-defined meta-paths. Then, entity ranking and similarity search can be performed over these views to find and explore entities of interest, taking also into account any spatial or temporal properties of entities. A Web-based user interface is provided to facilitate users in performing the various functionalities supported by the system, including metapath-based view definition, index construction, search parameters specification, and visual comparison of the results.

Geolocated time series, i.e., time series associated with certain locations, abound in many modern applications. In this paper, we consider hybrid queries for retrieving geolocated time series based on filters that combine spatial distance and time series similarity. For the latter, unlike existing work, we allow filtering based on local similarity, which is computed based on subsequences rather than the entire length of each series, thus allowing the discovery of more fine-grained trends and patterns. To efficiently support such queries, we first leverage the state-of-the-art BTSR-tree index, which utilizes bounds over both the locations and the shapes of time series to prune the search space. Moreover, we propose optimizations that check at specific timestamps to identify candidate time series that may exceed the required local similarity threshold. To further increase pruning power, we introduce the SBTSR-tree index, an extension to BTSR-tree, which additionally segments the time series temporally, allowing the construction of tighter bounds. Our experimental results on several real-world datasets demonstrate that SBTSR-tree can provide answers much faster for all examined query types.

Time series exploration and mining has many applications across several industrial and scientific domains. In this paper, we consider the problem of detecting locally similar pairs and groups, called bundles, over co-evolving time series. These are pairs or groups of subsequences whose values do not differ by more than ε for at least δ consecutive timestamps, thus indicating common local patterns and trends. We first present a baseline algorithm that performs a sweep line scan across all timestamps to identify matches. Then, we propose a filter-verification technique that only examines candidate matches at judiciously chosen checkpoints across time. Specifically, we introduce two block scanning algorithms for discovering local pairs and bundles respectively, which leverage the potential of checkpoints to aggressively prune the search space. We experimentally evaluate our methods against real-world and synthetic datasets, demonstrating a speed-up in execution time by an order of magnitude over the baseline.

We introduce a framework for online monitoring of moving objects, which takes into account their evolving trajectories and copes smoothly with fluctuating demands of multiple continuous queries for limited system resources. This centralized scheme accepts streaming positional updates from numerous objects, but it only examines recent trajectory segments with expectedly higher utility in query evaluation, shedding the rest as immaterial. We focus on adaptive processing under extreme load conditions, opting to retain salient trajectory segments and possibly sacrifice smaller, frequently observed paths in favor of longer, distinctive routes. We propose heuristics for incremental, yet approximate, query evaluation in order to provide up-to-date traffic analytics using windows that abstract particular regions and time intervals of interest. Finally, we conduct a comprehensive experimental study to validate our approach, demonstrating its benefits in result accuracy and efficiency for almost real-time response to trajectory-based aggregates.

Point of Interest (POI) data is widely used in many modern applications and services related to navigation, tourism, social networking, logistics, and many more. In this paper, we propose a comprehensive and vendor-agnostic data model to represent multi-faceted and enriched POI profiles. Harnessing the versatility of Linked Data technologies, this semantically rich ontology accommodates and extends existing POI formats for assembling and managing POI data from heterogeneous sources. Furthermore, we have developed the open-source software TripleGeo, which can effectively transform POI data from diverse sources and formats (geographical files, databases, and semi-structured data) to their RDF representations and vice versa. Thus, it is possible to import POI data from various existing systems and products, transfer and address the data integration challenges in the Linked Data domain, and export back the results. Our empirical study confirms the validity and efficiency of this framework for a variety of real-world POI assets and formats, underscoring its robustness to cope with scalable data volumes.

We present a big data framework for the prediction of streaming trajectory data, enriched from other data sources and exploiting mined patterns of trajectories, allowing accurate long-term predictions with low latency. To meet this goal, we follow a multi-step methodology. First, we efficiently compress surveillance data in an online fashion, by constructing trajectory synopses that are spatio-temporally linked with streaming and archival data from a variety of diverse and heterogeneous data sources. The enriched stream of trajectory synopses is stored in a distributed RDF store, supporting data exploration via SPARQL queries. The enriched stream of synopses along with the raw data is consumed by trajectory prediction algorithms that exploit mined patterns from the RDF store, namely medoids of (sub-) trajectory clusters, which prolong the horizon of useful predictions. The framework is extended with offline and online interactive visual analytics tool to facilitate real world analysis in the maritime and the aviation domains.

A geolocated time series is a sequence of values associated with a geolocation, such as measurements provided by a sensor installed at a certain location. In this paper, we address the problem of hybrid similarity joins over such geolocated time series. This operation returns all pairs of geolocated time series that exhibit similar behavior in the time series domain while also being closely located in space. First, we propose algorithms for performing such join operations using different types of indices, including spatial-only, time series-only, and hybrid indices. Such centralized indexing schemes can cope well with moderate data volumes but they face scalability issues when the dataset size increases significantly. To overcome this problem, we present a MapReduce-based processing scheme with space-driven partitioning. Our parallel and distributed algorithm leverages our hybrid index for geolocated time series to efficiently execute similarity joins locally within each partition and minimize the amount of data that needs to be shuffled between processing nodes. An extensive experimental evaluation confirms that our approach can efficiently compute all matching pairs even for datasets containing millions of geolocated time series.

We present an application framework that consumes streaming positions from a large fleet of flying aircrafts monitored in real time over a wide geographical area. Tailored for aviation surveillance, this online processing scheme only retains locations conveying salient mobility events along each flight, and annotates them as stop, change of speed, heading or altitude, etc. Such evolving trajectory synopses must keep in pace with the incoming raw streams so as to get incrementally annotated with minimal loss in accuracy. We also develop one-pass heuristics to eliminate inherent noise and provide reliable trajectory representations. Our prototype implementation on top of Apache Flink and Kafka has been tested against various real and synthetic datasets offering concrete evidence of its timeliness, scalability, and compression efficiency, with tolerable concessions to the quality of resulting trajectory approximations.

Given a set of geospatial objects, the Best Region Search problem finds the optimal placement of a fixed-size rectangle so that the value of a user-defined utility function over the enclosed objects is maximized. The existing algorithm for this problem computes only the top result. However, this is often quite restrictive in practice and falls short in providing sufficient insight about the dataset. In this paper, we introduce the k-BRS problem, and we present a method for efficiently and progressively computing the next best result for any number k of results requested by the user. We show that our approach can accommodate additional constraints. In particular, we consider the requirement of computing the next best rectangle that has no or little overlap with the already retrieved ones, which reduces the repetition and redundancy in the results presented to the user. Our experimental evaluation demonstrates that our algorithms are efficient and scalable to large real-world datasets.

Thousands of posts are generated constantly by millions of users in social media, with an increasing portion of this content being geotagged. Keeping track of the whole stream of this spatio-textual content can easily become overwhelming for the user. In this paper, we address the problem of selecting a small, representative and diversified subset of posts, which is continuously updated over a sliding window. Each such subset can be considered as a concise summary of the stream's contents within the respective time interval, being dynamically updated every time the window slides to reflect newly arrived and expired posts. We define the criteria for selecting the contents of each summary, and we present several alternative strategies for summary construction and maintenance that provide different trade-offs between information quality and performance. Furthermore, we optimize the performance of our methods by partitioning the newly arriving posts spatio-textually and computing bounds for the coverage and diversity of the posts in each partition. The proposed methods are evaluated experimentally using real-world datasets containing geotagged tweets and photos.

S.558-561

Time series associated with specific locations, such as visitor check-ins or sensor readings, have increased in size and popularity in several domains. Although several works have focused on efficient time series similarity search, there has been limited attention to the inherent challenge that geolocated time series introduce for hybrid queries on both spatial proximity and time series similarity. To efficiently process such queries, we propose a hybrid index, called TSR-tree, which extends the R-tree by introducing appropriate bounds for the time series indexed at each node. This reduces node accesses during query evaluation by simultaneously pruning the search space in the spatial domain and the time series domain while traversing the index. We also present an optimized version, the BTSR-tree, which uses tighter bounds by bundling together similar time series in each node. We describe how these indices can be used to efficiently evaluate different variants of hybrid queries combining spatial and time series filtering or ranking. Finally, we experimentally evaluate our work using real-world datasets from diverse domains, demonstrating a speed-up of 1.5 to 5 times in hybrid query workloads against the baseline R-tree method.

In this paper, we address the problem of continuously maintaining a concise, diversified summary of the contents of a sliding window over a stream of geotagged posts. Selecting posts to include in the summary takes into account both the criteria of coverage and diversity, and the summary is updated dynamically when the window slides. Our proposed strategy provides a trade-off between information quality and performance. An experimental evaluation of our method is presented using two real-world datasets containing spatio-textual posts from Twitter and Flickr.

We consider a centralized server that receives streaming updates from numerous moving objects regarding their current whereabouts. However, each object always relays its location cloaked into a broader uncertainty region under a Bivariate Gaussian model of varying densities. We wish to monitor a large number of continuous queries, each seeking k objects nearest to its own focal point with likelihood above a given threshold, e.g., "which of my friends are currently the k = 3 closest to our preferred cafe with probability over 75%". Since an exhaustive evaluation would be prohibitive, we develop heuristics based on spatial and probabilistic properties of the uncertainty model, and promptly issue approximate, yet reliable answers with confidence margins. We conducted a comprehensive empirical study to assess the performance and response quality of the proposed methodology, confirming that it can efficiently cope with large numbers of moving Gaussian objects under fluctuating uncertainty conditions, while also offering timely response with tolerable error to multiple queries of varying specifications.

Most messages posted in Twitter usually discuss an ongoing event, triggering a series of tweets that together may constitute a trending topic (e.g., #election2012, #jesuischarlie, #oscars2016). Sometimes, such a topic may be trending only locally, assuming that related posts have a geographical reference, either directly geotagging them with exact coordinates or indirectly by mentioning a well-known landmark (e.g., #bataclan). In this paper, we study how trending topics evolve both in space and time, by monitoring the Twitter stream and detecting online the varying spatial coverage of related geotagged posts across time. Observing the evolving spatial coverage of such posts may reveal the intensity of a phenomenon and its impact on local communities, and can further assist in improving user awareness on facts and situations with strong local footprint. We propose a technique that can maintain trending topics and readily recognize their locality by subdividing the area of interest into elementary cells. Thus, instead of costly spatial clustering of incoming messages by topic, we can approximately, but almost instantly, identify such areas of coverage as groups of contiguous cells, as well as their mutability with time. We conducted a comprehensive empirical study to evaluate the performance of the proposed methodology, as well as the quality of detected areas of coverage. Results confirm that our technique can efficiently cope with scalable volumes of messages, offering incremental response in real-time regarding coverage updates for trending topics.

Maritime monitoring is a typical Big Data problem where hundreds of thousands of vessels across the globe transmit messages about their location, speed and other information. We have developed a system for online vessel tracking that performs, as a first step, a high-rate but accurate trajectory compression. Subsequently, the compressed trajectories are analyzed by a complex event recognition engine, promptly reporting alerts to maritime authorities. To deal with realistic maritime event patterns, we seamlessly integrated spatial and temporal reasoning for online event recognition. The system is evaluated on real data from the Greek seas.

We present a system that combines intelligent online tracking with complex event recognition against streaming positions relayed from numerous vessels. Given the vital importance of maritime safety to the environment, the economy, and in national security, our sys-tem leverages the real-time acquisition of vessel activity with ge-ographical and other static information. Thus, it can offer timely notification in emergency situations, such as intrusion into marine preservation areas, loitering, and unsafe sailing. Thanks to a mobil-ity tracking module, evolving trajectories generated by massive po-sitional updates can be compressed online into concise, but reliable synopses per ship, retaining only salient motion features within a sliding window. These features are exploited by a complex event recognition module that detects suspicious situations of interest to maritime authorities. We conducted a comprehensive empirical validation against a real dataset of traces collected from thousands of vessels. Our results confirm the scalability and approximation accuracy of the proposed system, and thus demonstrate its poten-tial for effective, real-time maritime monitoring. 1.

An immense wealth of data is already accessible through the Semantic Web and an increasing part of it also has geospatial context or relevance. Although existing technology is mature enough to integrate a variety of information from heterogeneous sources into interlinked features, it still falls behind when it comes to representation and reasoning on spatial characteristics. It is only lately that several RDF stores have begun to accommodate geospatial entities and to enable some kind of processing on them. To address interoperability, the OGC has recently adopted the GeoSPARQL standard, which defines a vocabulary for representing geometric types in RDF and an extension to the SPARQL language for formulating queries. In this paper, we provide a comprehensive review of the current state-of-the-art in geospatially-enabled semantic data management. Apart from an insightful analysis of the available architectures in industry and academia, we conduct an evaluation study on prominent RDF stores with geospatial support. We also compare their performance and attested capabilities to renowned DBMSs widely used in geospatial applications. We introduce a methodology suitable to assess RDF stores for robustness against large geospatial datasets, and also for expressiveness on a variety of queries involving both spatial and thematic criteria. As our findings demonstrate, the potential for query optimization, advanced indexing schemes, and spatio-semantic extensions is significant. Towards this goal, we point out several challenging issues for joint research by the GIS and Semantic Web communities.

We consider an environment of numerous moving objects, equipped with location-sensing devices and capable of communicating with a central coordinator. In this setting, we investigate the problem of maintaining hot motion paths, i.e., routes frequently followed by multiple objects over the recent past. Motion paths approximate portions of objects' movement within a tolerance margin that depends on the uncertainty inherent in positional measurements. Discovery of hot motion paths is important to applications requiring classification/profiling based on monitored movement patterns, such as targeted advertising, resource allocation, etc. To achieve this goal, we delegate part of the path extraction process to objects, by assigning to them adaptive lightweight filters that dynamically suppress unnecessary location updates and, thus, help reducing the communication overhead. We demonstrate the benefits of our methods and their efficiency through extensive experiments on synthetic data sets.

We report on our experience from design and implementation of a powerful map application for managing, querying and visualizing evolving locations of moving objects. Instead of building a specialized spatiotemporal database, we have chosen to retain geographic information in a renowned stream processing engine with native support for spatial features. Through a graphical interface, users are able to specify typical continuous queries (such as range, distance, or nearest neighbor search), and receive incremental results. Moreover, this application offers capabilities for visual display of objects' trajectories and online collection of movement statistics.

We present a simulation environment that can be employed to study P2P mobile networks that are fast-evolving in both their topology and their content. This simulator implements a proposed P2P architecture based on Mobile Agent and Active Database technology and can be employed in order to build simulated mobile networks that are characterized by a diversity in peer needs, specifications and capabilities.

Handling streams of positional updates from numerous moving ob-jects has become a challenging task for many monitoring applica-tions. Several algorithms have been recently proposed for provid-ing exact answers particularly to continuous range and k-nearest neighbor queries against current object positions. In this work, we introduce a processing technique for efficiently maintaining an ap-proximate order-k Voronoi cell around a certain point of interest when all objects continuously change their locations. This heuristic can easily provide a fairly reliable estimate of the k-nearest neigh-bors for any query point found inside the constructed cell. We fur-ther extend our method to handle positional updates that are not received concurrently for all objects, but instead remain valid for a specific time interval according to a sliding window model. Ex-tensive experimental analysis over synthetic datasets confirms the robustness and scalability of this approach offering near real-time cell maintenance with acceptable error margins.

Several window constructs are usually specified in continuous queries over data streams as a means of limiting the amount of data processed each time and thus providing real-time responses. Current research has mostly focused on tackling the temporal volatility of the stream, overlooking other inherent features of incoming items. In this paper, we argue that novel window types, other than strictly temporal, can also prove adequate in providing finite portions of multidimensional streams. We systematically examine the particular case of spatiotemporal streams generated from moving point objects and we introduce a comprehensive classification of window variants useful in expressing the most common operations, such as range or nearest- neighbor search. Our investigation also demonstrates that composite windows, combining temporal and spatial properties, can effectively capture the evolving characteristics of trajectories and assist significantly in query specification.

We present a hierarchical tree structure for online maintenance of time-decaying synopses over streaming data. We exemplify such an amnesic behavior over streams of locations taken from numerous moving objects in order to obtain reliable trajectory approximations as well as affordable estimates regarding distinct count spatiotemporal queries.

Monitoring movement of high-dimensional points is essential for environmental databases, geospatial applications, and biodiversity informatics as it reveals crucial information about data evolution, provenance detection, pattern matching etc. Despite recent research interest on processing continuous queries in the context of spatiotemporal data streams, the main focus is on managing the current location of numerous moving objects. In this paper, we turn our attention onto a historical perspective of movement and examine trajectories generated by streaming positional updates. The key challenge is how to maintain a concise, yet quite reliable summary of each object's movement, avoiding any superfluous details and saving in processing complexity and communication cost. We propose two single-pass approximation techniques based on sampling that take advantage of the spatial locality and temporal timeliness inherent in trajectory streams. As a means of reducing substantially the scale of the datasets, we utilize heuristic prediction to distinguish which locations to preserve in the compressed trajectories. A comprehensive experimental study verifies the stability and robustness of the proposed techniques and demonstrates that intelligent compression schemes are able to act as effective load shedding operators achieving remarkable results