15456079
Neighborhood PropertyBased Pattern Selection for Support Vector Machines
The support vector machine (SVM) has been spotlighted in the machine learning community because of its theoretical soundness and practical performance. When applied to a large data set, however, it requires a large memory and a long time for training. To cope with the practical difficulty, we propose a pattern selection algorithm based on neighborhood properties. The idea is to select only the patterns that are likely to be located near the decision boundary. Those patterns are expected to be more informative than the randomly selected patterns. The experimental results provide promising evidence that it is possible to successfully employ the proposed algorithm ahead of SVM training.
15586209
Fast Pattern Selection for Support Vector Classifiers
SVMs tend to take a very long time to train with a large data set. If "redundant" patterns are identified and deleted in pre-processing, the training time could be reduced significantly. We propose a k-nearest neighbors(k-NN) based pattern selection method. The method tries to select the patterns that are near the decision boundary and that are correctly labeled. The simulations over synthetic data sets showed promising results: (1) By converting a non-separable problem to a separable one, the search for an optimal error tolerance parameter became unnecessary. (2) SVM training time decreased by two orders of magnitude without any loss of accuracy. (3) The redundant SVs were substantially reduced.
1668855
Fast Pattern Selection Algorithm for Support Vector Classifiers: Time Complexity Analysis
Training SVM requires large memory and long cpu time when the pattern set is large. To alleviate the computational burden in SVM training, we propose a fast preprocessing algorithm which selects only the patterns near the decision boundary. The time complexity of the proposed algorithm is much smaller than that of the naive M 2 algorithm
6919897
An Accurate Worst Case Timing Analysis for RISC Processors
An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time-bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. This paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.
6979297
An efficient color representation for image retrieval
A compact color descriptor and an efficient indexing method for this descriptor are presented. The target application is similarity retrieval in large image databases using color. Colors in a given region are clustered into a small number of representative colors. The feature descriptor consists of the representative colors and their percentages in the region. A similarity measure similar to the quadratic color histogram distance measure is defined for this descriptor. The representative colors can be indexed in the three-dimensional (3-D) color space thus avoiding the high-dimensional indexing problems associated with the traditional color histogram. For similarity retrieval, each representative color in the query image or region is used independently to find regions containing that color. The matches from all of the query colors are then combined to obtain the final retrievals. An efficient indexing scheme for fast retrieval is presented. Experimental results show that this compact descriptor is effective and compares favorably with the traditional color histogram in terms of overall computational complexity.
8855758
New Disk Scheduling Algorithms for Reduced Rotational Latency
Disk arm scheduling algorithms have been studied for many years to increase disk I/O performance. Most of the disks by the early 1980’s are characterized as a linear seek time and their seek time is responsible for the most time of disk access. So, the existing disk scheduling algorithms have focused on the reduction of the average seek distance. Seek time has improved greatly and today’s disks usually have nonlinear seek time characteristics, whereas the rotation speed has been steady at the 3600 RPM. So, it is of value to reduce average rotational latency. In this paper we propose two disk scheduling algorithms, i.e. Shortest Rotational Latency First(SRLF) and Shortest Access Tie Fist(SATF) for reduced rotational latency. SRLF services first a request with the shortest expected rotational latency and SATF services first a request with the shortest expected access time. We analyze the expected access time of the request serviced first by each of SSTF and SRLF under the uniform cylinder access. We evaluated the response time of SSTF, SRLF, and SATF through the simulations under the uniform and localized cylinder access. The results of the analysis and simulations show that the algorithms proposed in this paper are more efficient than SSTF which is known for the fastest response time.
12130632
A packet scheduling scheme for broadband wireless networks with heterogeneous services
A frame-based packet scheduling scheme, the pinwheel scheduling (PWS) scheme, is proposed and investigated at the medium access control (MAC) layer in broadband wireless networks. The objective of the proposed scheduling scheme is to provide, respectively, low delay and low jitter for real-time traffic and short queue length for nonreal-time traffic. We have demonstrated in this paper that the proposed PWS scheme not only satisfies the packet-level QoS requirements but also has low implementation cost. As the number of constant bit rate (CBR) connections increases, variable bit rate (VBR) traffic would suffer a larger jitter, the PWS with modular strategy (PWS/MS) scheme is proposed to further enhance the PWS scheme. We also introduce two different slot-reuse strategies named real-time traffic first (RTF) and longest queue first (LQF), respectively, to improve the resource utilization. In order to demonstrate the performance of the PWS and PWS/MS schemes, comparisons are made with existing schemes such as the round-robin (RR) and weighted-round-robin (WRR) by using the OPNET software. Simulation results show that the proposed schemes are capable of maintaining the lowest delay and jitter for VBR and CBR traffic while not sacrificing the available bit rate (ABR) traffic.
34064197
The study of quick download mechanism in an infrastructural wireless environment
Frequent handoff consumes a lot of system capability and signalling resources in a mobile system. In this paper, we present download mechanisms in mobile systems or broadcast systems to support data users to receive the whole packet in time before moving out of the coverage area. Three download strategies: Quick Download using Multi-channel (QDM) scheme, Prior Download using Single channel (PDS) scheme and the Quit Download (QUD) scheme are proposed in this study where the efficiencies of the three strategies are compared with the one without particular treatment. Some significant estimations such as the percentage of handoff data users having completed service before leaving the cell, the mean waiting time of non-handoff data users, and the blocking probability of data users are analysed and compared. The numerical results show that, the QDM strategy is most efficient in reducing the handoff rate, the QUD strategy can assure the waiting time of non-handoff data users and the PDS strategy can keep the handoff rate constant at light and heavy voice load. Furthermore, various number of guard channels for data users are evaluated in terms of data and voice performance based on various download strategies. Copyright © 2006 John Wiley & Sons, Ltd.