Our collaborative partitioning model posits a bicriteria objective in which we seek the best item clustering that satisfies the most users at the highest level of satisfaction. We consider two basic methods for determining user satisfaction. The first method is based on how well each user's preferences match a given partition, and the second method is based on average correlation scores taken over sufficiently large subpopulations of users. We show these problems are NP-Hard and develop a set of heuristic approaches for solving them. We provide lower bounds on the satisfaction level on random data, and error bounds in the planted partition model, which provide confidence levels for our heuristic methods. Finally, we present experiments on several real examples that demonstrate the effectiveness of our framework.

The construction of multicast trees is complicated by the need to balance a number of important objectives, including: minimizing latencies, minimizing depth/hops, and bounding the degree. In this paper, we study the problem of determining a degree-bounded directed spanning tree of minimum average-latency in a complete graph where the inter-node latencies are used to determine a metric. In particular, we focus on measuring the effects on average latency when imposing depth constraints (i.e., bounds on hop count) on degree-bounded spanning trees. The general problem is a well known NP-hard problem, and several works have proposed approximate solutions which aim at minimizing either depth or latency. In this work, we present a new heuristic algorithm which improves upon previous solutions by considering both depth and latency and the tradeoffs between them. Our algorithms are shown to improve the theoretical worst-case approximation factors, and we demonstrate improvements under empirical evaluation. Our experiments examine and analyze several different topologies, including, low-dimensional random geometric networks, random transit-stub networks, and high- dimensional hypercube networks. We show how our solutions can be applied in the context of enabling multicasting support in locality aware peer-to-peer overlay networks.

Application-level network relays possess many desirable properties, including support for communication between disconnected clients, increasing bandwidth between distant clients, and enabling routing around Internet failures. One problem not considered by existing systems is how to assign client load to relay servers in order to maximize throughput of the relay-system. In this paper, we are interested in the particular case where network conditions change frequently so that the ability of clients to adapt flow is restricted and each round of activity is critical. To this end, we present an algorithm, called Aggressive Increase, AAI which improves its competitive ratio in each time round that the network conditions persists. Given a relay network where a client connects to at most N servers, if network conditions persist for log(N) rounds then the algorithm's throughput becomes constant competitive. Our results improve upon the competitive ratio of previous work (of Awerbuch, Hajiaghayi, Kleinberg, and Leighton [2]). In addition we show that the AAI algorithm performs well in simulation studies as compared with the algorithm of [2] and an adaptation of the multiplicative increase algorithm of [8]. On a variety of input graphs, we show that the AAI algorithm typically reaches close to peak bandwidth levels within only a small constant (< 10) number of rounds.

File sharing is a very popular service provided by peer-to-peer (P2P) networks. In a P2P file-sharing network, users share files and issue queries to the network to find the locations of files residing at other peer nodes. Recently, proxy-enabled peers, or supernodes, have been incorporated to enhance scalability by providing indexing services to nodes on slower network connections. Typically, supernodes build a vector or multi-index of shared files stored on other (slower) peer nodes connected to them. We consider a new model whereby the index tables of individual nodes are merged into a single data structure stored by the supernode. We analyze this model in relation to the standard vectorized data structure. We compare the performance of these supernode indexing algorithms and provide a theoretical analysis that is asymptotic and probabilistic in nature. However, there are several significant constant factors that the theory does not account for, and which are important for designing an optimal system solution. We report on a series of simulation experiments which provide verification of the asymptotic analysis of the formal framework and tools to determine the magnitude of the constant factors. Our general conclusion is that when the query rate exceeds the rate of data updates, the new merged model is preferable to the vector model. However, the details of our analysis allow us to consider combinations of several parameters, and thereby enable the design of optimal indexing schemes via the incorporation of measurements of the parameters of particular applications.

In this paper we study the latency effects introduced in large scale internet applications. In particular, we study the effects of heterogeneous latency on reachability in decentralized, distributed networks operating under flooding protocols. We show that the standard protocol mechanisms of time-to-live (TTL) and unique message identification (UID), used to govern flooding message transmissions, can combine to potentially devastating effect on the reachability of message broadcast. We call this combined effect short-circuiting, and we investigate consequences of this phenomenon. We show that in the worstcase, short-circuiting resulting from heterogeneous latencies can near-completely eliminate the reach of broadcast messages, even with an ability to place k ⪈ 1 broadcast servers optimally. This dramatic negative effect on reachability shows that application protocol designs need to be sensitive to latency models. In addition, we show that short-circuiting can have a negative effect on well known approximation algorithms for maximizing reachability. We show that with respect to distance measures that account for short-circuiting, the standardk-center problem can not be approximated within n1-e, unless P = NP. Our theoretical results suggest that it may be quite difficult to find near optimal solutions to certain internet server selection problems. We consider the significance of our results on a large-scale peer-to-peer searching application, that relies on related flooding protocols. We report measurements through experimental studies with both simulated networks and a large network application known as Gnutella. Our empirical results, using statistics obtained from both the simulations and real applications, support the conclusion that, on average, the real effects of short-circuiting are significant, but not devastating to the performance of an overall large-scale system.

We introduce a natural distributed model for analyzing the survivability of distributed networks and network routing schemes based on considering the effects of local constraints on network connectivity. We investigate the computational consequences of two fundamental interpretations of the meaning of local constraints. We consider a full-duplex model in which constraints are applied to edges of a graph representing two-way communication links and a half-duplex model in which constraints are applied to edges representing one-wall links. We show that the problem of determining the survivability of a network under the full-duplex model is NP-hard, even in the restricted case of simply defined constraints. We also show that the problem of determining the survivability of network routing under the half-duplex model is highly tractable. We are able to effectively determine fault-tolerant routing schemes that are able to dynamically adapt to withstand any connectivity threats consistent with the constraints of the half-duplex model. The routing scheme is based on a multitree data structure, and we are able to generate optimal multitrees of minimum weighted depth. We also investigate an optimization problem related to achieving survivable network routing using a small sets of retransmission or landmark sites. Although the associated optimization problem is NP-hard, we show that sufficiently dense graphs can achieve survivable routing schemes using a small sets of landmarks. We prove an associated extremal result that is optimal over all graphs with minimum degree /spl delta/.

