Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity

One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (CKNN) query. A CKNN query is to retrieve the K-nearest neighbors (KNNs) of a moving user at each time instant within a user-given time interval [t _s , t _e ]. In this paper, we investigate how to process a CKNN query efficiently. Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed velocity, by allowing that the velocity of the object can vary within a known range. Due to the introduction of this uncertainty on the velocity of each object, processing a CKNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P² KNN algorithm to find the objects that could be the KNNs at each time instant within the given query time interval. Besides, a probability-based model is designed to quantify the possibility of each object being one of the KNNs. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed approach.

Moving objects forecast in image sequences using autoregressive algorithms

The objective of this paper is to present an overall approach to forecasting the future position of the moving objects of an image sequence after processing the images previous to it. The proposed method makes use of classical techniques such as optical flow to extract objects’ trajectories and velocities, and autoregressive algorithms to build the predictive model. Our method can be used in a variety of applications, where videos with stationary cameras are used, moving objects are not deformed and change their position with time. One of these applications is traffic control, which is used in this paper as a case study with different meteorological conditions to compare with.

Inverse multi-objective robust evolutionary design

In this paper, we present an Inverse Multi-Objective Robust Evolutionary (IMORE) design methodology that handles the presence of uncertainty without making assumptions about the uncertainty structure. We model the clustering of uncertain events in families of nested sets using a multi-level optimization search. To reduce the high computational costs of the proposed methodology we proposed schemes for (1) adapting the step-size in estimating the uncertainty, and (2) trimming down the number of calls to the objective function in the nested search. Both offline and online adaptation strategies are considered in conjunction with the IMORE design algorithm. Design of Experiments (DOE) approaches further reduce the number of objective function calls in the online adaptive IMORE algorithm. Empirical studies conducted on a series of test functions having diverse complexities show that the proposed algorithms converge to a set of Pareto-optimal design solutions with non-dominated nominal and robustness performances efficiently.

---

Adaptation and application of multi-objective evolutionary algorithms for rule reduction and parameter tuning of fuzzy rule-based systems

Recently, multi-objective evolutionary algorithms have been applied to improve the difficult tradeoff between interpretability and accuracy of fuzzy rule-based systems. It is known that both requirements are usually contradictory, however, these kinds of algorithms can obtain a set of solutions with different trade-offs. This contribution analyzes different application alternatives in order to attain the desired accuracy/interpr-etability balance by maintaining the improved accuracy that a tuning of membership functions could give but trying to obtain more compact models. In this way, we propose the use of multi-objective evolutionary algorithms as a tool to get almost one improved solution with respect to a classic single objective approach (a solution that could dominate the one obtained by such algorithm in terms of the system error and number of rules). To do that, this work presents and analyzes the application of six different multi-objective evolutionary algorithms to obtain simpler and still accurate linguistic fuzzy models by performing rule selection and a tuning of the membership functions. The results on two different scenarios show that the use of expert knowledge in the algorithm design process significantly improves the search ability of these algorithms and that they are able to improve both objectives together, obtaining more accurate and at the same time simpler models with respect to the single objective based approach.

---

A Schedule-based Pathfinding Algorithm for Transit Networks Using Pattern First Search

The lack of effective and efficient schedule-based pathfinding algorithms for transit networks has limited the application of GIS in transit trip planning services. This paper introduces a schedule-based path finding algorithm for transit networks. Based on a pattern-centered spatiotemporal transit network model, the algorithm searches the network by following route patterns. A pattern is a spatial layout of a route in transit terminology. A route usually has many patterns to serve various locations at different times. This path search algorithm is significantly different from traditional shortest path algorithms that are based on adjacent node search. By establishing a set of lemmas and theorems the paper proves that paths generated by the PFS algorithm are schedule-coordinated fastest paths for trips with given constraints. After analyzing computation and database query complexities of the algorithm the paper indicates that the PFS is efficient in computation and database query. Finally, effectiveness and efficiency of the algorithm are demonstrated by implementations in GIS-based online transit trip planners in Wisconsin, US.

Real-time stabilization of long range observation system turbulent video

The paper presents a real-time algorithm that compensates image distortions due to atmospheric turbulence in video sequences, while keeping the real moving objects in the video unharmed. The algorithm involves (1) generation of a “reference” frame, (2) estimation, for each incoming video frame, of a local image displacement map with respect to the reference frame, (3) segmentation of the displacement map into two classes: stationary and moving objects; (4) turbulence compensation of stationary objects. Experiments with both simulated and real-life sequences have shown that the restored videos, generated in real-time using standard computer hardware, exhibit excellent stability for stationary objects while retaining real motion.

