On the Minimization of Communication in Networked Systems with a Central Station

The problem of minimizing communication in a distributed networked system is considered in a discrete-event formalism where the system is modeled as a finite-state automaton. The system consists of a central station and a set of N local agents, each observing a set of local events. The central station needs to know exactly the state of the system, whereas local agents need to disambiguate certain pre-specified pairs of states for purposes of control or diagnosis. This requirement is achieved by communication, which occurs only between the central station and the local agents but not among the local agents. A communication policy is defined as a set of event occurrences to be communicated between the central station and the local agents. A communication policy is said to be minimal if any removal of communication of event occurrences will affect the correctness of the solution. Under an assumption on the absence of cycles (other than self-loops) in the system model, this paper presents an algorithm that computes a minimal communication policy in polynomial time in all parameters of the system. These results improve upon previous algorithms for solving minimum communication problems.

Partially Observable Markov Decision Process Approximations for Adaptive Sensing

Adaptive sensing involves actively managing sensor resources to achieve a sensing task, such as object detection, classification, and tracking, and represents a promising direction for new applications of discrete event system methods. We describe an approach to adaptive sensing based on approximately solving a partially observable Markov decision process (POMDP) formulation of the problem. Such approximations are necessary because of the very large state space involved in practical adaptive sensing problems, precluding exact computation of optimal solutions. We review the theory of POMDPs and show how the theory applies to adaptive sensing problems. We then describe a variety of approximation methods, with examples to illustrate their application in adaptive sensing. The examples also demonstrate the gains that are possible from nonmyopic methods relative to myopic methods, and highlight some insights into the dependence of such gains on the sensing resources and environment.

Optimal Node Visitation in Acyclic Stochastic Digraphs with Multi-threaded Traversals and Internal Visitation Requirements

The original definition of the problem of optimal node visitation (ONV) in acyclic stochastic digraphs concerns the identification of a routing policy that will enable the visitation of each leaf node a requested number of times, while minimizing the expected number of the graph traversals. The original work of Bountourelis and Reveliotis (2006) formulated this problem as a Stochastic Shortest Path (SSP) problem, and since the state space of this SSP formulation is exponentially sized with respect to the number of the target nodes, it also proposed a suboptimal policy that is computationally tractable and asymptotically optimal. This paper extends the results of Bountourelis and Reveliotis (2006) to the cases where (i) the tokens traversing the graph can “split” during certain transitions to a number of (sub-)tokens, allowing, thus, the satisfaction of many visitation requirements during a single graph traversal, and (ii) there are additional visitation requirements attached to the internal graph nodes, which, however, can be served only when the visitation requirements of their successors have been fully met. In addition, the presented set of results establishes stronger convergence properties for the proposed suboptimal policies, and it provides a formal complexity analysis of the considered ONV formulations. From a practical standpoint, the extension of the original results performed in this paper enables their effective usage in the application domains that motivated the ONV problem, in the first place.

A New Learning Algorithm for Optimal Stopping

A linear programming formulation of the optimal stopping problem for Markov decision processes is approximated using linear function approximation. Using this formulation, a reinforcement learning scheme based on a primal-dual method and incorporating a sampling device called ‘split sampling’ is proposed and analyzed. An illustrative example from option pricing is also included.

Backward Coupling in Bounded Free-Choice Nets Under Markovian and Non-Markovian Assumptions

In this paper, we show how to design a perfect sampling algorithm for stochastic Free-Choice Petri nets by backward coupling. For Markovian event graphs, the simulation time can be greatly reduced by using extremal initial states, namely blocking marking, although such nets do not exhibit any natural monotonicity property. Another approach for perfect simulation of non-Markovian event graphs is based on a (max,plus) representation of the system and the theory of (max,plus) stochastic systems. We also show how to extend this approach to one-bounded free choice nets to the expense of keeping all states. Finally, experimental runs show that the (max,plus) approach needs a larger simulation time than the Markovian approach.

Creating ambient music spaces in real and virtual worlds

