22669776
Identities via Bell matrix and Fibonacci matrix
In this paper, we study the relations between the Bell matrix and the Fibonacci matrix, which provide a unified approach to some lower triangular matrices, such as the Stirling matrices of both kinds, the Lah matrix, and the generalized Pascal matrix. To make the results more general, the discussion is also extended to the generalized Fibonacci numbers and the corresponding matrix. Moreover, based on the matrix representations, various identities are derived.
6659460
Generalized Riordan arrays
In this paper, we generalize the concept of Riordan array. A generalized Riordan array with respect to c"n is an infinite, lower triangular array determined by the pair (g(t),f(t)) and has the generic element d"n","k=[t^n/c"n]g(t)(f(t))^k/c"k, where c"n is a fixed sequence of non-zero constants with c"0=1. We demonstrate that the generalized Riordan arrays have similar properties to those of the classical Riordan arrays. Based on the definition, the iteration matrices related to the Bell polynomials are special cases of the generalized Riordan arrays and the set of iteration matrices is a subgroup of the Riordan group. We also study the relationships between the generalized Riordan arrays and the Sheffer sequences and show that the Riordan group and the group of Sheffer sequences are isomorphic. From the Sheffer sequences, many special Riordan arrays are obtained. Additionally, we investigate the recurrence relations satisfied by the elements of the Riordan arrays. Based on one of the recurrences, some matrix factorizations satisfied by the Riordan arrays are presented. Finally, we give two applications of the Riordan arrays, including the inverse relations problem and the connection constants problem.
17247210
Identities on Bell polynomials and Sheffer sequences
In this paper, we study exponential partial Bell polynomials and Sheffer sequences. Two new characterizations of Sheffer sequences are presented, which indicate the relations between Sheffer sequences and Riordan arrays. Several general identities involving Bell polynomials and Sheffer sequences are established, which reduce to some elegant identities for associated sequences and cross sequences.
16034501
Effective Keyword Search in XML Documents Based on MIU
Keyword search is an effective approach for most users to search for information because they do not need to learn complex query languages or the underlying structures of the data. This paper focuses on effective keyword search in XML documents which are modeled as labeled trees. We first analyze the problems caused by the refinement of result granularity during XML keyword search and then propose to partition an XML document into XML fragments with the granularity of Minimal Information Unit (MIU). Furthermore, we present efficient index structures and the corresponding search algorithms. Finally, our comprehensive experiments demonstrate the benefits of our method over previously proposed methods in terms of result quality, index size and execution time.
37619733
Taming Underlying Design for Energy Efficient Distributed Source Coding in Multirate Wireless Sensor Network
Signal processing applications such as Distributed Source Coding (DSC) in Wireless Sensor Network (WSN) are often multirate in nature, which provide additional significant opportunities in WSN design for achieving energy efficiency. In this paper, we analyze the DSC traffic for signal processing applications in multirate WSN and propose a novel rate oriented approach with MAC and PHY cross layer utilization to achieve high energy efficiency. Simulation results show that the proposed approach achieves significant energy efficiency by a factor of three while maintaining the transmission quality in WSN. This approach can be easily extended to other WSN MAC and PHY designs, providing multirate service to application layer to allow achieving higher energy efficiency
3069611
A General Framework for Fast Co-clustering on Large Datasets Using Matrix Decomposition
Simultaneously clustering columns and rows (co- clustering) of large data matrix is an important problem with wide applications, such as document mining, microarray analysis, and recommendation systems. Several co-clustering algorithms have been shown effective in discovering hidden clustering structures in the data matrix. For a data matrix of m rows and n columns, the time complexity of these methods is usually in the order of mtimesn (if not higher). This limits their applicability to data matrices involving a large number of columns and rows. Moreover, an implicit assumption made by existing co-clustering methods is that the whole data matrix needs to be held in the main memory. In this paper, we propose a general framework, CRD, for co-clustering large datasets utilizing recently developed sampling- based matrix decomposition methods. The time complexity of our approach is linear in m and n. And it does not require the whole data matrix be in the main memory. Experimental results show that CRD achieves competitive accuracy to existing co-clustering methods but with much less computational cost.
9042204
CRD: fast co-clustering on large datasets utilizing sampling-based matrix decomposition
The problem of simultaneously clustering columns and rows (co-clustering) arises in important applications, such as text data mining, microarray analysis, and recommendation system analysis. Compared with the classical clustering algorithms, co-clustering algorithms have been shown to be more effective in discovering hidden clustering structures in the data matrix. The complexity of previous co-clustering algorithms is usually O(m X n), where m and n are the numbers of rows and columns in the data matrix respectively. This limits their applicability to data matrices involving a large number of columns and rows. Moreover, some huge datasets can not be entirely held in main memory during co-clustering which violates the assumption made by the previous algorithms. In this paper, we propose a general framework for fast co-clustering large datasets, CRD. By utilizing recently developed sampling-based matrix decomposition methods, CRD achieves an execution time linear in m and n. Also, CRD does not require the whole data matrix be in the main memory. We conducted extensive experiments on both real and synthetic data. Compared with previous co-clustering algorithms, CRD achieves competitive accuracy but with much less computational cost.
7588231
Efficient Algorithms for Mining Maximal Frequent Concatenate Sequences in Biological Datasets
The growth of bioinformatics has resulted in datasets with new characteristics. The DNA sequences typically contain a large number of items. From them biologists assemble a whole genome of species based on frequent concatenate sequences, which ordinarily have hundreds of items. Such datasets pose a great challenge for existing frequent pattern discovery algorithms. Almost all of them are Apriori-like and so have an exponential dependence on the average sequence length. PrefixSpan is the most efficient algorithm, which presented the projection-based sequential pattern-growth approach. However it grows sequential patterns by exploring length-1 frequent patterns and so is not suitable for biological dataset with long frequent concatenate sequences. In this paper, we propose two novel algorithms, called MacosFSpan and MacosVSpan, to mine maximal frequent concatenate sequences. They are specially designed to handle datasets having long frequent concatenate sequences. Our performance study shows that MacosFSpan outperforms the traditional methods with length-1 sequences exploration and MacosVSpan is more efficient than Macos VSpan