The rapid adoption of electric vehicles calls for efficient and specialized route planning solutions.Existing solutions focus primarily on minimizing travel time or the number of necessary stops for recharging.In particular, not much attention has been given to the "range anxiety problem," i.e., maximizing proximity to charging stations and maintaining a given minimal acceptable battery level.This paper presents a route planning approach that generates Pareto-optimal routes by considering both travel time and range anxiety.Our solution leverages a multi-objective version of the well-known A* algorithm in order to find diverse route options that reflect trade-offs between those two conflicting objectives.We show the viability of our approach by implementing it as a standalone web-based application using openly accessible datasets for road networks and charging stations.

Effective route planning for shared mobility is crucial for user experience in transportation services such as ridesharing, logistics, and food delivery.However, in high-volume applications with travel times that depend on the time of day, high computational complexity can impair route planning throughput.This paper proposes a batch insertion operator that handles multiple concurrent requests.It proposes a novel partitioning solution that uses route length rather than spatial proximity as a partitioning criterion, then adaptively assigns workers to larger partitions.Compared to a greedy solution that repeatedly applies the standard, i.e., non-batched, insertion operator, query processing is significantly accelerated with minor to no degradation in solution quality.Extensive experiments using three city-scale datasets demonstrate that this approach can provide speedups up to 15× and is also amenable to parallelisation.

Finding the shortest route between two locations is a well-researched problem.We address a variation thereof, the "shade-optimizing routing problem," which allows one to set a preference for routes with more or less shade.This kind of problem is of interest, for instance, for runners and bikers, who may prefer shadier routes during summer heat or around noon time, and sunnier ones in late fall or early morning.As our main contribution, this demonstration paper presents ShadeRoute, a open-sourced cloud-based app that leverage open datasets and APIs in order to provide routes that fit the user's priorities regarding shade (or not) at a given route and particular time. CCS Concepts• Information

Quantitative information about entities constitutes a significant portion of tabular data in open sources and data lakes.Such tables often lack consistent labeling and proper schema, posing significant challenges for querying and integration.This paper studies the problem of numerical column annotation in scenarios where quantitative data may be gathered from different sources and unit consistency is a concern.For instance, weight measurements may vary between entities, expressed in kilograms for some and pounds for others, with no accompanying unit information.We investigate the conditions for effectively annotating mixed-unit numeric data, introduce a benchmark for such an annotation task, and propose an algorithm that reliably detects semantic types (e.g., height) and links them to the corresponding types present in a knowledge graph.Our evaluation on a diverse set of columns with mixed units and varying levels of annotation difficulty shows that our method significantly outperforms strong baselines such as GPT-4o-mini and SAND in terms of accuracy, excelling in both detecting mixed units and annotating them with appropriate semantic labels.

Trajectory data collected by GPS has found many critical applications. Unfortunately, most trajectory datasets have missing data due to technical problems or due to the sampling strategy used. Trajectory imputation is the task of filling in the gaps in actual trajectories by computing points that fit "naturally" within existing trajectories. Considering that both trajectories and natural language are essentially sequences of symbols, we explore the use of probabilistic language models for trajectory imputation. Using a grid-based representation of the space, and not considering the underlying road network, we convert trajectory points into tokens corresponding to the grid cell where they appear and train models of different sizes. We report experiments on a real dataset of over 500,000 taxi trips, showing that we can accurately fill gaps of up to 2km between GPS observations with 83% precision. These results are comparable to approaches using much more computationally demanding Large Language Models based on transformers. We discuss why transformers are overkill for the task through experiments that show that trajectory data does not exhibit very long dependencies, as is the case with natural language.

Last-mile delivery (LMD) is known as the task of delivering items from a warehouse to a customer. In LMD's original version, each item is to be delivered to a single location in a city's network. In this paper, we extend such a scenario by assuming that there can be alternative delivery locations for each item, depending on the time of the day, and aim at maximizing the number of deliveries completed by a courier. We call this new problem the Last Mile Flexible Delivery (LMFD) problem. In fact, at least one e-commerce company, namely Amazon, currently offers the possibility of delivering items to a customer's parked car, thus making the LMFD problem, not only computationally challenging, but also practically relevant. After showing LMFD's NP-hardness, we propose an efficient heuristic approach based on provably correct pruning of the search space, and, using a real and large mobility dataset, we show that such heuristic is both effective and highly efficient.