A multiscale approach to texture-based image retrieval

This paper presents research on a robust technique for texture-based image retrieval in multimedia museum collections. The aim is to be able to use a query image patch containing a single texture to retrieve images containing an area with similar texture to that in the query. The feature extractor used to build the feature vectors is based on an improved version of the discrete wavelet frames (DWF), proposed elsewhere. In order to utilise the feature extractor on real scene image datasets, a block-oriented decomposition technique, termed the multiscale sub-image matching method, is presented. The multiscale method, together with the DWF, provide an efficient content-based retrieval technique without the need for segmentation. The algorithms are tested on a range of databases of texture images as well as on real museum image collections. Promising results are reported.

A coherent query language for XML

Text search engines are inadequate for indexing and searching XML documents because they ignore metadata and aggregation structure implicit in the XML documents. On the other hand, the query languages supported by specialized XML search engines are very complex. In this paper, we present a simple yet flexible query language, and develop its semantics to enable intuitively appealing extraction of relevant fragments of information while simultaneously falling back on retrieval through plain text search if necessary. Our approach combines and generalizes several available techniques to obtain precise and coherent results.

Exploiting maximal redundancy to optimize SQL queries

Detecting and dealing with redundancy is an ubiquitous problem in query optimization, which manifests itself in many areas of research such as materialized views, multi-query optimization, and query-containment algorithms. In this paper, we focus on the issue of intra-query redundancy, redundancy present within a query. We present a method to detect the maximal redundancy present between a main (outer) query block and a subquery block. We then use the method for query optimization, introducing query plans and a new operator that take full advantage of the redundancy discovered. Our approach can deal with redundancy in a wider spectrum of queries than existing techniques. We show experimental evidence that our approach works under certain conditions, and compares favorably to existing optimization techniques when applicable.

A Relative Representation of Trajectories in Geogaphical Spaces

The research presented in this paper introduces a relative representation of trajectories in space and time. The objective is to represent space the way it is perceived by a moving observer acting in the environment, and to provide a complementary view to the usual absolute vision of space. Trajectories are characterized from the perception of a moving observer where relative positions and relative velocities are the basic primitives. This allows for a formal identification of elementary trajectory configurations, and their relationships with the regions that compose the environment. The properties of the model are studied, including transitions and composition tables. These properties characterize trajectory transitions by the underlying processes that semantically qualify them. The approach provides a representation that might help the understanding of trajectory patterns in space and time.

The 2007 IEEE CEC simulated car racing competition

This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process, we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

---

Dynamic space reconfiguration for Bayesian search and tracking with moving targets

This paper presents a technique for dynamically reconfiguring search spaces in order to enable Bayesian autonomous search and tracking missions with moving targets. In particular, marine search and rescue scenarios are considered, highlighting the need for space reconfiguration in situations where moving targets are involved. The proposed technique improves the search space configuration by maintaining the validity of the recursive Bayesian estimation. The advantage of the technique is that autonomous search and tracking can be performed indefinitely, without loss of information. Numerical results first show the effectiveness of the technique with a single search vehicle and a single moving target. The efficacy of the approach for coordinated autonomous search and tracking is shown through simulation, incorporating multiple search vehicles and multiple targets. The examples also highlight the added benefit to human mission planners resulting from the technique’s simplification of the search space allocation task.

Survey on index based homology search algorithms

Up to now, there are many homology search algorithms that have been investigated and studied. However, a good classification method and a comprehensive comparison for these algorithms are absent. This is especially true for index based homology search algorithms. The paper briefly introduces main index construction methods. According to index construction methods, index based homology search algorithms are classified into three categories, i.e., length based index ones, transformation based index ones, and their combination. Based on the classification, the characteristics of the currently popular index based homology search algorithms are compared and analyzed. At the same time, several promising and new index techniques are also discussed. As a whole, the paper provides a survey on index based homology search algorithms.

Measures for Benchmarking of Automatic Correspondence Algorithms

