Search

In pattern recognition tasks, selecting the appropriate features for a supervised classification problem is a critical task. One theoretical tool used for this purpose is the Test Theory, which identifies feature relevance and reduces the complexity of the training and classification processes. However, searching for irreducible subsets of features, called typical testors, that can differentiate objects belonging to different classes, is an exponential problem in terms of the number of features. To address this problem, various algorithms have been proposed in the literature that use different strategies to avoid unnecessary comparisons. In this paper, is proposed the RegularSearch algorithm to find all typical testors in a dataset associated with a supervised classification problem. The algorithm incrementally searches for candidate subsets of features that are most likely to be associated with a typical testor, reducing the number of comparisons as new features are added to the candidate subset. Our comparisons with the best-performing algorithms reported in the literature demonstrate that RegularSearch is more efficient for processing synthetic and real problem datasets in certain scenarios. [ABSTRACT FROM AUTHOR]

Highlights • A Quick Inclusion-Exclusion (QIE) technique is proposed. • The proposed QIE is for multi-state flow network reliability problems. • The proposed QIE is easy to code and only needs one comparision in each (intersection) term. • The proposed QIE is simpler than the traditional IE. • The proposed QIE is faster than the RSDP which is the most popular sum-of-disjoint product method. Abstract The reliability of modern information systems modeled as multi-state flow networks (MFNs) is a crucial concern the planning, design and control of these systems. The inclusion-exclusion technique (IET) is a popular tool for assessing MFN reliability because it is simple and easily understood. However, it is less efficient than other methods, like the sum-of-disjoint product method (SDP), for example. This paper proposes a new IET, called the Quick Inclusion-Exclusion technique (QIE) to increase the efficiency of the IET and reduce the amount of memory required in MFNs. The correctness and the time complexity of QIE is analyzed and proven. An MFN reliability example is implemented to illustrate the proposed QIE. In order to demonstrate its performance, the proposed QIE is compared with the most popular SDP, the recursive SDP (RSDP) in 20 benchmark networks taken from the literature. Numerical examples demonstrate that the proposed QIE outperforms RSDP in terms of both efficiency and memory use. This result differs significantly from those obtained by traditional methods. [ABSTRACT FROM AUTHOR]

Boolean matrix factorization has become an important direction in data analysis. In this paper, we examine the question of how to assess the quality of Boolean matrix factorization algorithms. We critically examine the current approaches, and argue that little attention has been paid to this problem so far and that a systematic approach to it is missing. We regard quality assessment of factorization algorithms as a multifaceted problem, identify major views with respect to which quality needs to be assessed, and present various observations on the available algorithms in this regard. Due to its primary importance, we concentrate on the quality of collections of factors computed from data, present a method to assess this quality, and evaluate this method by experiments. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we introduce a novel class of facility location problems, and propose solutions based on Voronoi diagrams. Our solutions locate a set of facilities on a two dimensional space, with respect to a set of dynamic demand. The information about these demand is gathered through modifications of the overall system, into a central decision unit. This influences our objective of minimizing the total loss function. Considering a continuous space and discrete time, facilities are assigned to meet demands in each time cycle. Two distinct approaches are proposed and thoroughly studied, followed by a case study. We call our main algorithm Reactive Agent Dynamic Voronoi Diagram Facility Spread. We also test our solutions empirically through a set of experiments. Considering n and p to be the number of demand points, and the number of facilities in hand, respectively, the time complexity of the algorithm is for a complete run of c cycles. [Copyright &y& Elsevier]

Abstract: Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k 1 nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k 2 NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search and identify its characteristics, and then develop several algorithms for processing MNN queries efficiently. In particular, we investigate two classes of MNN queries, i.e., MNNP and MNNT queries, which are defined with respect to stationary query points and moving query trajectories, respectively. Our methods utilize the batch processing and reusing technology to reduce the I/O cost (i.e., number of node/page accesses) and CPU time significantly. In addition, we extend our techniques to tackle historical continuous MNN (HCMNN) search for moving object trajectories, which returns the mutual nearest neighbors of q (for a specified k 1 and k 2) at any time instance of Γ. Extensive experiments with real and synthetic datasets demonstrate the performance of our proposed algorithms in terms of efficiency and scalability. [Copyright &y& Elsevier]