HDBSCAN*, a state-of-the-art density-based hierarchical clustering method, produces a hierarchical organization of clusters in a dataset w.r.t. a parameter mpts. While a small change in mpts typically leads to a small change in the clustering structure, choosing a “good” mpts value can be challenging: depending on the data distribution, a high or low mpts value may be more appropriate, and certain clusters may reveal themselves at different values. To explore results for a range of mpts values, one has to run HDBSCAN* for each value independently, which can be computationally impractical. In this paper, we propose an approach to efficiently compute all HDBSCAN* hierarchies for a range of mpts values by building upon results from computational geometry to replace HDBSCAN*'s complete graph with a smaller equivalent graph. An experimental evaluation shows that our approach can obtain over one hundred hierarchies for the computational cost equivalent to running HDBSCAN* about twice, which corresponds to a speedup of more than 60 times, compared to running HDBSCAN* independently that many times. We also propose a series of visualizations that allow users to analyze a collection of hierarchies for a range of mpts values, along with case studies that illustrate how these analyses are performed.

This demonstration paper focuses on transportation-related queries within a city that go beyond simple routing and that are of interest to different types of users. For instance, individual users could be interested in which modes of transport are more effective to reach a set of alternative locations at a given time of the day, whereas urban planners could be interested in the effect that adding/removing a bus line would have in connecting regions of a city, e.g., a residential neighborhood and downtown. Given that context and using real data from the city of Berlin, we introduce RRAMEN, an interactive tool which is well equipped to support different city-scale mobility-related queries by different types of users.

Consider a customer who has a shopping list and a personal shopper who is willing to buy and resell goods in a customer's shopping list. It is in the personal shopper's best interest to find shopping routes that minimize two competing criteria: the time needed to serve a customer and the price paid for the goods. In this short paper we present an efficient solution to this problem based on finding an approximate linear skyline set of such shopping routes. (An extended version of this paper can be found at [1]).

Consider the following scenario: (a) a worker traveling on the shortest path between two locations in a city's road network, (b) he/she is willing to deviate from such path in order to complete tasks in the network, (c) tasks are associated with rewards and appear and disappear dynamically, i.e., they are not known in advance, and (d) the worker specifies a time budget which limits the total time he/she is willing to spend on his/her trip. Now assume the worker wants to minimize the detour from the original path while, at the same time, maximizing the rewards collected by completing tasks; clearly two competing criteria. We call this problem the Online In-Route Task Selection (Online-IRTS) query, and we investigate it using the paradigm of skyline queries in order to systematically explore different trade-offs between earned rewards and path deviation. Because of the online nature of the problem, i.e., irrevocable decisions about which task to perform have to be made without knowledge of future tasks, it is not possible to guarantee optimal solutions for the Online-IRTS query. Therefore, we propose two heuristic approaches, one is based on local optimizations, and the other one is based on incremental solutions, along with a method to evaluate the quality of their solutions w.r.t. the optimal offline solution. Our experiments using city-scale realistic datasets show that the first approach is more effective whereas the second is more efficient, allowing one to choose which approach to use according to his/her priorities.

The well-known Optimal Sequenced Routing (OSR) query considers a traveller that needs to stop by some cost-free points of interest (POIs), each belonging to a given strict sequence of categories of interest (COIs), while minimizing only the distance traveled. In this paper we extend the OSR query by adding the constraint that (1) each POI yields a non-null cost and that (2) the traveller wishes to minimize the travel distance as well as the total cost of POIs he/she stops by. We name this new query as Trade-Off Aware Sequenced Routing (TASeR). The challenging aspect of this query is that it is not always possible to optimize both travel distance and total POI cost simultaneously. As well, combining both criteria into a single one with predetermined weights may not be desirable or even feasible. As our main contribution we make use of the linear skyline paradigm, along with provably correct pruning criteria, to propose an approach that finds all optimal solutions for any linear combination of the two competing criteria very efficiently. Our experiments using real city-scale data show that our proposed approach can obtain optimal linear skyline sets in sub-second processing time for reasonably sized instances of the TASeR query. Moreover, we show that any instance of the traditional OSR query can be easily modeled as a TASeR query, hence, our proposed approach can also solve OSR queries at the expense of negligible overhead.

