MedSMan: a live multimedia stream querying system

Querying live media streams is a challenging problem that is becoming an essential requirement in a growing number of applications. Research in multimedia information systems has addressed and made good progress in dealing with archived data. Meanwhile, research in stream databases has received significant attention for querying alphanumeric symbolic streams. The lack of a data model capable of representing different multimedia data in a declarative way, hiding the media heterogeneity and providing reasonable abstractions for querying live multimedia streams poses the challenge of how to make the best use of data in video, audio and other media sources for various applications. In this paper we propose a system that enables directly capturing media streams from sensors and automatically generating more meaningful feature streams that can be queried by a data stream processor. The system provides an effective combination between extendible digital processing techniques and general data stream management research. Together with other query techniques developed in related data stream management streams, our system can be used in those application areas where multifarious live media senors are deployed for surveillance, disaster response, live conferencing, telepresence, etc.

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

A universal topological transformation group inL 2 (G × G)

LetG denote an infinite,-compact, locally compact topological group. In this paper a construction is given for a topological transformation groupH _G with the Hilbert spaceL ² (G × G) as a phase space such that any topological transformation group (G, X, ) can be embedded inH _G , providedX is a separable metrizable space and is a bounded action. The class of such topological transformation groups contains all actions ofG on separable, metrizable, locally compact spaces.     

InterViso: Dealing with the complexity of federated database access

Connectivity products are finally available to provide the highways between computers containing data. IBM has provided strong validation of the concept with their Information Warehouse. DBMS vendors are providing gateways into their products, and SQL is being retrofitted on many older DBMSs to make it easier to access data from standard 4GL products and application development systems. The next step needed for data integration is to provide (1) a common data dictionary with a conceptual schema across the data to mask the many differences that occur when databases are developed independently and (2) a server that can access and integrate the databases using information from the data dictionary. In this article, we discuss InterViso, one of the first commercial federated database products. InterViso is based on Mermaid, which was developed at SDC and Unisys (Templeton et al., 1987b). It provides a value added layer above connectivity products to handle views across databases, schema translation, and transaction management.     

Self-organizing neural networks for the analysis and representation of data: Some financial cases

Many recent papers have dealt with the application of feedforward neural networks in financial data processing. This powerful neural model can implement very complex nonlinear mappings, but when outputs are not available or clustering of patterns is required, the use of unsupervised models such as self-organizing maps is more suitable. The present work shows the capabilities of self-organizing feature maps for the analysis and representation of financial data and for aid in financial decision-making. For this purpose, we analyse the Spanish banking crisis of 1977–1985 and the Spanish economic situation in 1990 and 1991, making use of this unsupervised model. Emphasis is placed on the analysis of the synaptic weights, fundamental for delimiting regions on the map, such as bankrupt or solvent regions, where similar companies are clustered. The time evolution of the companies and other important conclusions can be drawn from the resulting maps.Characters and symbols used and their meaning nx x dimension of the neuron grid, in number of neurons - ny y dimension of the neuron grid, in number of neurons - n dimension of the input vector, number of input variables - (i, j) indices of a neuron on the map - k index of the input variables - w _ijk synaptic weight that connects thek input with the (i, j) neuron on the map - W _ij weight vector of the (i, j) neuron - x _k input vector - X input vector - (t) learning rate - _o starting learning rate - _f final learning rate - R(t) neighbourhood radius - R₀ starting neighbourhood radius - R _f final neighbourhood radius - t iteration counter - t _rf number of iterations until reachingR _f - t _f number of iterations until reaching _f - h(·) lateral interaction function - standard deviation - for every - d (x, y) distance between the vectors x and y     

Local determinacy of abstract local dynamical systems

O. Hájek proved in his book Dynamical Systems in the Plane (Chapter III) that there isat most one abstract local dynamical system which is locally equivalent to, or equivalently an extension of, a given elementary dynamical system, and suggested a question of finding reasonable conditions on the latter for the existence ofat least one such abstract local dynamical system. An elementary dynamical system is said to satisfy the No-Intersection Axiom and is called an abstract germ if(x ₁, t) = (x ₂,t) impliesx ₁ =x ₂. We show that is (uniquely) extendable to an abstract local dynamical system if and only if is an abstract germ, and hence the question is completely answered. After introducing various kinds of isomorphisms of abstract germs and abstract local dynamical systems corresponding to those of continuous germs and continuous local dynamical systems, we obtain some sufficient conditions for extendability of isomorphisms and possibility of restriction of them, and thus establish the local determinacy of abstract local dynamical systems up to isomorphisms in some wider categories.Dedicated to Professor Yusuke HAGIHARA in Commemoration of His Seventy-Seventh Anniversary     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

Constructing H4, a Fast Depth-Size Optimal Parallel Prefix Circuit

Given n values x ₁, x ₂,...,x _n and an associative binary operation , the prefix problem is to compute x ₁x ₂x _i, 1in. Prefix circuits are combinational circuits for solving the prefix problem. For any n-input prefix circuit D with depth d and size s, if d+s=2n–2, then D is depth-size optimal. In general, a prefix circuit with a small depth is faster than one with a large depth. For prefix circuits with the same depth, a prefix circuit with a smaller fan-out occupies less area and is faster in VLSI implementation. This paper is on constructing parallel prefix circuits that are depth-size optimal with small depth and small fan-out. We construct a depth-size optimal prefix circuit H4 with fan-out 4. It has the smallest depth among all known depth-size optimal prefix circuits with a constant fan-out; furthermore, when n136, its depth is less than, or equal to, those of all known depth-size optimal prefix circuits with unlimited fan-out. A size lower bound of prefix circuits is also derived. Some properties related to depth-size optimality and size optimality are introduced; they are used to prove that H4 is depth-size optimal.     

A forbidden subposet characterization of an order — dimension inequality

Dushnik and Miller defined the dimension of a partially ordered setX, DimX, as the minimum number of linear extensions ofX whose intersection is the partial ordering onX. The concept of dimension for a partially ordered set has applications to preference structures and the theory of measurement. Hiraguchi proved that DimX [|X|/2] when |X| 4. Bogart, Trotter, and Kimble gave a forbidden subposet characterization of Hiraguchi's inequality by constructing for eachn 2 the minimum collection _n of posets such that if [|X|/2] =n 2, then DimX < n unlessX contains one of the posets in _n . Recently Trotter gave a simple proof of Hiraguchi's inequality based on the following theorem. IfA is an antichain ofX and |X – A| =n 2, then DimX n. In this paper we give a forbidden subposet characterization of this last inequality.     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.