Sat, 05 Jul 2008 00:22:36 BST CiteULike: AbnerCYH sys_performance http://www.citeulike.org/user/AbnerCYH/tag/sys_performance CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/2945162 <i>The Computer Journal, Vol. 51, No. 4. (1 July 2008), pp. 451-469.</i><br /><br />We derive CPU time formulae for the two simplest linear time-sorting algorithms, linear probing sort and bucket sort, as a function of the load factor, and show agreement with experimentally measured CPU times. This allows us to compute optimal load factors for each algorithm, whose values have previously been identified only approximately in the literature. We also present a simple model of cache latency and apply it not only to linear probing sort and bucket sort, where the bulk of the latency is due to random access, but also to the log-linear algorithm quicksort, where the access is primarily sequential, and again show agreement with experimental CPU times. With minor modifications, our model also fits CPU times previously reported by LaMarca and Ladner for radix sort, and by Rahman and Raman for most significant digit radix sort, Flashsort1, and memory tuned quicksort. 10.1093/comjnl/bxm097 Analysis of Linear Time Sorting Algorithms Paul Shutler Seok Sim Wei Lim doi:10.1093/comjnl/bxm097 The Computer Journal, Vol. 51, No. 4. (1 July 2008), pp. 451-469. 2008-06-30T15:03:52-00:00 2008 The Computer Journal 51 4 451 469 algorithms sys_performance http://www.citeulike.org/user/AbnerCYH/article/2944739 <i>Multiple Classifier Systems (2003), pp. 161-161.</i><br /><br />Boosting algorithms are a means of building a strong ensemble classifier by aggregating a sequence of weak hypotheses. In this paper we consider three of the best-known boosting algorithms: Adaboost [9], Logitboost [11] and Brownboost [8]. These algorithms are adaptive, and work by maintaining a set of example and class weights which focus the attention of a base learner on the examples that are hardest to classify. We conduct an empirical study to compare the performance of these algorithms, measured in terms of overall test error rate, on five real data sets. The tests consist of a series of cross-validatory samples. At each validation, we set aside one third of the data chosen at random as a test set, and fit the boosting algorithm to the remaining two thirds, using binary stumps as a base learner. At each stage we record the final training and test error rates, and report the average errors within a 95% confidence interval. We then add artificial class noise to our data sets by randomly reassigning 20% of class labels, and repeat our experiment. We find that Brownboost and Logitboost prove less likely than Adaboost to overfit in this circumstance. An Empirical Comparison of Three Boosting Algorithms on Real Data Sets with Artificial Class Noise Ross Mcdonald David Hand Idris Eckley doi:10.1007/3-540-44938-8_4 Multiple Classifier Systems (2003), pp. 161-161. 2008-06-30T14:15:47-00:00 2003 Multiple Classifier Systems 161 161 algorithms kdd sys_performance http://www.citeulike.org/user/AbnerCYH/article/2929443 <i>Machine Learning, Vol. 40, No. 2. (2000), pp. 139-157.</i><br /><br />Bagging and boosting are methods that generate a diverse ensemble of classifiers by manipulating the training data given to a “base” learning algorithm. Breiman has pointed out that they rely for their effectiveness on the instability of the base learning algorithm. An alternative approach to generating an ensemble is to randomize the internal decisions made by the base algorithm. This general approach has been studied previously by Ali and Pazzani and by Dietterich and Kong. This paper compares the effectiveness of randomization, bagging, and boosting for improving the performance of the decision-tree algorithm C4.5. The experiments show that in situations with little or no classification noise, randomization is competitive with (and perhaps slightly superior to) bagging but not as accurate as boosting. In situations with substantial classification noise, bagging is much better than boosting, and sometimes better than randomization. An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization Thomas Dietterich doi:10.1023/A:1007607513941 Machine Learning, Vol. 40, No. 2. (2000), pp. 139-157. 2008-06-26T09:40:27-00:00 2000 Machine Learning 40 2 139 157 algorithms kdd sys_performance http://www.citeulike.org/user/AbnerCYH/article/2810208 <i>(14 May 2008)</i><br /><br />Path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. In this paper, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. Network paths are modeled as erasure Gilbert-Elliot channels. It is known that over any erasure channel, Maximum Distance Separable (MDS) codes achieve the minimum probability of irrecoverable loss among all block codes of the same size. Based on the adopted model for the error behavior, we prove that the probability of irrecoverable loss for MDS codes decays exponentially for an asymptotically large number of paths. Then, optimal rate allocation problem is solved for the asymptotic case where the number of paths is large. Moreover, it is shown that in such asymptotically optimal rate allocation, each path is assigned a positive rate iff its quality is above a certain threshold. The quality of a path is defined as the percentage of the time it spends in the bad state. Finally, using dynamic programming, a heuristic suboptimal algorithm with polynomial runtime is proposed for rate allocation over a finite number of paths. This algorithm converges to the asymptotically optimal rate allocation when the number of paths is large. The simulation results show that the proposed algorithm approximates the optimal rate allocation (found by exhaustive search) very closely for practical number of paths, and provides significant performance improvement compared to the alternative schemes of rate allocation. Path Diversity over Packet Switched Networks: Performance Analysis and Rate Allocation Shervan Fashandi Shahab Gharan Amir Khandani (14 May 2008) 2008-05-18T16:02:36-00:00 2008 algorithms graph sys_performance http://www.citeulike.org/user/AbnerCYH/article/2624181 <i>(1996), pp. 128-139.</i> Structured permuting in place on parallel disk systems Leonard Wisniewski doi:10.1145/236017.236047 (1996), pp. 128-139. 2008-04-02T18:18:07-00:00 1996 128 139 ACM algorithms parallel sys_performance http://www.citeulike.org/user/AbnerCYH/article/2609109 <i>ACM Comput. Surv. (1999)</i> Algorithm engineering Giuseppe Cattaneo Giuseppe Italiano doi:10.1145/333580.333582 ACM Comput. Surv. (1999) 2008-03-28T18:31:17-00:00 1999 ACM Comput. Surv. 0360-0300 ACM algorithms sys_performance http://www.citeulike.org/user/AbnerCYH/article/2548178 <i>Soft\-waredash Prac\-tice and Experience, Vol. 30, No. 11. (2000), pp. 1167-1202.</i><br /><br />this paper we present and discuss the design of this C++ software library. On the design of CGAL a computational geometry algorithms library Andreas Fabri Geert Giezeman Lutz Kettner Stefan Schirra Sven Schönherr Soft\-waredash Prac\-tice and Experience, Vol. 30, No. 11. (2000), pp. 1167-1202. 2008-03-18T03:55:27-00:00 2000 Soft\-waredash Prac\-tice and Experience 30 11 1167 1202 algorithms sys_performance http://www.citeulike.org/user/AbnerCYH/article/2269937 <i>(December 2004)</i><br /><br />MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day. MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean Sanjay Ghemawat (December 2004) 2008-01-21T20:16:16-00:00 2004 algorithms data_structure distributed sys_performance http://www.citeulike.org/user/AbnerCYH/article/2242896 <i>Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM (2002), pp. 32-41.</i><br /><br />Tiling has long been used to improve cache performance. Recursion hers recently been used as a cache-oblivious method of improving cache performance. Both of these techniques are normally applied to dense linear algebra problems. We develop new implementations by means of these two techniques for the fundamental graph problem of Transitive Closure, namely the Floyd-Warshall Algorithm, and prove their optimality with respect to processor-memory traffic. Using these implementations we show up to 10× improvement in execution time. We also address Dijkstra's algorithm for the single-source shortest path problem and Prim's algorithm for Minimum Spanning Tree, for which neither tiling nor recursion can be directly applied. For these algorithms, we demonstrate up to a 2× improvement by using a cache friendly graph representation. Experimental results are shown for the Pentium Ill, UltraSPARC Ill, Alpha 21264, and MIPS R12000 machines using problem sizes between 1024 and 4096 vertices. We demonstrate improved cache performance using the Simplescalar simulator Optimizing graph algorithms for improved cache performance Joon-Sang Park M Penner VK Prasanna doi:10.1109/IPDPS.2002.1015509 Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM (2002), pp. 32-41. 2008-01-17T05:02:51-00:00 2002 Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM 32 41 algorithms sys_performance