Proximity-oriented spatial queries, such as range queries and k-nearest neighbors (kNNs), are common in many applications, notably in Location Based Services (LBS). However, in many settings, users may also desire that the returned proximal objects exhibit (likely) maximal and fine-grained semantic diversity. For instance, nearby restaurants with different menu items are more interesting than close ones offering similar menus. Towards that goal, we propose a topic modeling approach based on the Latent Dirichlet Allocation, a generative statistical model, to effectively model and exploit a fine-grained notion of diversity, namely based on sets of keywords (e.g., menu items) instead of a coarser user-given category (e.g., a restaurant's cuisine). In addition, and relying on the notion of Distance Signatures, we propose an index structure that can be used to effectively extract the k objects that are within a range distance from a given query location, and which are also semantically diverse. Our experimental evaluations using real datasets demonstrate that the proposed methodology is able to provide highly diversified answers to cardinality-wise constrained range queries much more efficiently than a straightforward alternative solution.

We consider a spatial crowdsourcing scenario where (1) a worker is traveling on a preferred/typical path within a road network where (2) there is a set of tasks, each associated with a positive reward, available to be performed and (3) that the worker is willing to possibly deviate from his/her preferred path to perform tasks as long as (4) he/she travels at most a total given distance/time. We name this the In-Route Task Selection (IRTS) problem and investigate it using the skyline paradigm in order to obtain a set of diverse solutions yielding good combinations of detour and reward. Given the NP-hardness of the IRTS problem we present a heuristic approach that produces solutions with good values of precision and recall for problems of realistic sizes within practical query processing time.

This paper presents a solution to the problem posed in the ACM SIGSPATIAL GIS Cup 2018, namely to identify all upstream features---nodes and edges existing on simple paths between starting points and controllers---in a given spatial network. Our approach is based primarily on a two-sweep depth-first search which decomposes a graph into its biconnected components prior to collecting the upstream features. Our algorithm runs in linear time in the size of the graph and, in practice, is able to solve large instances with millions of features within seconds on an ordinary personal laptop, identifying features if and only if they are upstream.

Consider a group of colleagues going from their offices to their homes, via their preferred subway or bus routes, who wish to find k alternative restaurants to meet and which would minimize a given aggregate deviation distance from their typical routes. We call this the "k-Optimal Meeting Points for Public Transit" (k-OMPPT) query and present two approaches for returning provably correct answers for both SUM and MAX aggregate detour distances. Both approaches exploit geometric properties of the problem in order to refine the POI search space and hence reduce the query's processing time. Our experiments, using real datasets, compare the efficiency of both approaches and show which approach is preferable given the type of aggregate the group is interested in minimizing.

In this demonstration paper we introduce MustaCHE ( Multiple Clustering Hierarchies Explorer ), a tool that allows analysis and exploration of multiple clustering hierarchies in an interactive and visual manner. A known issue in the context of density-based clustering is how to set parameters. Typically one has to resort to trial-and-error, and its potential pitfalls, which may possibly include not finding existing clusters at all. In a previous work we have devised a very efficient technique to generate clustering hierarchies using HDBSCAN* w.r.t . a range of its clustering parameter, mpts . However, finding the "best" mpts value is still an open problem. In order to mitigate this issue we developed MustaCHE, a tool that allows a user to visualize several different density-based cluster hierarchies of a dataset w.r.t . a large range of mpts values. The user can then explore hierarchies individually and, at the same time, see how they compare to the other hierarchies. The simultaneous visualization of multiple clustering hierarchies provided by MustaCHE makes it feasible (and easy) for a user to gain a deeper understanding of the data and how its cluster structures behave under different parameter settings.

Humans are animals of habit, e.g., people follow typical and/or familiar paths in their daily routines. With that in mind we investigate the problem where a user, traveling on his/her preferred path, needs to visit one of many available points-of-interest while (1) minimizing his/her total travel distance and also (2) minimizing the detour distance incurred to reach the chosen point-of-interest. We call this new problem the "Best-Compromise In-Route Nearest Neighbor" query in order to emphasize that a route cannot typically optimize both criteria at the same time, but rather find a compromise between them. In fact, the competing nature of these two criteria resembles the notion of skyline queries. In that context, we propose a solution based on using suitable upper-bounds to both cost criteria to prune uninteresting paths. It returns all linearly non-dominated paths that are optimal under any given linear combination of the two competing criteria. Our experiments using real data sets of different sizes show that our proposal can be orders of magnitude faster than a straightforward alternative.

MinMax routing is the task of finding a feasible route between two points such that the maximum distance between any point in the path and a set of points-of-interest is minimal. In this demonstration paper we focus on the case of routing electric vehicles and where points-of-interest are charging stations. In this scenario, the MinMax route guarantees that for any arbitrary point in such a route, the maximum distance that has to be traveled in order to reach a charging station is minimal, being thus a "safer" route. We propose a solution to the MinMax routing problem and implement a web-based prototype that produces practical MinMax routes in realistic sized networks, e.g., the state of California, in sub-second processing time.

HDBSCAN*, a state-of-the-art density-based hierarchical clustering method, produces a hierarchical organization of clusters in a dataset w.r.t. a parameter mpts. While the performance of HDBSCAN* is robust w.r.t. mpts, choosing a "good" value for it can be challenging: depending on the data distribution, a high or low value for mpts may be more appropriate, and certain data clusters may reveal themselves at different values of mpts. To explore results for a range of mpts, one has to run HDBSCAN* for each value in the range independently, which is computationally inefficient. In this paper we propose an efficient approach to compute all HDBSCAN* hierarchies for a range of mpts by replacing the graph used by HDBSCAN* with a much smaller graph that is guaranteed to contain the required information. Our experiments show that our approach can obtain, for example, over one hundred hierarchies for a cost equivalent to running HDBSCAN* about 2 times. In fact, this speedup tends to increase with the number of hierarchies to be computed.

Consider a road network where some vertices represent points-of-interests (POIs) and each POI belongs to exactly one category-of-interest (COI). Within that context, consider a group of travelers, each leaving from their source locations towards their destinations (all possibly distinct), as well as a sequence of COIs that the group is interested to visit. A Sequenced Group Trip Planning Query (SGTPQ) returns, for each traveler, the route from their source locations to their destinations such that all users go through the same POIs, each one belonging to the specified sequence of COIs, while minimizing the total distance traveled by the group. Previous proposals for processing SGTPQs require examining some POIs repeatedly, thus incurring in redundant computation. In order to overcome that we state the Suffix Optimality Principle, which allows efficient reuse of previously computed optimal partial group trips. We use it as the backbone of our proposal, the Iterative Backward Search (IBS). IBS is a provably correct stateful depth-first search algorithm for processing SGTPQs. Our extensive experiments based on real and synthetic data sets show that IBS, by virtue of its statefulness, significantly outperforms state-of-the-art, but otherwise stateless, approaches.

In this paper, we investigate a novel query type for road networks, namely the k-Optimal Meeting Points based on Preferred paths (k-OMP3) query. Consider a group of friends currently at different places, e.g., their offices. Before going to their respective homes, using their own preferred paths in the underlying road network, the group is willing to meet at a restaurant for dinner. A k-OMP3 query would return the k restaurants that would minimize the group detour distance. In this short paper we present a provably correct approach which exploits the geometric properties of the problem in order to reduce the query's processing time. Our experiments, using real and synthetic data sets, confirm the effectiveness and efficiency of such approach.

Given two sets of nodes P and Q on a road network, a k-Closest Pairs Query (k-CPQ) finds the pairs from P × Q which have the k smallest network distances. Although this problem has been well studied in the Euclidean and metric spaces, this is the first time it is being investigated in the more realistic case of road networks. As our first contribution, we present a new indexing structure, named G -tree, which is designed to support our proposed algorithms. Then, we propose, as our main contribution, two different approaches for processing k-CPQs. While the first approach applies a top-down traversal paradigm by applying a best-first search strategy, the second approach looks for the k-closest pairs by traversing the G*-tree in a bottom-up manner. Both of the these approaches employ an effective pruning strategy for shrinking the search space based on the minimum network distance between sub-graphs, which is main driver for the G*-tree's construction. Finally, we investigate the efficiency of the proposed approaches under a number of different parameters using real road networks.

Despite the wealth of research published on reverse k-nearest neighbour (RkNN) queries very few attempts have been made to solve the problem in time-dependent networks, i.e., networks where the edge cost varies with time. A typical example of such network is one made of a city's streets. An interesting consequence of such assumption is that set of RkNNs can change over time even if the objects are not moving. We present an efficient algorithm that computes a RkNN schedule for a given time interval, e.g., one day. Once computed, such schedule allows one to find the RkNNs for any point within the given time interval doing a simple table lookup. We experimentally evaluate our novel methods using a straightforward solution, namely computing the RkNN set for every (discrete) instant within a time interval. Our results show that the proposed algorithms are orders of magnitude faster than such baseline approach.

In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. Our approach uses the A* search paradigm equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. Our experiments using a real data set have shown our proposed solution to be up to two orders of magnitude faster than a previous solution extended to handle time-dependency.

Graphast is a framework tool that allows developers to compose a number of network models, data importing/exporting services as well as query services, in order to quickly build applications on time-dependent networks. The main goal is to allow developers to implement solutions to different types of problems on time-dependent networks using spatial queries, such as nearest neighbor queries, optimal sequenced routes, etc. Graphast allows the combination of facilities provided by the framework via a public API and/or the building of new facilities, e.g., a new query processing algorithm, and incorporate those into Graphast for others to use them as well. In this paper, we discuss Graphast's architectural components and how one can create/store instances of those components in order to build an application. The steps necessary for building a real world application are also presented.

Consider the problem of a group of friends who want to depart from their current locations (e.g., workplaces) towards a common destination (e.g., a restaurant) but also want to meet at a single intermediary point before continuing traveling together from there. The goal is to minimize an aggregate perceived travel cost by taking advantage of companionship, e.g., a pre-defined mutual affinity factor, motivated by the common impression that "time flies when in good company". This is an instance of what we name as the Optimal Single Connecting Point (OSCP) query. In this paper we present Meet-and-Go, a prototype application with a simple interface for solving instances of the (top) k-OSCP query, thus allowing the user to also explore alternative solutions as well.

Directions and paths, as commonly provided by route guidance systems, are usually derived considering absolute metrics, e.g., finding the shortest path within the underlying road network. This demo presents a framework which uses crowdsourced geospatial data to obtain paths that do not only minimize travel time but also guide users along popular points of interest (POIs). By analyzing textual travel blog data and Flickr data, we define a measure for popularity of POIs. This measure is used as an additional cost criterion in the underlying road network graph. Furthermore, we propose an approach to reduce the problem of finding paths which maximize popularity while minimizing travel time to the computation of bicriterion pareto optimal paths. The presented framework allows users to specify origin and destination within a road network, returning the set of pareto optimal paths or a subset thereof if a desired number of POIs along the path has been specified. Each of the returned routes is enriched with representative Flickr images and textual information from travel blogs. The framework and its results show that the computed paths yield competitive solutions in terms of travel time while also providing more “popular” paths, making routing easier and more informative for the user.

We study Sequenced Group Trip Planning Queries (SGTPQs). Consider a road network where some vertices represent Points of interest (POIs) and each POI belongs to exactly one Category of Interest (COI), e.g., A COI can be "Restaurants" and each POI in this COI is a specific instance of a restaurant. Given a group of users, each starting from a (possibly distinct) source location and going ultimately to a (possibly distinct) destination, as well as a ordered sequence of COIs, the SGTPQ finds, for each user, the route from his/her source location to his/her destination such that all users go through the same POIs, each one belonging to the specified sequence of COIs, while minimizing the total distance travelled by all users in the group. Different from previous work which investigated SGTPQs in Euclidean distance, we focus on SGTPQs in the more realistic case of road networks. The only existing algorithm for processing SGTPQs which may be also applicable in road networks, named IA, suffers from two drawbacks: it is not able to produce optimal answers and is computationally expensive. The first contribution of this paper is a small modification to IA, so that it can provide optimal solutions. The second and main contribution is a new approach, called Progressive Group Neighbour Exploration (PGNE) that delivers the optimal solution while being more efficient than IA. Our extensive experiments based on real and synthetic datasets show that PGNE is always faster than the modified IA and, in particular, typically twice as fast with respect to the number of users in the group travelling together, an important parameter for this type of query.

A Wireless Sensor Network (WSN) consists of a set of small and autonomous sensing nodes, which possess limited energy and computational capabilities, and are typically used to monitor events. In many applications, one is interested in continuous and robust statistical summaries of the observed values, and in this paper we focus on reporting the median of the observed values gathered by the WSN. Keeping in mind that the nodes' energy consumption is paramount in a WSN, we propose a distributed and energy-efficient approach based on the use of multiple, suitably designed, histogram queries which efficiently explore existing cached results minimizing the number of bytes transmitted. Our experimental results, using synthetic and real datasets, show that our proposed solution is indeed able to substantially extend the lifespan of the WSN when compared to the current state-of-the-art.

A major concern when processing queries within a wireless sensor network is to minimize the energy consumption of the network nodes, thus extending the networks lifetime. One way to achieve this is by minimizing the amount of communication required to answer queries. In this paper we investigate exact continuous quantile queries, focusing on the particular case of the median query. Many recently proposed algorithms determine a quantile by performing a series of refining histogram queries. For that class of queries, we recently proposed a cost-model to estimate the optimal number of histogram buckets within an algorithm for mini-mizing the energy consumption of a query. In this paper, we extend that algorithm for continuous queries. Furthermore we also offer a new refinement-based algorithm that employs a heuristic to minimize the number of message transmis-sions. Our experiments, using synthetic and real datasets, show that despite its theoretical runtime complexity our heuristic solution is able to perform significantly better than histogram-based approaches. 1.

Directions and paths, as commonly provided by navigation systems, are usually derived considering absolute metrics, e.g., finding the shortest path within an underlying road network. With the aid of crowdsourced geospatial data we aim at obtaining paths that do not only minimize distance but also lead through more popular areas using knowledge generated by users. We extract spatial relations such as "nearby" or "next to" from geo-textual travel blogs, that define closeness between pairs of points of interest (POIs) and quantify each of these relations using a probabilistic model. Using Bayesian inference, we obtain a probabilistic measure of spatial closeness according to the crowd. Applying this measure to the corresponding road network, we derive an altered cost function taking crowdsourced spatial relations into account. We propose two routing algorithms on the enriched road networks. To evaluate our approach, we use Flickr photo data as a ground truth for popularity. Our experimental results -- based on real world datasets -- show that the computed paths yield competitive solutions in terms of path length while also providing more "popular" paths, making routing easier and more informative for the user.

We consider the problem of finding the k nearest points of interest from a given location in time-dependent road networks, i.e., One where travel time along each edge is a function of the departure time, and where the operating times of the points of interest are also taken into consideration. More specifically, we address the following query: find the k points of interest in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the point of interest and the waiting time, if it is closed. Previous works have proposed solutions to answer kNN queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters.

In this paper we investigate how to efficiently and effectively use histogram queries for processing quantile queries in wireless sensor networks. A major concern when processing queries within such an environment is to minimize the energy consumption by the network nodes, thus extending the networks lifetime, e.g., the time when the first node runs out of energy. Towards that goal, we define a cost model for a refinement-based algorithm that performs a series of refining histogram queries in order to determine the exact quantile value. Given that the histogram size, i.e., its number of bins, is an important factor in the query processing cost, we use the defined cost model to estimate the histogram size that minimizes the maximum energy cost per-node when processing the quantile query. This is equivalent to maximizing the time until the first node dies and therefore to extending the network's lifetime. In our experiments, using synthetic and real datasets, we evaluate the performance of the proposed solutions in a variety of different settings.

Existing distance measures of time series such as the euclidean distance, DTW, and EDR are inadequate in handling certain degrees of amplitude shifting and scaling variances of data items. We propose a novel distance measure of time series, Spatial Assembling Distance (SpADe), that is able to handle noisy, shifting, and scaling in both temporal and amplitude dimensions. We further apply the SpADe to the application of streaming pattern detection, which is very useful in trend-related analysis, sensor networks, and video surveillance. Our experimental results on real time series data sets show that SpADe is an effective distance measure of time series. Moreover, high accuracy and efficiency are achieved by SpADe for continuous pattern detection in streaming time series.

In this paper, we consider the exact top-k query problem in wireless sensor networks, i.e., where one seeks to find the k highest reported values as well as the complete set of nodes that reported them. Our primary contribution in this context is EXTOK, a provably correct and topology-independent new filtering-based algorithm for processing exact top-k queries. As a secondary contribution we confirm a previous result of ours by showing that the efficiency of top-k query processing algorithms, including EXTOK, can be further improved by simply choosing a proper underlying logical tree topology. We examine EXTOK's performance with respect to a number of parameters and different logical tree topologies while using both synthetic and real data sets. Our simulation reveal that EXTOK consistently outperforms the current state-of-the-art algorithm by a very significant margin and regardless of the underlying logical tree topology.

Top-k queries are a popular type of query in wireless sensor networks. Typical solutions rely on coordinated root-to-nodes and nodes-to-root messages and on maintaining filters at the nodes, aiming at suppressing unnecessary messages, hence saving energy and furthering the network's lifetime. In this paper, we exploit the capability of a sensor node to cache a few recently observed values in order to determine "trends" for the observed values. Those trends can be used to further restrict the number of messages that need to be exchanged in the network, thus ultimately extending the network's lifetime. We compare our approach to the most recently proposed solutions in the literature using real and synthetic datasets, and we show that our approach is able to improve the network's lifetime by up to 28% without any loss in the quality of the answer.

In a Moving Object Database (MOD), the dataset, for example, the location of objects and their distribution, and the workload change frequently. Traditional static indexes are not able to cope well with such changes, that is, their effectiveness and efficiency are seriously affected. This calls for the development of novel indexes that can be reconfigured automatically based on the state of the system. In this article, we design and present the ST 2 B-tree, a S elf- T unable S patio- T emporal B + -tree index for MODs. In ST 2 B-tree, the data space is partitioned into regions of different density with respect to a set of reference points. Based on the density, objects in a region are managed using a grid of appropriate granularity; intuitively, a dense region employs a grid with fine granularity, while a sparse region uses a grid with coarse granularity. In this way, the ST 2 B-tree adapts itself to workload diversity in space. To enable online tuning, the ST 2 B-tree employs a “multitree” indexing technique. The underlying B + -tree is logically divided into two subtrees. Objects are dispatched to either subtree depending on their last update time. The two subtrees are rebuilt periodically and alternately. Whenever a subtree is rebuilt, it is tuned to optimize performance by picking an appropriate setting (e.g., the set of reference points and grid granularity) based on the most recent data and workload. To cut down the overhead of rebuilding, we propose an eager update technique to construct the subtree. Finally, we present a tuning framework for the ST 2 B-tree, where the tuning is conducted online and automatically without human intervention, and without interfering with the regular functions of the MOD. We have implemented the tuning framework and the ST 2 B-tree, and conducted extensive performance evaluations. The results show that the self-tuning mechanism minimizes the degradation of performance caused by workload changes without any noticeable overhead.

In a moving objects database (MOD) the dataset and the workload change frequently. As the locations of objects change in space and time, the data distribution also changes and the answer for a same query over the same region may vary widely over time. As a result, traditional static indexes are not able to perform well and it is critical to develop self-tuning indexes that can be reconfigured automatically based on the state of the system. Towards this goal we propose the ST2B-tree, a Self-Tunable Spatio-Temporal B+-Tree index for MODs, which is amenable to tuning. Frequent updates to its subtrees allows rebuilding (tuning) a subtree using a different set of reference points and different grid size without significant overhead. We also present an online tuning framework for the ST2B-tree, where the tuning is conducted online and automatically without human intervention, also not interfering with regular functions of the MOD. Our extensive experiments show that the self-tuning process minimizes the effectiveness degradation of the index caused by workload changes at the cost of virtually no overhead.

This article discusses a novel approach developed for static index pruning that takes into account the locality of occurrences of words in the text. We use this new approach to propose and experiment on simple and effective pruning methods that allow a fast construction of the pruned index. The methods proposed here are especially useful for pruning in environments where the document database changes continuously, such as large-scale web search engines. Extensive experiments are presented showing that the proposed methods can achieve high compression rates while maintaining the quality of results for the most common query types present in modern search engines, namely, conjunctive and phrase queries. In the experiments, our locality-based pruning approach allowed reducing search engine indices to 30% of their original size, with almost no reduction in precision at the top answers. Furthermore, we conclude that even an extremely simple locality-based pruning method can be competitive when compared to complex methods that do not rely on locality information.

Monitoring predefined patterns in streaming time series is useful to applications such as trend-related analysis, sensor networks and video surveillance. Most current studies on such monitoring employ Euclidean distance to calculate the similarities between given query patterns and subsequences of streaming time series. Euclidean distance has been shown to be ineffective in measuring distances of time series in which shifting and scaling usually exist. Consequently, warping distances such as dynamic time warping (DTW), longest common subsequence (LCSS), have been proposed to handle warps in temporal dimension. However, they are inadequate in handling shifting and scaling in amplitude dimension. Moreover, they have been designed mainly for full sequence matching, whereas in online monitoring applications, we typically have no knowledge on the positions and lengths of possible matching subsequences. In this paper, we first discuss the weaknesses of existing warping distances on detecting patterns from streaming time series. We then propose a novel warping distance, which we name Spatial Assembling Distance (SpADe), that is able to handle shifting and scaling in both temporal and amplitude dimensions. We further propose an efficient approach for continuous pattern detection using SpADe, that is fundamental for subsequence matching on streaming data. Finally, our experimental results show that SpADe is effective and efficient for continuous pattern detection in streaming time series.

We consider the problem of processing join queries in a wireless sensor network, focusing on where (which sensor node(s)) to process the join. We propose four strategies for processing such queries and investigate their performance across several scenarios. Not surprisingly, our experiments show that no single strategy performs best for all scenarios. In order to avoid the potential high cost of using a fixed strategy for processing all queries, we develop a cost-based model that can be used to select the best join strategy for the query at hand. Our experiments confirm that, given a set of queries, selecting the join strategy based on the cost model is always better than using any fixed strategy for all queries.

Given their autonomy, flexibility and large range of functionality, wireless sensor networks can be used as an effective and discrete means for monitoring data in many domains. Typical sensor nodes are very constrained, in particular regarding their energy and memory resources. Thus, any query processing solution over these devices should consider their limitations. We investigate the problem of processing join queries within a sensor network. Due to the limited memory at nodes, joins are typically processed in a distributed manner over a set of nodes. Previous approaches have either assumed that the join processing nodes have sufficient memory to buffer the subset of the join relations assigned to them, or that the amount of available memory at nodes is known in advance. These assumptions are not realistic for most scenarios. In this context we propose and investigate DIJ, a distributed algorithm for join processing that considers the memory limitations at nodes and does not make a priori assumptions on the available memory at the processing nodes. At the same time, our algorithm still aims at minimizing the energy cost of query processing.

Sensor networks are made of autonomous devices that are able to collect, store, process and share data with other devices. Spatiotemporal region queries can be used for retrieving information of interest from such networks. Such queries require the answers only from the subset of the network nodes that fall into the query region. If the network is redundant in the sense that the measurements of some nodes can be substituted by those of other nodes with a certain degree of confidence, then a much smaller subset of nodes may be sufficient to answer the query at a lower energy cost. We investigate how to take advantage of such data redundancy and propose two techniques to process spatiotemporal region queries under these conditions. Our techniques reduce up to twenty times the energy cost of query processing compared to the typical network flooding, thus prolonging the lifetime of the sensor network.

The unarguably fast, and continuous, growth of the volume of indexed (and indexable) documents on the Web poses a great challenge for search engines. This is true regarding not only search effectiveness but also time and space efficiency. In this paper we present an index pruning technique targeted for search engines that addresses the latter issue without disconsidering the former. To this effect, we adopt a new pruning strategy capable of greatly reducing the size of search engine indices. Experiments using a real search engine show that our technique can reduce the indices' storage costs by up to 60% over traditional lossless compression methods, while keeping the loss in retrieval precision to a minimum. When compared to the indices size with no compression at all, the compression rate is higher than 88%, i.e., less than one eighth of the original size. More importantly, our results indicate that, due to the reduction in storage overhead, query processing time can be reduced to nearly 65% of the original time, with no loss in average precision. The new method yields significative improvements when compared against the best known static pruning method for search engine indices. In addition, since our technique is orthogonal to the underlying search algorithms, it can be adopted by virtually any search engine.

This short paper presents a light weight technique to merge results lists obtained from querying different databases. The motivation for such a technique is a general purpose search engine for Palm-OS based PDAs.

This paper presents \bic (Border/Interior pixel Classification), a compact and efficient CBIR approach suitable for broad image domains. It has three main components: (1) a simple and powerful image analysis algorithm that classifies image pixels as either border or interior, (2) a new logarithmic distance (dLog) for comparing histograms, and (3) a compact representation for the visual features extracted from images. Experimental results show that the BIC approach is consistently more compact, more efficient and more effective than state-of-the-art CBIR approaches based on sophisticated image analysis algorithms and complex distance functions. It was also observed that the dLog distance function has two main advantages over vectorial distances (e.g., L1): (1) it is able to increase substantially the effectiveness of (several) histogram-based CBIR approaches and, at the same time, (2) it reduces by 50% the space requirement to represent a histogram.

The authors present a novel content based image retrieval (CBIR) approach, for image databases, based on cluster analysis. CBIR relies on the representation (metadata) of images' visual content. In order to produce such metadata, we propose an efficient and adaptive clustering algorithm to segment the images into regions of high similarity. This approach contrasts with those that use a single color histogram for the whole image (global methods), or local color histograms for a fixed number of image cells (partition based methods). Our experimental results show that our clustering approach offers high retrieval effectiveness with low space overhead. For example, using a database of 20000 images, we obtained higher retrieval effectiveness than partition based methods with about the same space overhead of global methods, which are typically regarded as storage-wise compact.

We present an approach, named MAP21, which uses standard B/sup +/-trees to provide efficient indexing of valid time ranges. The MAP21 approach is based on mapping one dimensional ranges to one dimensional points where the lexicographical order among the ranges is preserved. The proposed approach may employ more than one tree, each indexing a disjoint subset of the indexed data. When compared to the Time Index and the B/sup +/-tree we show that MAP21's performance is comparable to or better than those, depending on the type of query. In terms of storage, MAP21's structure was less than 10 percent larger than the B/sup +/-tree's and much smaller than the Time Index's. The main contribution of this paper though, is to show that standard B/sup +/-trees, available in virtually any DBMS, can be used to provide an efficient temporal index.

Stemming is a technique which aims to extract common suffixes of words. Thus, words which are literally different but have a common stem, may be abstracted by their common stem. The underlying goal when using a stemming technique is to improve recall, at the possible expense of precision loss. A well known technique for stemming text is M.F. Porter's (1980) algorithm, which is based on a set of rules extracted from the English language. We argue that such an algorithm it is not efficient for non traditional texts, e.g., one made up mainly of medical terms. We thus investigate the use of a technique, called Peak-and-Plateau, which is based on tries, and compare it to Porter's algorithm. Our experiments have shown that using Porter's algorithm or none at all makes no difference as far as precision and recall goes. On the other hand using the Peak-and-Plateau technique we improved recall by about 15% and decreased precision by an average of 40%. Moreover it compressed the original text by 40% and the invented file by 45%.

There is a wide range of scientific applications requiring sophisticated management of spatio-temporal data. However existing database management systems offer very limited support for managing such data. Thus, it is left to the researchers themselves to repeatedly code this management into each application. We present an extensible framework, based on extending an object-oriented database system, with kernel spatio-temporal classes, data structures and functions, to provide support for the development of spatio-temporal applications.

We propose an indexing structure for bitemporal databases. Such structure is based on two trees, one indexing valid time and another indexing transaction time. The trees share pointers to the actual data records, which are thus not duplicated. Bitemporal queries are processed by dividing the query in two parts, a valid time part and a transaction time part. Each tree is searched according to these partial queries, and the answer is determined by the correct composition of the partial answers. We show how simple coordination of the tree searching, along with a simple assumption on the temporal data, improves query processing performance. The proposed structure also allows querying either time dimension, separately from the other one.