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).     

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     

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.     

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)     

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     

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.     

Cardinality problems of compositions of morphisms and inverse morphisms

We show that we cannot effectively determine whether, for morphisms _i , _i ,card (u ₀ ^–1 ₁) =card(u ₀ ^–1 ₁) for all wordsu over the domain alphabets of the two given compositions. In contrast it is decidable for morphisms _i , _i and a regular setR whethercard(u _{0 1} ^–1 ) =card(u _{0 1} ^–1 ) for all wordsu inR. In order to prove the latter result we give a characterization of the multiplicity functions of simple finite automata by using cardinalities of compositions of the above form. Finally, we show that the above decidability result also holds when we consider rational functions rather than morphisms.     

Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

We present a randomized procedure named Hierarchical Sampling from Sketches (Hss) that can be used for estimating a class of functions over the frequency vector f of update streams of the form . We illustrate this by applying the Hss technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p≥2 and for estimating the entropy of a data stream. Preliminary version of this paper appeared as the following conference publications. “Simpler algorithm for estimating frequency moments of data streams,” Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh and Chandan Saha, Proceedings of the ACM Symposium on Discrete Algorithms, 2006, pp. 708–713 and “Estimating entropy over data streams,” Lakshminath Bhuvanagiri and Sumit Ganguly, Proceedings of the European Symposium on Algorithms, LNCS, vol. 4168, pp. 148–159, Springer, 2006.     

On Steiner minimal trees withLp distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ –x ₂¦ ^p + ¦y₁ –y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio _p to be inf{L _s (P)/L _m (P)¦PL _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ₁ = 2/3. Chung and Graham proved ₂ > 0.842. We prove in this paper that {} = 2/3 and (2/2)_{12 p} 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.     

One-way multihead finite automata and 2-bounded languages

LanguagesL _n ={1 ^x 2 ^ix :i, x , 1in} were used to show that, for eachk, one-way non-sensing deterministic finite automata (1-MFA) withk+1 heads are more powerful than such automata withk heads, even if we consider only 2-bounded languages (Chrobak). Fork letf(k) be the maximal numbern such that languageL _n can be recognized by a 1-MFA withk heads. We present a precise inductive formula forf(k). It may be shown that, fork3,

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

The existence of setsnot being _tt ^P -reducible to low sets is investigated for several complexity classes such as UP, NP, the polynomial-time hierarchy, PSPACE, and EXPTIME. The p-selective sets are mainly considered as a class of low sets. Such investigations were done in many earlier works, but almost all of these have dealt withpositive reductions in order to imply the strongest consequence such as P=NP under the assumption that all sets in NP are polynomial-time reducible to low sets. Currently, there seems to be some difficulty in obtaining the same strong results undernonpositive reducibilities. The purpose of this paper is to develop a useful technique to show for many complexity classes that if each set in the class is polynomial-time reducible to a p-selective set via anonpositive reduction, then the class is already contained in P. The following results are shown in this paper.(1) If each set in UP is _tt ^P -reducible to a p-selective set, then P=UP.(2) If each set in NP is _tt ^P -reducible to a p-selective set, then P=FewP and R=NP.(3) If each set in ₂ ^P is _tt ^P -reducible to a p-selective set, then P=NP.(4) If each set in PSPACE is _tt ^P -reducible to a p-selective set, then P=PSPACE.(5) There is a set in EXPTIME that is not _tt ^P -reducible to any p-selective set.It remains open whether P=NP follows from a weaker assumption that each set in NP is _tt ^P -reducible to a p-selective set.     

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.     

Optimal embeddings of butterfly-like graphs in the hypercube

We present optimal embeddings of three genres of butterfly-like graphs in the (boolean) hypercube; each embedding is specified via a linear-time algorithm. Our first embedding finds an instance of the FFT graph as a subgraph of the smallest hypercube that is big enough to hold it; thus, we embed then-level FFT graph, which has (n+1)2 ⁿ vertices, in the (n+log₂(n+1))-dimensional hypercube, with unit dilation. This embedding yields a mapping of the pipelined FFT algorithm on the hypercube architecture, which is optimal in all resources (time, processor utilization, load balancing, etc.) and which is on-line in the sense that inputs can be added to the transform even during the computation. Second, we find optimal embeddings of then-level butterfly graph and then-level cube-connected cycles graph, each of which hasn2 ⁿ vertices, in the (n+log₂ n)-dimensional hypercube. These embeddings, too, have optimal dilation, congestion, and expansion. The dilation is 1+(n mod 2), which is best possible. Our embeddings indicate that these two bounded-degree approximations to the hypercube do not have any communication power that is not already present in the hypercube.The research of D. S. Greenberg was supported in part by NSF Grant MIP-86-01885. The research of L. S. Heath was supported in part by NSF Grant DCI-85-04308. The research of A. L. Rosenberg was supported in part by NSF Grants DCI-85-04308, DCI-87-96236, and CCR-88-12567.     

Data structures and mesh modification tools for unstructured multigrid adaptive techniques

A complete set of data structures and mesh modification tools for effectively defining unstructured threedimensional multigrids on general curved domains is presented. The mesh adaptive procedures can be used for generating hierarchies of unstructured grids by means of uniform or local refinement and coarsening, while a local retriangulation algorithm is used for controlling the degradation of the quality of the mesh during adaptation. Intergrid transfer operators are efficiently realized on the fly during adaptation. The data structure allows the efficient storage and handling of multiple grids, where mesh entities belonging to multiple levels can be stored just once. The capabilities and performance of the proposed procedures are exemplified by means of examples.Nomenclature g Geometric model - m _r Mesh model at levelr - v Domain associated with modelv (v=g,m) - (v) Boundary of modelv - Closure of domain of modelv (v(v)) - G _i ^d j Topological entityi of dimensiond _j in the geometric model - M _i ^d j _(p,q) Topological entityi of dimensiond _j in the mesh model, appearing at mesh levelsp throughq - M _i ^d j _(r) Topological entityi in the mesh model of dimensiond _j , considered at mesh levelr - (M _i ^d j) Boundary of topological entity - [·] Ordered list of entities - {·} Unordered list of entities - M _i ^d j _(r) {M ^d j} Unordered group of topological entities of dimensiond _j that are adjacent toM _i ^d j _(r) at mesh levelr - Classification, i.e. association of a topological entity with a model entity     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

The complexity of computing maximal word functions

Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [21]. By the maximal word function of a languageL ^*, we mean the problem of finding, on inputx, the lexicographically largest word belonging toL that is smaller than or equal tox.In this paper we present a parallel algorithm for computing maximal word functions for languages recognized by one-way nondeterministic auxiliary pushdown automata (and hence for the class of context-free languages).This paper is a continuation of a stream of research focusing on the problem of identifying properties others than membership which are easily computable for certain classes of languages. For a survey, see [24].     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.