We present a mathematical model for network routing based on generating paths in a consistent direction. Our development is based on an algebraic and geometric framework for defining a directional coordinate system for real vector spaces. Our model, which generalizes graph st-numberings, is based on mapping the nodes of a network to points in multidimensional space and ensures that the paths generated in different directions from the same source are node-disjoint. Such directional embeddings encode the global disjoint path structure with very simple local information. We prove that all 3-connected graphs have 3-directional embeddings in the plane so that each node outside a set of extreme nodes has a neighbor in each of the three directional regions defined in the plane. We conjecture that the result generalizes to k-connected graphs. We also show that a directed acyclic graph (dag) that is k-connected to a set of sinks has a k-directional embedding in (k-1)-space with the sink set as the extreme nodes.

This paper presents a concise and efficient implementation of a method of producing De Bruijn sequences. The implementation is based on a recursive method due to A. Lempel (1970). We provide code for a function that for each pair of integers n/spl ges/2 and 0/spl les/x<2/sup n-2/ returns a unique De Bruijn sequence of order-n. The implementation requires only O(2/sup n/) bit operations.

Article Free Access Share on On testing consecutive-ones property in parallel Authors: F. S. Annexstein Department of ECECS, University of Cincinnati, Cincinnati, OH Department of ECECS, University of Cincinnati, Cincinnati, OHView Profile , R. P. Swaminathan Department of ECECS, University of Cincinnati, Cincinnati, OH Department of ECECS, University of Cincinnati, Cincinnati, OHView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 234–243https://doi.org/10.1145/215399.215449Published:20 July 1995Publication History 3citation257DownloadsMetricsTotal Citations3Total Downloads257Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A unified framework for finding efficient permutation routes on parallel networks in an off-line setting is presented.If the underlying graph of a parallel network contains an appropriate "approximate" product structure then our method guarantees the existence of non-blocking near-optimal permutation routes.The routes in question can be determined in polynomial time.Furthermore, our results are extended to finding permutation routes among the remaining "live" nodes in a faulty network.

The authors develop an algebraic framework that exposes the structural kinship among the deBruijn, shuffle-exchange, butterfly, and cube-connected cycles networks and illustrate algorithmic benefits that ensue from the exposed relationships. The framework builds on two alge-braically specified genres of graphs: A group action graph (GAG, for short) is given by a set V of vertices and a set $\Pi$ of permutations of V : For each $v \in V$ and each $\pi \in \Pi$, there is an arc labeled $\pi$ from vertex v to vertex $v \pi$. A Cayley graph is a $\operatorname{GAG}(V, \Pi)$, where V is the group ${\bf {\operatorname{Gr}}}(\Pi)$ generated by $\Pi$ and where each $\pi \in \Pi$ acts on each $g \in {\bf {\operatorname{Gr}}} (\Pi)$ by right multiplication. The graphs $({\bf {\operatorname{Gr}}}(\Pi), \Pi)$ and $(V, \Pi)$ are called associated graphs. It is shown that every ${\operatorname{GAG}}$ is a quotient graph of its associated Cayley graph. By applying such general results, the authors determine the following: • The butterfly network (a Cayley graph) and the deBruijn network (a ${\operatorname{GAG}}$) are associated graphs. • The cube-connected cycles network (a Cayley graph) and the shuffle-exchange network (a ${\operatorname{GAG}}$) are associated graphs. • The order-n instance of both the butterfly and the cube-connected cycles share the same underlying group, but have slightly different generator sets $\Pi$. By analyzing these algebraic results, it is delimited, for any Cayley graph $\mathcal{G}$ and associated $\operatorname{GAG} \mathcal{H}$, a family of “leveled” algorithms which run as efficiently on $\mathcal{H}$ as they do on (the much larger) $\mathcal{G}$. Further analysis of the results yields new, surprisingly efficient simulations by the shuffle-oriented networks (the shuffle-exchange and deBruijn networks) of like-sized butterfly-oriented networks (the butterfly and cube-connected cycles networks): • An N-vertex butterfly-oriented network can be simulated by the smallest shuffle-oriented network that is big enough to hold it with slowdown $O(\log \log N)$. This simulation is exponentially faster than the anticipated logarithmic slowdown. The mappings that underlie the simulation can be computed in linear time; and they afford one an algorithmic tech-nique for translating any program developed for a butterfly-oriented architecture into an equivalent program for a shuffle-oriented architecture, the latter program incurring only the indicated slowdown factor.

We present algbri~hms which reconfigure faulty deBruijn and Butterfly networks.We show that, with high probability, an N-node deBruijn (resp., Butterfly) network with uniformly distributed faulty processors can simulate a fault-free N-node deBrnijn (resp., Butterfly) network with a slowdown factor of O(loglogN).Our configuration algorithm is deterministic, operates in a distributed fashion, uses only local control, and takes time O (log 2 N). INTRODUCTIONIn any VLSI implementation of a large-scale computer network, some positive fraction of the processing elements are likely to contain faults.l~ecent work of Hastad, Leighton, and Newman [6] has shown that the hypercube has a strong fault-tolerance property: an N-node hypercube with a constant fraction of randomly distributed processor failures can still, with probability 1 -O(1/N), simulate the computation of a fault-free N-node hypercube, with only a constant factor slowdown in total pro-