Automatic localisation of correspondences for the construction of Statistical Shape Models from examples has been the focus of intense research during the last decade. Several algorithms are available and benchmarking is needed to rank the different algorithms. Prior work has argued that the quality of the models produced by the algorithms can be evaluated by measuring compactness, generality and specificity. In this paper severe problems with these standard measures are analysed both theoretically and experimentally both on natural and synthetic datasets. We also propose that a Ground Truth Correspondence Measure (GCM) is used for benchmarking and in this paper benchmarking is performed on several state of the art algorithms using seven real and one synthetic dataset.

Indexing Fast Moving Objects for kNN Queries Based on Nearest Landmarks

With the rapid advancements in positioning technologies such as the Global Positioning System (GPS) and wireless communications, the tracking of continuously moving objects has become more convenient. However, this development poses new challenges to database technology since maintaining up-to-date information regarding the location of moving objects incurs an enormous amount of updates. Existing indexes can no longer keep up with the high update rate while providing speedy retrieval at the same time. This study aims to improve k nearest neighbor (kNN) query performance while reducing update costs. Our approach is based on an important observation that queries usually occur around certain places or spatial landmarks of interest, called reference points. We propose the Reference-Point-based tree (RP-tree), which is a two-layer index structure that indexes moving objects according to reference points. Experimental results show that the RP-tree achieves significant improvement over the TPR-tree.

Obtaining linguistic fuzzy rule-based regression models from imprecise data with multiobjective genetic algorithms

Backfitting of fuzzy rules is an Iterative Rule Learning technique for obtaining the knowledge base of a fuzzy rule-based system in regression problems. It consists in fitting one fuzzy rule to the data, and replacing the whole training set by the residual of the approximation. The obtained rule is added to the knowledge base, and the process is repeated until the residual is zero, or near zero. Such a design has been extended to imprecise data for which the observation error is small. Nevertheless, when this error is moderate or high, the learning can stop early. In this kind of algorithms, the specificity of the residual might decrease when a new rule is added. There may happen that the residual grows so wide that it covers the value zero for all points (thus the algorithm stops), but we have not yet extracted all the information available in the dataset. Focusing on this problem, this paper is about datasets with medium to high discrepancies between the observed and the actual values of the variables, such as those containing missing values and coarsely discretized data. We will show that the quality of the iterative learning degrades in this kind of problems, because it does not make full use of all the available information. As an alternative to sequentially obtaining rules, we propose a new multiobjective Genetic Cooperative Competitive Learning (GCCL) algorithm. In our approach, each individual in the population codifies one rule, which competes in the population in terms of maximum coverage and fitting, while the individuals in the population cooperate to form the knowledge base.

---

Adaptive training of video sets for image recognition on mobile phones

We present an enhancement towards adaptive video training for PhoneGuide, a digital museum guidance system for ordinary camera-equipped mobile phones. It enables museum visitors to identify exhibits by capturing photos of them. In this article, a combined solution of object recognition and pervasive tracking is extended to a client–server-system for improving data acquisition and for supporting scale-invariant object recognition. A static as well as a dynamic training technique are presented that preprocess the collected object data differently and apply two types of neural networks (NN) for classification. Furthermore, the system enables a temporal adaptation for ensuring a continuous data acquisition to improve the recognition rate over time. A formal field experiment reveals current recognition rates and indicates the practicability of both methods under realistic conditions in a museum.

---

A survey of browsing models for content based image retrieval

The problem of content based image retrieval (CBIR) has traditionally been investigated within a framework that emphasises the explicit formulation of a query: users initiate an automated search for relevant images by submitting an image or draw a sketch that exemplifies their information need. Often, relevance feedback is incorporated as a post-retrieval step for optimising the way evidence from different visual features is combined. While this sustained methodological focus has helped CBIR to mature, it has also brought out its limitations more clearly: There is often little support for exploratory search and scaling to very large collections is problematic. Moreover, the assumption that users are always able to formulate an appropriate query is questionable. An effective, albeit much less studied, method of accessing image collections based on visual content is that of browsing. The aim of this survey paper is to provide a structured overview of the different models that have been explored over the last one to two decades, to highlight the particular challenges of the browsing approach and to focus attention on a few interesting issues that warrant more intense research.

Methods for quantitative usability requirements: a case study on the development of the user interface of a mobile phone

Quantitative usability requirements are a critical but challenging, and hence an often neglected aspect of a usability engineering process. A case study is described where quantitative usability requirements played a key role in the development of a new user interface of a mobile phone. Within the practical constraints of the project, existing methods for determining usability requirements and evaluating the extent to which these are met, could not be applied as such, therefore tailored methods had to be developed. These methods and their applications are discussed.

---