Search Constraints
Filtering by:
Date Created
2009
Remove constraint Date Created: 2009
Publisher
Springer Berlin Heidelberg
Remove constraint Publisher: Springer Berlin Heidelberg
1  10 of 10
Number of results to display per page
Search Results

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos, Krizanc, Danny, Narayanan, Lata, and Keane, Michael
 Abstract:
 Delay (or disruption) tolerant sensor networks may be modeled as Markovian evolving graphs [1]. We present experimental evidence showing that considering multiple (possibly not shortest) paths instead of one fixed (greedy) path can decrease the expected time to deliver a packet on such a network by as much as 65 per cent depending on the probability that an edge exists in a given time interval. We provide theoretical justification for this result by studying a special case of the Markovian evolving grid graph. We analyze a natural algorithm for routing on such networks and show that it is possible to improve the expected time of delivery by up to a factor of two depending upon the probability of an edge being up during a time step and the relative positions of the source and destination. Furthermore we show that this is optimal, i.e., no other algorithm can achieve a better expected running time. As an aside, our results give high probability bounds for Knuth's toilet paper problem [11].
 Date Created:
 20091201

 Resource Type:
 Conference Proceeding
 Creator:
 He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
 Date Created:
 20091201

 Resource Type:
 Conference Proceeding
 Creator:
 Krizanc, D., Yazdani, M., Stacho, L., Narayanan, L., Lambadaris, Ioannis, Opatrny, J., Czyzowicz, J., Kranakis, Evangelos, and Urrutia, J.
 Abstract:
 We consider n mobile sensors located on a line containing a barrier represented by a finite line segment. Sensors form a wireless sensor network and are able to move within the line. An intruder traversing the barrier can be detected only when it is within the sensing range of at least one sensor. The sensor network establishes barrier coverage of the segment if no intruder can penetrate the barrier from any direction in the plane without being detected. Starting from arbitrary initial positions of sensors on the line we are interested in finding final positions of sensors that establish barrier coverage and minimize the maximum distance traversed by any sensor. We distinguish several variants of the problem, based on (a) whether or not the sensors have identical ranges, (b) whether or not complete coverage is possible and (c) in the case when complete coverage is impossible, whether or not the maximal coverage is required to be contiguous. For the case of n sensors with identical range, when complete coverage is impossible, we give linear time optimal algorithms that achieve maximal coverage, both for the contiguous and noncontiguous case. When complete coverage is possible, we give an O(n 2) algorithm for an optimal solution, a linear time approximation scheme with approximation factor 2, and a (1∈+∈ε) PTAS. When the sensors have unequal ranges we show that a variation of the problem is NPcomplete and identify some instances which can be solved with our algorithms for sensors with unequal ranges.
 Date Created:
 20091019

 Resource Type:
 Conference Proceeding
 Creator:
 Barbeau, Michel and Laurendeau, Christine
 Abstract:
 Increasingly ubiquitous wireless technologies require novel localization techniques to pinpoint the position of an uncooperative node, whether the target be a malicious device engaging in a security exploit or a lowbattery handset in the middle of a critical emergency. Such scenarios necessitate that a radio signal source be localized by other network nodes efficiently, using minimal information. We propose two new algorithms for estimating the position of an uncooperative transmitter, based on the received signal strength (RSS) of a single target message at a set of receivers whose coordinates are known. As an extension to the concept of centroid localization, our mechanisms weigh each receiver's coordinates based on the message's relative RSS at that receiver, with respect to the span of RSS values over all receivers. The weights may decrease from the highest RSS receiver either linearly or exponentially. Our simulation results demonstrate that for all but the most sparsely populated wireless networks, our exponentially weighted mechanism localizes a target node within the regulations stipulated for emergency services location accuracy.
 Date Created:
 20090928

 Resource Type:
 Conference Proceeding
 Creator:
 Smid, Michiel
 Date Created:
 20091016

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Howat, John, and Morin, Pat
 Abstract:
 The time required for a sequence of operations on a data structure is usually measured in terms of the worst possible such sequence. This, however, is often an overestimate of the actual time required. Distributionsensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are nonrandom in many applications. Unfortunately, many of the distribution sensitive structures in the literature require a great deal of space overhead in the form of pointers. We present a dictionary data structure that makes use of both randomization and existing spaceefficient data structures to yield very low space overhead while maintaining distribution sensitivity in the expected sense.
 Date Created:
 20090914

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Maheshwari, Anil, He, Meng, and Morin, Pat
 Abstract:
 We present a succinct representation of a set of n points on an n×n grid using bits to support orthogonal range counting in time, and range reporting in time, where k is the size of the output. This achieves an improvement on query time by a factor of upon the previous result of Mäkinen and Navarro [1], while using essentially the informationtheoretic minimum space. Our data structure not only can be used as a key component in solutions to the general orthogonal range search problem to save storage cost, but also has applications in text indexing. In particular, we apply it to improve two previous spaceefficient text indexes that support substring search [2] and positionrestricted substring search [1]. We also use it to extend previous results on succinct representations of sequences of small integers, and to design succinct data structures supporting certain types of orthogonal range query in the plane.
 Date Created:
 20090914

 Resource Type:
 Conference Proceeding
 Creator:
 Farshi, Mohammad, Abam, Mohammad Ali, Smid, Michiel, and Carmi, Paz
 Abstract:
 A SemiSeparated Pair Decomposition (SSPD), with parameter s > 1, of a set is a set {(A i ,B i )} of pairs of subsets of S such that for each i, there are balls and containing A i and B i respectively such that min ( radius ) , radius ), and for any two points p, q S there is a unique index i such that p A i and q B i or viceversa. In this paper, we use the SSPD to obtain the following results: First, we consider the construction of geometric tspanners in the context of imprecise points and we prove that any set of n imprecise points, modeled as pairwise disjoint balls, admits a tspanner with edges which can be computed in time. If all balls have the same radius, the number of edges reduces to . Secondly, for a set of n points in the plane, we design a query data structure for halfplane closestpair queries that can be built in time using space and answers a query in time, for any ε> 0. By reducing the preprocessing time to and using space, the query can be answered in time. Moreover, we improve the preprocessing time of an existing axisparallel rectangle closestpair query data structure from quadratic to nearlinear. Finally, we revisit some previously studied problems, namely spanners for complete kpartite graphs and lowdiameter spanners, and show how to use the SSPD to obtain simple algorithms for these problems.
 Date Created:
 20090914

 Resource Type:
 Conference Proceeding
 Creator:
 Gudmundsson, Joachim, Farshi, Mohammad, Smid, Michiel, De Berg, Mark, and Ali Abam, Mohammad
 Abstract:
 Let (S,d) be a finite metric space, where each element p S has a nonnegative weight w(p). We study spanners for the set S with respect to weighted distance function d w , where d w (p,q) is w(p)+d(p,q)+wq if p≠q and 0 otherwise. We present a general method for turning spanners with respect to the dmetric into spanners with respect to the d w metric. For any given ε>0, we can apply our method to obtain (5+ε)spanners with a linear number of edges for three cases: points in Euclidean space ℝ d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝ d where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)spanners for points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlogn). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any noncomplete graph has stretch factor larger than 2ε.
 Date Created:
 20091102

 Resource Type:
 Conference Proceeding
 Creator:
 Guo, Yuhong
 Abstract:
 In this paper, we present a novel semidefinite programming approach for multipleinstance learning. We first formulate the multipleinstance learning as a combinatorial maximum margin optimization problem with additional instance selection constraints within the framework of support vector machines. Although solving this primal problem requires nonconvex programming, we nevertheless can then derive an equivalent dual formulation that can be relaxed into a novel convex semidefinite programming (SDP). The relaxed SDP has free parameters where T is the number of instances, and can be solved using a standard interiorpoint method. Empirical study shows promising performance of the proposed SDP in comparison with the support vector machine approaches with heuristic optimization procedures.
 Date Created:
 20091201