Abstract: Skyline queries have been increasingly used in multi-criteria decision making and data mining applications. They retrieve a set of interesting points from a potentially large set of data points. A point is said to be interesting if it is not dominated by any other point. Skyline cube (skycube) consists of skylines of all possible non-empty subsets of a given set of dimensions. In this paper, we propose two algorithms for computing skycube using bitmaps that are derivable from indexes. The Point-based skycube algorithm is an improvement over the existing Bitmap algorithm, extended to compute skycube. The Point-based algorithm processes one point at a time to check for skylines in all subspaces. The Domain-based skycube algorithm views points as value combinations and probes entire search space for potential skyline points. It significantly reduces bitmap access for low cardinality dimensions. Our experimental study shows that the two algorithms strictly dominate, or at least comparable to, the current skycube algorithm in most of the cases, suggesting that such an approach could be a useful addition to the set of skyline query processing techniques. [Copyright &y& Elsevier]

Abstract: This paper describes a new algorithm for the generation of pseudo random numbers with approximate self-similar structure. The Simple Self-Similar Sequences Generator (4SG) elaborates on an intuitive approach to obtain a fast and accurate procedure, capable of reproducing series of points exhibiting the property of persistence and anti-persistence. 4SG has a computational complexity of and memory requirements of the order of , where is the number of points to be generated. The accuracy of the algorithm is evaluated by means of computer-based simulations, recurring to several Hurst parameter estimators, namely Variance Time (VT) and the Wavelets-based estimator. The Hosking and the Wavelets-based methods for the generation of self-similar series were submitted to the same tests the 4SG was analysed with, providing for a basis for comparison of several performance aspects of the algorithm. Results show that the proposal embodies a good candidate not only for on-demand emulation of arbitrarily long self-similar sequences, but also for fast and efficient online simulations. [Copyright &y& Elsevier]

Abstract: This paper deals with a general α-decomposition problem of fuzzy relations, which can be stated as follows: given a fuzzy relation , determine two fuzzy relations and such that , where X (resp. Y) is a finite set. Firstly we point out that every fuzzy relation R is always generally α-decomposable, and give an algorithm to construct Q and T with for a given R. Secondly, we show that the general content with is equal to the chromatic number of the simple graph F R generated by R. Therefore, finding an exact algorithm for calculating is an NP-complete problem. [Copyright &y& Elsevier]

Abstract: In a number of emerging streaming applications, the data values that are produced have an associated time interval for which they are valid. A useful computation over such streaming data is to produce a continuous and valid skyline summary. Previous work on skyline algorithms have only focused on evaluating skylines over static data sets, and there are no known algorithms for skyline computation in the continuous setting. In this paper, we introduce the continuous time-interval skyline operator, which continuously computes the current skyline over a data stream. We present a new algorithm called LookOut for evaluating such queries efficiently, and empirically demonstrate the scalability of this algorithm. In addition, we also examine the effect of the underlying spatial index structure when evaluating skylines. Whereas previous work on skyline computations have only considered using the R ∗-tree index structure, we show that for skyline computations using an underlying quadtree has significant performance benefits over an R ∗-tree index. [Copyright &y& Elsevier]

Abstract: The RC4 is a stream cipher widely deployed in software applications due to its simplicity and efficiency. The paper presents a cryptanalytic attack that employs the tree representation of this cipher and introduces an abstraction in the form of general conditions for managing the information about its internal state. In order to find the initial state, the tree of general conditions is searched applying the hill-climbing strategy. The complexity of this attack is lower than that of an exhaustive search. The attack is derived from a general cryptanalytic approach for a class of table-shuffling ciphers, whose next-state function permutes the table entries. Incorporating the general conditions in the existing backtracking algorithm, the estimated complexity of the cryptanalytic attack is decreased below the best published result but the RC4 still remains a quite secure cipher in practice. [Copyright &y& Elsevier]