2513432
Cache-efficient matrix transposition
We investigate the memory system performance of several algorithms for transposing an N/spl times/N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data cache, the translation lookaside buffer, register tiling, and the array layout function to the overall running time of the algorithms. We use various memory models to capture and analyze the effect of various facets of cache memory architecture that guide the choice of a particular algorithm, and attempt to experimentally validate the predictions of the model. Our major conclusions are as follows: limited associativity in the mapping from main memory addresses to cache sets can significantly degrade running time; the limited number of TLB entries can easily lead to thrashing; the fanciest optimal algorithms are not competitive on real machines even at fairly large problem sizes unless cache miss penalties are quite high: low-level performance tuning "hacks", such as register tiling and array alignment, can significantly distort the effects of improved algorithms; and hierarchical non-linear layouts are inherently superior to the standard canonical layouts (such as row- or column-major) for this problem.
1068367
An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains
Abstract. We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log 4 n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms.
10562059
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O(1) query time, require O(\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O(n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O(n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O(n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O(\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O(1) time. This improves the previous best known update bound by a factor of log n. For maintaining all-pairs shortest paths, we present an algorithm that achieves O(\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O(\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0, that achieves a sub-quadratic update time of O(n log2n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O(1/nc) for any constant c).
32334601
Finding an Approximate Median with High Probability in Constant Parallel Time
Given n elements from a totally ordered set we outline a method for choosing an element whose rank is γn for some 0 0.
9302549
Planar Graph Blocking for External Searching

AbstractWe present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.

11169442
Linear Time Algorithms for Clustering Problems in Any Dimensions
We generalize the k-means algorithm presented by the authors [14] and show that the resulting algorithm can solve a larger class of clustering problems that satisfy certain properties (existence of a random sampling procedure and tightness). We prove these properties for the k-median and the discrete k-means clustering problems, resulting in O(2(k/e)O(1)dn) time (1+e)-approximation algorithms for these problems. These are the first algorithms for these problems linear in the size of the input (nd for n points in d dimensions), independent of dimensions in the exponent, assuming k and e to be fixed. A key ingredient of the k-median result is a (1+e)-approximation algorithm for the 1-median problem which has running time O(2(1/e)O(1)d). The previous best known algorithm for this problem had linear running time.
1889631
Characterizing Unstructured Overlay Topologies in Modern P2P File-Sharing Systems
During recent years, peer-to-peer (P2P) file-sharing systems have evolved in many ways to accommodate growing numbers of participating peers. In particular, new features have changed the properties of the unstructured overlay topology formed by these peers. Despite their importance, little is known about the characteristics of these topologies and their dynamics in modern file-sharing applications.
 This paper presents a detailed characterization of P2P overlay topologies and their dynamics, focusing on the modern Gnutella network. Using our fast and accurate P2P crawler, we capture a complete snapshot of the Gnutella network with more than one million peers in just a few minutes. Leveraging more than 18,000 recent overlay snapshots, we characterize the graph-related properties of individual overlay snapshots and overlay dynamics across hundreds of back-to-back snapshots. We show how inaccuracy in snapshots can lead to erroneous conclusions--such as a power-law degree distribution. Our results reveal that while the Gnutella network has dramatically grown and changed in many ways, it still exhibits the clustering and short path lengths of a small world network. Furthermore, its overlay topology is highly resilient to random peer departure and even systematic attacks. More interestingly, overlay dynamics lead to an "onion-like" biased connectivity among peers where each peer is more likely connected to peers with higher uptime. Therefore, long-lived peers form a stable core that ensures reachability among peers despite overlay dynamics.
41882641
Using limited information to enhance group stability
The performance of individual agents in a group depends critically on the quality of information available to them about local and global goals and resources. In general, it is assumed that the more accurate and comprehensive the available information, the better is the expected performance of the individual and the group. This conclusion can be challenged in a number of scenarios. We investigate the use of limited information by agents in choosing betwen one of several different options, and conclude that if agents are kept ignorant about, or they deliberately ignore, any number of options, the group can converge faster to a stable and optimal configuration. We present a probabilistic analysis that sheds light on the observed phenomenon of quicker system convergence with less global information. This analysis suggests a desirable adaptive behavior on the part of individual agents. Experiments with agents following these adaptive behavior exhibits faster convergence. We also demonstrate how a couple of coalition formation schemes can improve the rate of convergence. A variable coalition formation mechanism is found to be more effective than a static one.
9417710
Using real-valued genetic algorithms to evolve rule sets for classification
In this paper, we use a genetic algorithm to evolve a set of classification rules with real-valued attributes. We show how real-valued attribute ranges could be encoded with real-valued genes and present a new uniform method for representing don't cares in the rules. We view supervised classification as an optimization problem, and evolve rule sets that maximize the number of correct classifications of input instances. We use a variant of the Pitt approach to genetic-based machine learning system with a novel conflict resolution mechanism between competing rules within the same rule set. Experimental results demonstrate the effectiveness of our proposed approach on a benchmark wine classifier system.<<ETX>>
1681173
Optimal proxy cache allocation for efficient streaming media distribution
We address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as hatching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resulting transmission cost. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in a predominantly unicast environment such as the Internet.
10902519
Effects of Local Information on Group Behavior
Researchers in the field of Distributed Artificial Intelligence have studied the effects of local decisionmaking on overall system performance in both cooperative and self-interested agent groups (Bond & Gasser, 1988) . The performance of individual agents depends critically on the quality of information available to it about local and global goals and resources. Whereas in general it is assumed that the more accurate and up-to-date the available information, the better is the expected performance of the individual and the group, this conclusion can be challenged in a number of scenarios. The populace in human societies tend to look for opportunities and search for better opportunities in their environment (Bartos, 1967) . The theory of migration in social behavior and occupational mobility suggests that the stability of the population depends on how an individual chooses its action based on the prevailing circumst antes. As agent designers, we are faced with the problem of developing decision mechanisms that allow agent societies to stabilize in states where system resources are effectively utilized. In this research, we focus on a particular aspect of distributed decision-making: the effect of limited global knowledge on group behavior. The research question that we are asking is the following: Can limited local knowledge be a boon rather than a bane in a multiagent system ? To investigate this issue we use a resource utilization problem where a number of agents are distributed between several identical resources. We assume that the cost of using any resource is directly proportional to its usage. This cost can be due to a delay in processing of the task in hand, or a reduction in the quality of the resource due to congestion. Hence, there is a justified urge in agents to seek out and move to resource with lesser usage. Other researchers have shown that such systems can exhibit oscillatory or chaotic behavior where agents move back and forth between resources (Hogg & Huberman 1991; Kephart, Hogg & Huberman 1989) resulting in ineffective uti1406 AAAI-96 lization of system resources. Whereas asynchrony, heterogeneous agent decision mechanisms, etc. has been suggested as possible means for solving the instability problem, our proposed solution of using locally differing global views is a novel mechanism to introduce asymmetry in group decisions that expedites group stability.