Efficient similarity search for uncertain data is a challenging task in many modern data mining applications like image retrieval, speaker recognition and stock market analysis. A common way to model the uncertainty of data objects is using probability density functions in the form of Gaussian Mixture Models (GMMs), which have an ability to approximate arbitrary distribution. However, due to the possible unequal length of mixture models, the use of existing index techniques has serious problems for the objects modeled by GMMs. Either the techniques cannot handle GMMs or they have too many limitations. Hence, we propose a dynamic index structure, Gaussian Component based Index (GCI), for GMMs. GCI decomposes GMMs into the single, pairs, or n-lets of Gaussian components, stores these components into well studied index trees such as U-tree and Gauss-Tree, and refines the corresponding GMMs in a conservative but tight way. GCI supports both k-most-likely queries and probability threshold queries by means of Matching Probability. Extensive experimental evaluations of GCI demonstrate a considerable speed-up of similarity search on both synthetic and real-world data sets.

Efficient similarity search in uncertain data is a central problem in many modern applications such as biometric identification, stock market analysis, sensor networks, medical imaging, etc. In such applications, the feature vector of an object is not exactly known but is rather defined by a probability density function like a Gaussian Mixture Model (GMM). Previous work is limited to axis-parallel Gaussian distributions, hence, correlations between different features are not considered in the similarity search. In this paper, we propose a novel, efficient similarity search technique for general GMMs without independence assumption for the attributes, named SUDN, which approximates the actual components of a GMM in a conservative but tight way. A filter-refinement architecture guarantees no false dismissals, due to conservativity, as well as a good filter selectivity, due to the tightness of our approximations. An extensive experimental evaluation of SUDN demonstrates a considerable speed-up of similarity queries on general GMMs and an increase in accuracy compared to existing approaches.

The ability to deal with uncertain information is becoming increasingly important for modern database applications. Whereas a conventional (certain) object is usually represented by a vector from a multidimensional feature space, an uncertain object is represented by a multivariate probability density function (PDF). This PDF can be defined either discretely (e.g. by a histogram) or continuously in parametric form (e.g. by a Gaussian Mixture Model). For a database of uncertain objects, the users expect similar data analysis techniques as for a conventional database of certain objects. An important analysis technique for certain objects is the skyline operator which finds maximal or minimal vectors with respect to any possible attribute weighting. In this paper, we propose the concept of probabilistic skylines, an extension of the skyline operator for uncertain objects. In addition, we propose efficient and effective methods for determining the probabilistic skyline of uncertain objects which are defined by a PDF in parametric form (e.g. a Gaussian function or a Gaussian Mixture Model). To further accelerate the search, we elaborate how the computation of the probabilistic skyline can be supported by an index structure for uncertain objects. An extensive experimental evaluation demonstrates both the effectiveness and the efficiency of our technique.

In 1999, Davis and Jedwab gave an explicit algebraic normal form for$m! \cdot 2^{h(m+2)}$ordered Golay pairs of length$2^{m}$over$ {\BBZ }_{2^{h}}$, involving$m!/2 \cdot 2^{h(m+1)}$Golay sequences. In 2005, Li and Chu unexpectedly found an additional 1024 length 16 quaternary Golay sequences. Fiedler and Jedwab showed in 2006 that these new Golay sequences exist because of a “crossover” of the aperiodic autocorrelation function of certain quaternary length eight sequences belonging to Golay pairs, and that they spawn further new quaternary Golay sequences and pairs of length$2^{m}$for$m > 4$under BudiŠin's 1990 iterative construction. The total number of Golay sequences and pairs spawned in this way is counted, and their algebraic normal form is given explicitly. A framework of constructions is derived in which Turyn's 1974 product construction, together with several variations, plays a key role. All previously known Golay sequences and pairs of length$2^{m}$over$ {\BBZ }_{2^{h}}$can be obtained directly in explicit algebraic normal form from this framework. Furthermore, additional quaternary Golay sequences and pairs of length$2^{m}$are produced that cannot be obtained from any other known construction. The framework generalizes readily to lengths that are not a power of$2$, and to alphabets other than$ {\BBZ }_{2^{h}}$.

In 1999, Davis and Jedwab gave a direct construction of Golay complementary sequences over Zopf2hof length 2m. Recently, Li and Chu found 1024 more quaternary Golay complementary sequences of length 16, that cannot be obtained by the direct construction, using exhaustive computer enumeration. It is shown how these sequences arise from interleaving and concatenation of two classes of Golay complementary sequences given as an example by Davis and Jedwab. These examples spawn new Golay sequences over Zopf2hof length 2mfor all h ges 2 and m ges 4