Search Constraints
Filtering by:
Publisher
Springer Berlin Heidelberg
Remove constraint Publisher: Springer Berlin Heidelberg
« Previous 
41  50 of 50

Next »
Number of results to display per page
Search Results

 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:
 Smid, Michiel, Zeh, Norbert, and Maheshwari, Anil
 Abstract:
 We present I/Oefficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell” spanner of [6] for point sets in higher dimensions. As important ingredients to our algorithms, we present I/O efficient algorithms to color the vertices of a graph of bounded degree, answer binary search queries on topology buffer trees, and preprocess a rooted tree for answering prioritized ancestor queries.
 Date Created:
 20010101

 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:
 Smid, Michiel and Gudmundsson, Joachim
 Date Created:
 20130924

 Resource Type:
 Conference Proceeding
 Creator:
 Shi, Wei, Santoro, Nicola, Královič, R., and Dobrev, S.
 Abstract:
 A black hole is a highly harmful host that disposes of visiting agents upon their arrival. It is known that it is possible for a team of mobile agents to locate a black hole in an asynchronous ring network if each node is equipped with a whiteboard of at least O(log n) dedicated bits of storage. In this paper, we consider the less powerful token model: each agent has has available a bounded number of tokens that can be carried, placed on a node or removed from it. All tokens are identical (i.e., indistinguishable) and no other form of communication or coordination is available to the agents. We first of all prove that a team of two agents is sufficient to locate the black hole in finite time even in this weaker coordination model. Furthermore, we prove that this can be accomplished using only O(nlogn) moves in total, which is optimal, the same as with whiteboards. Finally, we show that to achieve this result the agents need to use only O(1) tokens each.
 Date Created:
 20060101

 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

 Resource Type:
 Conference Proceeding
 Creator:
 Wiese, Andreas and Kranakis, Evangelos
 Date Created:
 20081126

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos, Pelc, Andrzej, and Paquette, Michel
 Abstract:
 We study the feasibility and time of communication in random geometric radio networks, where nodes fail randomly with positive correlation. We consider a set of radio stations with the same communication range, distributed in a random uniform way on a unit square region. In order to capture fault dependencies, we introduce the ranged spot model in which damaging events, called spots, occur randomly and independently on the region, causing faults in all nodes located within distance s from them. Node faults within distance 2s become dependent in this model and are positively correlated. We investigate the impact of the spot arrival rate on the feasibility and the time of communication in the faultfree part of the network. We provide an algorithm which broadcasts correctly with probability 1  ε in faulty random geometric radio networks of diameter D in time O(D + log1/ε).
 Date Created:
 20081126