TY - CONF
T1 - Brute force and indexed approaches to pairwise document similarity comparisons with MapReduce
T2 - Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval
Y1 - 2009
A1 - Jimmy Lin
KW - distributed algorithms
KW - hadoop
AB - This paper explores the problem of computing pairwise similarity on document collections, focusing on the application of "more like this" queries in the life sciences domain. Three MapReduce algorithms are introduced: one based on brute force, a second where the problem is treated as large-scale ad hoc retrieval, and a third based on the Cartesian product of postings lists. Each algorithm supports one or more approximations that trade effectiveness for efficiency, the characteristics of which are studied experimentally. Results show that the brute force algorithm is the most efficient of the three when exact similarity is desired. However, the other two algorithms support approximations that yield large efficiency gains without significant loss of effectiveness.
JA - Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval
T3 - SIGIR '09
PB - ACM
CY - New York, NY, USA
SN - 978-1-60558-483-6
UR - http://doi.acm.org/10.1145/1571941.1571970
M3 - 10.1145/1571941.1571970
ER -
TY - CONF
T1 - Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks
T2 - IEEE INFOCOM 2009
Y1 - 2009
A1 - Han,Bo
A1 - Kumar,V. S.A
A1 - Marathe,M. V
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - access hash function
KW - Channel allocation
KW - channel assignment algorithm
KW - channel capacity
KW - collision avoidance
KW - Computer science
KW - cryptography
KW - distributed algorithm
KW - distributed algorithms
KW - Educational institutions
KW - inductive-scheduling technique
KW - Interference
KW - interference set
KW - packet scheduling algorithm
KW - Peer to peer computing
KW - Radio network
KW - radio networks
KW - radiofrequency interference
KW - random oracle methodology
KW - scheduling
KW - Scheduling algorithm
KW - simultaneous channel allocation
KW - software radio
KW - software-defined radio wireless network capacity
KW - telecommunication congestion control
KW - telecommunication security
KW - Throughput
KW - wireless channels
KW - Wireless networks
AB - Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
JA - IEEE INFOCOM 2009
PB - IEEE
SN - 978-1-4244-3512-8
M3 - 10.1109/INFCOM.2009.5062069
ER -
TY - JOUR
T1 - Efficient lookup on unstructured topologies
JF - IEEE Journal on Selected Areas in Communications
Y1 - 2007
A1 - Morselli,R.
A1 - Bhattacharjee, Bobby
A1 - Marsh,M.A.
A1 - Srinivasan, Aravind
KW - Computer science
KW - DHT
KW - distributed algorithms
KW - Distributed computing
KW - distributed hash table
KW - Least squares approximation
KW - LMS
KW - local minima search
KW - lookup protocol
KW - Network topology
KW - node failures
KW - Peer to peer computing
KW - Performance analysis
KW - Protocols
KW - replication strategy
KW - Resilience
KW - Robustness
KW - table lookup
KW - telecommunication network topology
KW - unstructured network topology
AB - We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size
VL - 25
SN - 0733-8716
CP - 1
M3 - 10.1109/JSAC.2007.07007
ER -
TY - JOUR
T1 - Cooperative peer groups in NICE
JF - Computer Networks
Y1 - 2006
A1 - Sherwood,Rob
A1 - Lee,Seungjoon
A1 - Bhattacharjee, Bobby
KW - distributed algorithms
KW - P2P
KW - Reputation base trust
AB - We present a distributed scheme for trust inference in peer-to-peer networks. Our work is in the context of the NICE system, which is a platform for implementing cooperative applications over the Internet. We describe a technique for efficiently storing user reputation information in a completely decentralized manner, and show how this information can be used to efficiently identify non-cooperative users in NICE. We present a simulation-based study of our algorithms, in which we show our scheme scales to thousands of users using modest amounts of storage, processing, and bandwidth at any individual node. Lastly we show that our scheme is robust and can form cooperative groups in systems where the vast majority of users are malicious.
VL - 50
SN - 1389-1286
UR - http://www.sciencedirect.com/science/article/pii/S1389128605002185
CP - 4
M3 - 10.1016/j.comnet.2005.07.012
ER -
TY - CONF
T1 - Efficient lookup on unstructured topologies
T2 - Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing
Y1 - 2005
A1 - Morselli,Ruggero
A1 - Bhattacharjee, Bobby
A1 - Srinivasan, Aravind
A1 - Marsh,Michael A
KW - distributed algorithms
KW - lookup protocols
KW - peer-to-peer networks
KW - random walks
AB - We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT).We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.
JA - Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing
T3 - PODC '05
PB - ACM
CY - New York, NY, USA
SN - 1-58113-994-2
UR - http://doi.acm.org/10.1145/1073814.1073828
M3 - 10.1145/1073814.1073828
ER -
TY - CONF
T1 - Computing with very weak random sources
T2 - , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
Y1 - 1994
A1 - Srinivasan, Aravind
A1 - Zuckerman,D.
KW - Application software
KW - BPP simulations
KW - Chor-Goldreich sources
KW - computational complexity
KW - Computational modeling
KW - Computer science
KW - Computer simulation
KW - cryptography
KW - distributed algorithms
KW - expander constructions
KW - hardness
KW - MATHEMATICS
KW - min-entropy
KW - Physics computing
KW - Polynomials
KW - probability
KW - R-bit string
KW - randomness-efficient Leftover Hash Lemma
KW - RP algorithms simulation
KW - Testing
KW - time-space tradeoffs
KW - very weak random sources
AB - For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson
JA - , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
PB - IEEE
SN - 0-8186-6580-7
M3 - 10.1109/SFCS.1994.365688
ER -
TY - CONF
T1 - A distributed algorithm for ear decomposition
T2 - , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
Y1 - 1993
A1 - Hannenhalli, Sridhar
A1 - Perumalla,K.
A1 - Chandrasekharan,N.
A1 - Sridhar,R.
KW - Asynchronous communication
KW - asynchronous communication network
KW - Automata
KW - Communication networks
KW - computational complexity
KW - Computer networks
KW - Computer science
KW - decomposition graph
KW - distributed algorithm
KW - distributed algorithms
KW - Distributed computing
KW - Ear
KW - ear decomposition
KW - graph theory
KW - message-optimal
KW - network decomposition
KW - sorting
KW - Testing
KW - time-optimal
AB - A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
JA - , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
PB - IEEE
SN - 0-8186-4212-2
M3 - 10.1109/ICCI.1993.315382
ER -