Sound and, specifically, music is a medium that is used for a wide range of purposes in different situations in very different ways. Ways for music selection and consumption range from completely passive, almost unnoticed perception of background sound environments to the very specific selection of a particular recording of a piece of music with a specific orchestra and conductor at a certain event. Different systems and interfaces exist for the broad range of needs in music consumption. Locating a particular recording is well supported by traditional search interfaces via metadata. Other interfaces support the automatic creation of playlists via artist or album selection, up to more artistic installations of sound environments that users can navigate through. In this paper we present a set of systems that support the creation of as well as the navigation in musical spaces, both in the real world as well as in virtual environments. We show common principles and point out further directions for a more direct coupling of the various spaces and interaction methods, creating ambient sound environments and providing organic interaction with music for different purposes.

State Observer for DES Under Partial Observation with Time Petri Nets

This paper deals with a state observation approach for Discrete Event Systems with a known behavior. The system behavior is modeled using a Time Petri Net model. The proposed approach exploits temporal constraints to assess the system state and therefore detect and determine faults given partial observability of events. The goal here is to track the system state and to identify the event scenarios which occur on the system. Our approach uses the class graph of the Time Petri Net which models the complete system behavior to develop a state observer which is a base to perform online fault detection and diagnosing.

Using visual and text features for direct marketing on multimedia messaging services domain

Traditionally, direct marketing companies have relied on pre-testing to select the best offers to send to their audience. Companies systematically dispatch the offers under consideration to a limited sample of potential buyers, rank them with respect to their performance and, based on this ranking, decide which offers to send to the wider population. Though this pre-testing process is simple and widely used, recently the industry has been under increased pressure to further optimize learning, in particular when facing severe time and learning space constraints. The main contribution of the present work is to demonstrate that direct marketing firms can exploit the information on visual content to optimize the learning phase. This paper proposes a two-phase learning strategy based on a cascade of regression methods that takes advantage of the visual and text features to improve and accelerate the learning process. Experiments in the domain of a commercial Multimedia Messaging Service (MMS) show the effectiveness of the proposed methods and a significant improvement over traditional learning techniques. The proposed approach can be used in any multimedia direct marketing domain in which offers comprise both a visual and text component.

Control of Parameterized Discrete Event Systems

This paper investigates the control of parameterized discrete event systems when specifications are given in terms of predicates and satisfy a similarity assumption. This study is motivated by a weakness in current synthesis methods that do not scale well to huge systems. For systems consisting of similar processes under total or partial observation, conditions are given to deduce properties of a system of n processes (arbitrary size) from properties of a system of n ₀ processes (bounded size), with n ≥ n ₀. Furthermore, it is shown how to infer a control policy for the former from the latter’s, while taking into account interconnections between processes.

PatchPeer: A scalable video-on-demand streaming system in hybrid wireless mobile peer-to-peer networks

Video-on-demand service in wireless networks is one important step to achieving the goal of providing video services anywhere anytime. Typically, carrier mobile networks are used to deliver videos wirelessly. Since every video stream comes from the base station, regardless of what bandwidth sharing techniques are being utilized, the media stream system is still limited by the network capacity of the base station. The key to overcome the scalability issue is to exploit resources available at mobile clients in a peer-to-peer setting. We observe that it is common to have a carrier mobile network and a mobile peer-to-peer network co-exist in a wireless environment. A feature of such hybrid environment is that the former offers high availability assurance, while the latter presents an opportunistic use of resources available at mobile clients. Our proposed video-on-demand technique, PatchPeer, leverages this network characteristic to allow the video-on-demand system scale beyond the bandwidth capacity of the server. Mobile clients in PatchPeer are no longer passive receivers, but also active senders of video streams to other mobile clients. Our extensive performance study shows that PatchPeer can accept more clients than the current state-of-the-art technique, while maintaining the same Quality-of-Service to clients.

Web data retrieval: solving spatial range queries using k-nearest neighbor searches

As Geographic Information Systems (GIS) technologies have evolved, more and more GIS applications and geospatial data are available on the web. Spatial objects in a given query range can be retrieved using spatial range query − one of the most widely used query types in GIS and spatial databases. However, it can be challenging to retrieve these data from various web applications where access to the data is only possible through restrictive web interfaces that support certain types of queries. A typical scenario is the existence of numerous business web sites that provide their branch locations through a limited “nearest location” web interface. For example, a chain restaurant’s web site such as McDonalds can be queried to find some of the closest locations of its branches to the user’s home address. However, even though the site has the location data of all restaurants in, for example, the state of California, it is difficult to retrieve the entire data set efficiently due to its restrictive web interface. Considering that k-Nearest Neighbor (k-NN) search is one of the most popular web interfaces in accessing spatial data on the web, this paper investigates the problem of retrieving geospatial data from the web for a given spatial range query using only k-NN searches. Based on the classification of k-NN interfaces on the web, we propose a set of range query algorithms to completely cover the rectangular shape of the query range (completeness) while minimizing the number of k-NN searches as possible (efficiency). We evaluated the efficiency of the proposed algorithms through statistical analysis and empirical experiments using both synthetic and real data sets.

