Search Constraints
Filtering by:
Language
English
Remove constraint Language: English
Resource Type
Conference Proceeding
Remove constraint Resource Type: Conference Proceeding
« Previous 
101  118 of 118

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

 Resource Type:
 Conference Proceeding
 Creator:
 Whitehead, Anthony D.
 Abstract:
 we present a method of segmenting video to detect cuts with accuracy equal to or better than both histogram and other feature based methods. As well, the method is faster than other feature based methods. By utilizing feature tracking on corners, rather than lines, we are able to reliably detect features such as cuts, fades and salient frames. Experimental evidence shows that the method is able to withstand high motion situations better than existing methods. Initial implementations using full sized video frames are able to achieve processing rates of 1030 frames per second depending on the level of motion and number of features being tracked; this includes the time to generate the MPEG decompressed frames.
 Date Created:
 20030101

 Resource Type:
 Conference Proceeding
 Creator:
 Nayak, Amiya, Du, Jingzhe, and Kranakis, Evangelos
 Abstract:
 We describe a novel Distributed Storage protocol in Disruption (Delay) Tolerant Networks (DTN). Since DTNs can not guarantee the connectivity of the network all the time, distributed data storage and look up has to be performed in a storeandforward way. In this work, we define local distributed location regions which are called cells to facilitate the data storage and look up process. Nodes in a cell have high probability of moving within their cells. Our protocol resorts to storing data items in cells which have hierarchical structure to reduce routing information storage at nodes. Multiple copies of a data item may be stored at nodes to counter the adverse impact of the nature of DTNs. The cells are relatively stable regions and as a result, data exchange overheads among nodes are reduced. Through experimentation, we show that the proposed distributed storage protocol achieves higher successful data storage ratios with lower delays and limited data item exchange requirements than other protocols in the literature.
 Date Created:
 20100827

 Resource Type:
 Conference Proceeding
 Creator:
 Yanikomeroglu, Halim and AlAhmadi, Saad
 Date Created:
 20091019

 Resource Type:
 Conference Proceeding
 Creator:
 Foster, Blair and Somayaji, Anil
 Abstract:
 This paper presents ObjRecombGA, a genetic algorithm framework for recombining related programs at the object file level. A genetic algorithm guides the selection of object files, while a robust link resolver allows working program binaries to be produced from the object files derived from two ancestor programs. Tests on compiled C programs, including a simple web browser and a wellknown 3D video game, show that functional program variants can be created that exhibit key features of both ancestor programs. This work illustrates the feasibility of applying evolutionary techniques directly to commodity applications. Copyright 2010 ACM.
 Date Created:
 20100827

 Resource Type:
 Conference Proceeding
 Creator:
 Van Oorschot, Paul C., Biddle, Robert, Forget, Alain, Chiasson, Sonia, and Stobert, Elizabeth
 Abstract:
 The underlying issues relating to the usability and security of multiple passwords are largely unexplored. However, we know that people generally have difficulty remembering multiple passwords. This reduces security since users reuse the same password for different systems or reveal other passwords as they try to log in. We report on a laboratory study comparing recall of multiple text passwords with recall of multiple clickbased graphical passwords. In a onehour session (shortterm), we found that participants in the graphical password condition coped significantly better than those in the text password condition. In particular, they made fewer errors when recalling their passwords, did not resort to creating passwords directly related to account names, and did not use similar passwords across multiple accounts. After two weeks, participants in the two conditions had recall success rates that were not statistically different from each other, but those with text passwords made more recall errors than participants with graphical passwords. In our study, clickbased graphical passwords were significantly less susceptible to multiple password interference in the shortterm, while having comparable usability to text passwords in most other respects. Copyright 2009 ACM.
 Date Created:
 20091201

 Resource Type:
 Conference Proceeding
 Creator:
 Brubaker, Jed R., Handel, Mark, Yarosh, Svetlana, Bivens, Rena, Haimson, Oliver L., and Lingel, Jessa
 Abstract:
 Online systems often struggle to account for the complicated selfpresentation and disclosure needs of those with complex identities or specialized anonymity. Using the lenses of gender, recovery, and performance, our proposed panel explores the tensions that emerge when the richness and complexity of individual personalities and subjectivities run up against design norms that imagine identity as simplistic or onedimensional. These models of identity not only limit the ways individuals can express their own identities, but also establish norms for other users about what to expect, causing further issues when the inevitable dislocations do occur. We discuss the challenges in translating identity into these systems, and how this is further marred by technical requirements and normative logics that structure cultures and practices of databases, algorithms and computer programming.
 Date Created:
 20150101

 Resource Type:
 Conference Proceeding
 Creator:
 Noble, James, Marshall, Stuart, Anslow, Craig, and Biddle, Robert
 Abstract:
 Developing applications for touch devices is hard. Developing touch based applications for multiuser input is harder. The MultiTouch for Java (MT4j) toolkit supports developing touch based applications for multiple users. In this paper, we outline our experience using MT4j for developing a number of software applications to support developers working in colocated teams. Our experience using the toolkit will help developers to understand the nuances of the toolkit and design issues that can be applied to other toolkits for developing multiuser touch based applications.
 Date Created:
 20161021

 Resource Type:
 Conference Proceeding
 Creator:
 Oommen, B. John, Zhan, Justin, and Crisostomo, Johanna
 Abstract:
 Anomaly detection involves identifying observations that deviate from the normal behavior of a system. One of the ways to achieve this is by identifying the phenomena that characterize "normal" observations. Subsequently, based on the characteristics of data learned from the normal observations, new observations are classified as being either normal or not. Most stateoftheart approaches, especially those which belong to the family parameterized statistical schemes, work under the assumption that the underlying distributions of the observations are stationary. That is, they assume that the distributions that are learned during the training (or learning) phase, though unknown, are not timevarying. They further assume that the same distributions are relevant even as new observations are encountered. Although such a " stationarity" assumption is relevant for many applications, there are some anomaly detection problems where stationarity cannot be assumed. For example, in network monitoring, the patterns which are learned to represent normal behavior may change over time due to several factors such as network infrastructure expansion, new services, growth of user population, etc. Similarly, in meteorology, identifying anomalous temperature patterns involves taking into account seasonal changes of normal observations. Detecting anomalies or outliers under these circumstances introduces several challenges. Indeed, the ability to adapt to changes in nonstationary environments is necessary so that anomalous observations can be identified even with changes in what would otherwise be classified as normal behavior. In this paper, we proposed to apply weak estimation theory for anomaly detection in dynamic environments. In particular, we apply this theory to detect anomaly activities in system calls. Our experimental results demonstrate that our proposal is both feasible and effective for the detection of such anomalous activities.
 Date Created:
 20120922
 « Previous
 Next »
 1
 2
 3