To increase the efficiency of interest-point based object retrieval, researchers have put remarkable research efforts into improving the efficiency of kNN-based feature matching, pursuing to match thousands of features against a database within fractions of a second. However, due to the high-dimensional nature of image features that reduces the effectivity of index structures (curse of dimensionality) and due to the vast amount of features stored in image databases (images are often represented by up to several thousand features), this ultimate goal demanded to trade kNN query runtimes for query precision. In this paper we address an approach complementary to indexing in order to improve the efficiency of retrieval by querying only the most promising keypoint descriptors, as this affects kNN matching time linearly. As this reduction of kNN queries reduces the number of tentative correspondences, a loss of query precision is minimized by an additional image-level correspondence generation stage with a computational performance independent of the underlying indexing structure. Our experimental evaluation suggests good performance on a variety of datasets.

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.

The always increasing number of videos on the internet yield data for novel quite useful multimedial service applications, but finding videos best satisfying the users need is becoming challenging. At the same time, new video collection platforms allow to upload videos enriched with positional metadata when recorded with a GPS-enabled device such as a smartphone. These platforms can thus go beyond the prevalent keyword search and instead take advantage from the positional metadata of videos, e.g., to find videos recorded in a certain area. This information, however allows for much more interesting queries. In this paper we present Video Route which allows a user to specify a target route (query) and obtain an approximation of the target route that is piecewise composed of subtrajectories derived from a set of given trajectories. Our approach is aimed at high approximation accuracy while keeping the number of composed subtrajectories low.

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.

This demonstration presents our Uncertain-Spatio-Temporal (UST)} framework that we have developed in recent years. The framework allows not only to visualize and explore spatio-temporal data consisting of (location, time, object)-triples but also provides an extensive codebase easily extensible and customizable by developers and researchers. The main research focus of this UST-framework is the explicit consideration of uncertainty, an aspect that is inherent in spatio-temporal data, due to infrequent position updates, due to physical limitations and due to power constraints. The UST-framework can be used to obtain a deeper intuition of the quality of spatio-temporal data models. Such models aim at estimating the position of a spatio-temporal object at a time where the object's position is not explicitly known, for example by using both historic (traffic-) pattern information, and by using explicit observations of objects. The UST-framework illustrates the resulting distributions by allowing a user to move forward and backward in time. Additionally the framework allows users to specify simple spatio-temporal queries, such as spatio-temporal window queries and spatio-temporal nearest neighbor (NN) queries. Based on recently published theoretic concepts, the UST-framework allows to visually explore the impact of different models and parameters on spatio-temporal data. The main result showcased by the UST-framework is a minimization of uncertainty by employing stochastic processes, leading to small expected distances between ground truth trajectories and modelled positions.

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.

Most algorithms treat Wireless Sensor Networks (WSNs) only as a generator of data without any autonomy. In contrast to this approach, we propose the ACIDE framework: A completely decentralized, bottom-up clustering process and information exchange that does not depend on given infrastructure such as fixed root nodes. While it has slightly higher requirements for the nodes, its dynamic and independent nature has many advantages, such as the user beeing able to initiate queries from any point in the network rather than being limited to query the network through an a priori fixed sink node. The framework can deal with changing environments and energy depletion. Through careful abstraction, we also support customization and adaption to different environments.

Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their applications in spatio-temporal data analysis. More recent work has considered the realistic case where the trajectories are uncertain; however, only simple uncertainty models have been proposed, which do not allow for accurate probabilistic search. In this paper, we fill this gap by addressing probabilistic nearest neighbor queries in databases with uncertain trajectories modeled by stochastic processes, specifically the Markov chain model. We study three nearest neighbor query semantics that take as input a query state or trajectory q and a time interval, and theoretically evaluate their runtime complexity. Furthermore we propose a sampling approach which uses Bayesian inference to guarantee that sampled trajectories conform to the observation data stored in the database. This sampling approach can be used in Monte-Carlo based approximation solutions. We include an extensive experimental study to support our theoretical results.

This demo presents a framework for running probabilistic graph queries on uncertain graphs and visualizing their results. The framework supports the most common uncertainty model for uncertain graphs, i.e. existential uncertainty for the edges of the graph. A large variety of meaningful graph queries are supported, such as shortest path, range, kN, reverse kN, reachability and various aggregation queries. Since the problem of exact probability computation according to possible world semantics is in #P-Time for many combinations of model and query, and since ignoring uncertainty (e.g. by using expectations only) will yield counterintuitive and hard to interpret results, our framework uses an optimized version of Monte-Carlo sampling to estimate the results which allows us not only to perform queries that conform to possible world semantics but also to sample only parts of a graph relevant for a given query. The main strength of this framework is the visualization combined with statistic hypothesis tests, which gives the user not only the estimated result of a query, but also an indication of how significant and reliable these results are. The aim of this demonstration is to give an intuition that a sampling based approach to probabilistic graphs is viable, and that the estimated results quickly converge even for very large graphs. A video demonstrating our framework can be downloaded at http://www.dbs.ifi.lmu.de/Publikationen/videos/PGraph.html

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.