Ordinal Optimization and Quantification of Heuristic Designs

This paper focuses on the performance evaluation of complex man-made systems, such as assembly lines, electric power grid, traffic systems, and various paper processing bureaucracies, etc. For such problems, applying the traditional optimization tool of mathematical programming and gradient descent procedures of continuous variables optimization are often inappropriate or infeasible, as the design variables are usually discrete and the accurate evaluation of the system performance via a simulation model can take too much calculation. General search type and heuristic methods are the only two methods to tackle the problems. However, the “goodness” of heuristic methods is generally difficult to quantify while search methods often involve extensive evaluation of systems at many design choices in a large search space using a simulation model resulting in an infeasible computation burden. The purpose of this paper is to address these difficulties simultaneously by extending the recently developed methodology of Ordinal Optimization (OO). Uniform samples are taken out from the whole search space and evaluated with a crude but computationally easy model when applying OO. And, we argue, after ordering via the crude performance estimates, that the lined-up uniform samples can be seen as an approximate ruler. By comparing the heuristic design with such a ruler, we can quantify the heuristic design, just as we measure the length of an object with a ruler. In a previous paper we showed how to quantify a heuristic design for a special case but we did not have the OO ruler idea at that time. In this paper we propose the OO ruler idea and extend the quantifying method to the general case and the multiple independent results case. Experimental results of applying the ruler are also given to illustrate the utility of this approach.

Analyzing the efficacy of using digital ink devices in a learning environment

There has been increased interest on the impact of mobile devices such as PDAs and Tablet PCs in introducing new pedagogical approaches and active learning experiences. We propose an intelligent system that efficiently addresses the inherent subjectivity in student perception of note taking and information retrieval. We employ the idea of cross indexing the digital ink notes with matching electronic documents in the repository. Latent Semantic Indexing is used to perform document and page level indexing. Thus for each retrieved document, the user can go over to the relevant pages that match the query. Techniques to handle problems such as polysemy (multiple meanings of a word) in large databases, document folding and no match for query are discussed. We tested our system for its performance, usability and effectiveness in the learning process. The results from the exploratory studies reveal that the proposed system provides a highly enhanced student learning experience, thereby facilitating high test scores.

Automatically and Accurately Conflating Raster Maps with Orthoimagery

Recent growth of geospatial information online has made it possible to access various maps and orthoimagery. Conflating these maps and imagery can create images that combine the visual appeal of imagery with the attribution information from maps. The existing systems require human intervention to conflate maps with imagery. We present a novel approach that utilizes vector datasets as “glue” to automatically conflate street maps with imagery. First, our approach extracts road intersections from imagery and maps as control points. Then, it aligns the two point sets by computing the matched point pattern. Finally, it aligns maps with imagery based on the matched pattern. The experiments show that our approach can conflate various maps with imagery, such that in our experiments on TIGER-maps covering part of St. Louis county, MO, 85.2% of the conflated map roads are within 10.8 m from the actual roads compared to 51.7% for the original and georeferenced TIGER-map roads.

Theory of relative defect proneness

In this study, we investigated the functional form of the size-defect relationship for software modules through replicated studies conducted on ten open-source products. We consistently observed a power-law relationship where defect proneness increases at a slower rate compared to size. Therefore, smaller modules are proportionally more defect prone. We externally validated the application of our results for two commercial systems. Given limited and fixed resources for code inspections, there would be an impressive improvement in the cost-effectiveness, as much as 341% in one of the systems, if a smallest-first strategy were preferred over a largest-first one. The consistent results obtained in this study led us to state a theory of relative defect proneness (RDP): In large-scale software systems, smaller modules will be proportionally more defect-prone compared to larger ones. We suggest that practitioners consider our results and give higher priority to smaller modules in their focused quality assurance efforts.

Advances in GML for Geospatial Applications

