15971365
Efficiency of Data Distribution in BitTorrent-Like Systems
BitTorrent (BT) in practice is a very efficient method to share data over a network of clients. In this paper we extend the recent work of Arthur and Panigrahy [1] on modelling the distribution of individual data blocks in BT systems, aiming at a better understanding of why BT can achieve a high degree of parallelism. In particular, we include in our study several new network features that BT systems are using, as well as different local heuristics for routing data blocks in each client. We conduct simulations to figure out to what extent the new network features and routing heuristics would affect the distribution efficiency. Our findings confirm that for the primitive network setting studied in [1], it does require i¾?(blogn) phases for nclients to download bdata blocks. More interestingly, our work suggests that for the more realistic network setting, the heuristics Random and Rarest Block First both allow nclients to download bblocks in b+ O(logn) phases. We believe that the latter bound better reflects the high degree of parallelism of BT observed in reality. It is also worth-mentioning that b+ lognis the smallest possible number of phases needed; it is interesting to see that some simple local routing heuristics have a performance so close to the optimal.
15069863
Non-migratory online deadline scheduling on multiprocessors
In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors [8] or a migratory online schedule using m speed-2 processors [13]. Our result is based on a simple conservative scheduling algorithm called PARK which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.
17611435
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
We study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (highest density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using O(1) times unit-speed machines, are 1-competitive for flow time and stretch and O(1)-competitive for weighted flow time, respectively.
18562701
Compressed Index for a Dynamic Collection of Texts
Let T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2,4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P|log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T|log n) time.
34112863
Compressed Indexes for Approximate String Matching
We revisit the problem of indexing a string S[1..n] to support searching all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(mk) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m + occ + logn loglogn) time. The previously best solution achieving this time complexity requires an index of size O(n logn). This new index can be used to improve existing indexes for k ≥2 errors. Among others, it can support matching with k=2 errors in O(m logn loglogn + occ) time.
8031191
Dynamic dictionary matching and compressed suffix trees
Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length <i>n</i> from <i>O</i>(<i>n</i> log <i>n</i>) bits to <i>O</i>(<i>n</i>) bits, while allowing very efficient pattern matching [10, 13]. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first <i>O</i>(<i>n</i>)-bit representation of a suffix tree for a dynamic collection of texts whose total length is <i>n</i>, which supports insertion and deletion of a text <i>T</i> in <i>O</i>(|<i>T</i> | log<sup>2</sup> <i>n</i>) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an <i>O</i>(<i>d</i>)-bit data structure for a dynamic collection of patterns of total length <i>d</i> that can support the dictionary matching query efficiently. When compared with the <i>O</i>(<i>d</i> log <i>d</i>)-bit suffix tree based solution of Amir <i>et al.</i>, the compact solution increases the query time by roughly a factor of log <i>d</i> only. In the study of the above results, we also derive the first <i>O</i>(<i>n</i>)-bit representation for maintaining <i>n</i> pairs of balanced parentheses in <i>O</i>(log <i>n</i>/log log <i>n</i>) time per operation, matching the time complexity of the previous <i>O</i>(<i>n</i> log <i>n</i>)-bit solution.
34280688
Mammography Tomosynthesis System for High Performance 3D Imaging
Tomosynthesis provides a major advance in image quality compared to conventional projection mammography by effectively eliminating the effects of superimposed tissue on anatomical structures of interest. Early tomosynthesis systems focused primarily on feasibility assessment by providing 3-dimensional images to determine performance advantages. However, tomosynthesis image quality depends strongly on three key parameters: 1) detector performance at low dose, 2) angular range and number of projections acquired in the tomosynthesis scan, and 3) reconstruction algorithm processing characteristics used to create slice images from the measured projections. In this work, a new GE mammo-graphy tomosynthesis research system was developed that incorporates key improvements in each of these three areas compared to an early feasibility prototype system in use at Massachusetts General Hospital from 2000 to 2004. The performance gains that can be achieved by these enhancements are cha-racterized, and clinical images acquired with the system at the University of Michigan Cancer and Geriatrics Center are presented. The advanced research system also provides the ability to acquire mechanically co-registered x-ray tomosynthesis and ultrasound images of the breast, and initial dual modality images are also presented.
3053066
Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters
Previous work on sensitivity analysis in Bayesian networks has focused on single parameters, where the goal is to understand the sensitivity of queries to single parameter changes, and to identify single parameter changes that would enforce a certain query constraint. In this paper, we expand the work to multiple parameters which may be in the CPT of a single variable, or the CPTs of multiple variables. Not only do we identify the solution space of multiple parameter changes that would be needed to enforce a query constraint, but we also show how to find the optimal solution, that is, the one which disturbs the current probability distribution the least (with respect to a specific measure of disturbance). We characterize the computational complexity of our new techniques and discuss their applications to developing and debugging Bayesian networks, and to the problem of reasoning about the value (reliability) of new information.
5672538
When do Numbers Really Matter?
Common wisdom has it that small distinctions in the probabilities quantifying a belief network do not matter much for the results of probabilistic queries. Yet, one can develop realistic scenarios under which small variations in network probabilities can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytical results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They also help explain some of the previous experimental results and observations with regards to network robustness against parameter changes.
6130133
Security and Privacy in Sensor Networks
Sensor networks offer economically viable solutions for a variety of applications. For example, current implementations monitor factory instrumentation, pollution levels, freeway traffic, and the structural integrity of buildings. Other applications include climate sensing and control in office buildings and home environmental sensing systems for temperature, light, moisture, and motion. Sensor networks are key to the creation of smart spaces, which embed information technology in everyday home and work environments. The miniature wireless sensor nodes, or motes, developed from low-cost off-the-shelf components at the University of California, Berkeley, as part of its smart dust projects, establish a self-organizing sensor network when dispersed into an environment. The privacy and security issues posed by sensor networks represent a rich field of research problems. Improving network hardware and software may address many of the issues, but others will require new supporting technologies.
987821
Using Clustering Information for Sensor Network Localization
Sensor network localization continues to be an important research challenge. The goal of localization is to assign geographic coordinates to each node in the sensor network. Localization schemes for sensor network systems should work with inexpensive off-the-shelf hardware, scale to large networks, and also achieve good accuracy in the presence of irregularities and obstacles in the deployment area. 
 
We present a novel approach for localization that can satisfy all of these desired properties. Recent developments in sensor network clustering algorithms have resulted in distributed algorithms that produce highly regular clusters. We propose to make use of this regularity to inform our localization algorithm. The main advantages of our approach are that our protocol requires only three randomly-placed nodes that know their geographic coordinates, and does not require any ranging or positioning equipment (i.e., no signal strength measurement, ultrasound ranging, or directional antennas are needed). So far, only the DV-Hop localization mechanism worked with the same assumptions [1]. We show that our proposed approach may outperform DV-Hop in certain scenarios, in particular when there exist large obstacles in the deployment field, or when the deployment area is free of obstacles but the number of anchors is limited.