The suffix tree is one of most widely adopted indexes in the application of genome sequence alignment. Although it supports very fast alignment, it has a couple of shortcomings, such as a very long construction time and a very large volume size. Loh et al. [7] proposed a suffix tree construction algorithm with dramatically improved performance; however, the size still remains as a challenging problem. We propose an algorithm by extending the one by Loh et al. to reduce the suffix tree size. As a result of our experiments, our algorithm constructed a suffix tree of approximately 60% of the size within almost the same time period.

The international telecommunication standards bodies such as ITU-T, ATM Forum, and IETF recommend the dual leaky bucket for the traffic specifications for VBR service. On the other hand, recent studies have demonstrated multiple time-scale burstiness in compressed video traffic. In order to fill this gap between the current standards and real traffic characteristics, we present a standard-compatible traffic parameter selection method based on the notion of a critical time scale (CTS). The defined algorithm is optimal in the sense that it minimizes the required amount of link capacity for a traffic flow under a maximum delay constraint. Simulation results with compressed video traces demonstrate the efficiency of the defined traffic parameter selection algorithm in resource allocation.

We propose a robust and efficient algorithm called ROCKET for clustering large-scale transaction databases. ROCKET is a divisive hierarchical algorithm that makes the most of recent hardware architecture. ROCKET handles the cases with the small and the large number of similar transaction pairs separately and efficiently. Through experiments, we show that ROCKET achieves high-quality clustering with a dramatic performance improvement.