This paper presents a study of Geography Markup Language (GML), the issues that arise from using GML for spatial applications, including storage, parsing, querying and visualization, as well as the use of GML for mobile devices and web services. GML is a modeling language developed by the Open Geospatial Consortium (OGC) as a medium of uniform geographic data storage and exchange among diverse applications. Many new XML-based languages are being developed as open standards in various areas of application. It would be beneficial to integrate such languages with GML during the developmental stages, taking full advantage of a non-proprietary universal standard. As GML is a relatively new language still in development, data processing techniques need to be refined further in order for GML to become a more efficient medium for geospatial applications.

Optimizing two-pass connected-component labeling algorithms

We present two optimization strategies to improve connected-component labeling algorithms. Taking together, they form an efficient two-pass labeling algorithm that is fast and theoretically optimal. The first optimization strategy reduces the number of neighboring pixels accessed through the use of a decision tree, and the second one streamlines the union-find algorithms used to track equivalent labels. We show that the first strategy reduces the average number of neighbors accessed by a factor of about 2. We prove our streamlined union-find algorithms have the same theoretical optimality as the more sophisticated ones in literature. This result generalizes an earlier one on using union-find in labeling algorithms by Fiorio and Gustedt (Theor Comput Sci 154(2):165–181, 1996). In tests, the new union-find algorithms improve a labeling algorithm by a factor of 4 or more. Through analyses and experiments, we demonstrate that our new two-pass labeling algorithm scales linearly with the number of pixels in the image, which is optimal in computational complexity theory. Furthermore, the new labeling algorithm outperforms the published labeling algorithms irrespective of test platforms. In comparing with the fastest known labeling algorithm for two-dimensional (2D) binary images called contour tracing algorithm, our new labeling algorithm is up to ten times faster than the contour tracing program distributed by the original authors.

Automatic and Accurate Extraction of Road Intersections from Raster Maps

Since maps are widely available for many areas around the globe, they provide a valuable resource to help understand other geospatial sources such as to identify roads or to annotate buildings in imagery. To utilize the maps for understanding other geospatial sources, one of the most valuable types of information we need from the map is the road network, because the roads are common features used across different geospatial data sets. Specifically, the set of road intersections of the map provides key information about the road network, which includes the location of the road junctions, the number of roads that meet at the intersections (i.e., connectivity), and the orientations of these roads. The set of road intersections helps to identify roads on imagery by serving as initial seed templates to locate road pixels. Moreover, a conflation system can use the road intersections as reference features (i.e., control point set) to align the map with other geospatial sources, such as aerial imagery or vector data. In this paper, we present a framework for automatically and accurately extracting road intersections from raster maps. Identifying the road intersections is difficult because raster maps typically contain much information such as roads, symbols, characters, or even contour lines. We combine a variety of image processing and graphics recognition methods to automatically separate roads from the raster map and then extract the road intersections. The extracted information includes a set of road intersection positions, the road connectivity, and road orientations. For the problem of road intersection extraction, our approach achieves over 95% precision (correctness) with over 75% recall (completeness) on average on a set of 70 raster maps from a variety of sources.

Periodicity and stability issues of a <Emphasis Type="Italic">chaotic</Emphasis> pattern recognition neural network

Traditional pattern recognition (PR) systems work with the model that the object to be recognized is characterized by a set of features, which are treated as the inputs. In this paper, we propose a new model for PR, namely one that involves chaotic neural networks (CNNs). To achieve this, we enhance the basic model proposed by Adachi (Neural Netw 10:83–98, 1997), referred to as Adachi’s Neural Network (AdNN), which though dynamic, is not chaotic. We demonstrate that by decreasing the multiplicity of the eigenvalues of the AdNN’s control system, we can effectively drive the system into chaos. We prove this result here by eigenvalue computations and the evaluation of the Lyapunov exponent. With this premise, we then show that such a Modified AdNN (M-AdNN) has the desirable property that it recognizes various input patterns. The way that this PR is achieved is by the system essentially sympathetically “resonating” with a finite periodicity whenever these samples (or their reasonable resemblances) are presented. In this paper, we analyze the M-AdNN for its periodicity, stability and the length of the transient phase of the retrieval process. The M-AdNN has been tested for Adachi’s dataset and for a real-life PR problem involving numerals. We believe that this research also opens a host of new research avenues. Research partially supported by the Natural Sciences and Engineering Research Council of Canada.

---