Search Constraints

Start Over
Filtering by: Language English Remove constraint Language: English Resource Type Conference Proceeding Remove constraint Resource Type: Conference Proceeding

Search Results

  • A distribution-sensitive dictionary with low space overhead

    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. Distribution-sensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are non-random 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 space-efficient data structures to yield very low space overhead while maintaining distribution sensitivity in the expected sense.
    Date Created:
    2009-09-14

  • I/O-efficient shortest path queries in geometric spanners

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel, Zeh, Norbert, and Maheshwari, Anil
    Abstract:
    We present I/O-efficient 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:
    2001-01-01

  • Succinct orthogonal range search structures on a grid with applications to text indexing

    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 information-theoretic 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 space-efficient text indexes that support substring search [2] and position-restricted 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:
    2009-09-14

  • On the power of the semi-separated pair decomposition

    Resource Type:
    Conference Proceeding
    Creator:
    Farshi, Mohammad, Abam, Mohammad Ali, Smid, Michiel, and Carmi, Paz
    Abstract:
    A Semi-Separated 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 vice-versa. In this paper, we use the SSPD to obtain the following results: First, we consider the construction of geometric t-spanners in the context of imprecise points and we prove that any set of n imprecise points, modeled as pairwise disjoint balls, admits a t-spanner 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 half-plane closest-pair 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 axis-parallel rectangle closest-pair query data structure from quadratic to near-linear. Finally, we revisit some previously studied problems, namely spanners for complete k-partite graphs and low-diameter spanners, and show how to use the SSPD to obtain simple algorithms for these problems.
    Date Created:
    2009-09-14

  • Fréchet queries in geometric trees

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel and Gudmundsson, Joachim
    Date Created:
    2013-09-24

  • Black hole search in asynchronous rings using tokens

    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:
    2006-01-01

  • Geometric spanners for weighted point sets

    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 non-negative 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 d-metric 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 non-complete graph has stretch factor larger than 2-ε.
    Date Created:
    2009-11-02

  • Max-margin Multiple-Instance Learning via Semidefinite Programming

    Resource Type:
    Conference Proceeding
    Creator:
    Guo, Yuhong
    Abstract:
    In this paper, we present a novel semidefinite programming approach for multiple-instance learning. We first formulate the multiple-instance 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 non-convex 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 interior-point method. Empirical study shows promising performance of the proposed SDP in comparison with the support vector machine approaches with heuristic optimization procedures.
    Date Created:
    2009-12-01

  • Local maximal matching and local 2-approximation for vertex cover in UDGs (extended abstract)

    Resource Type:
    Conference Proceeding
    Creator:
    Wiese, Andreas and Kranakis, Evangelos
    Date Created:
    2008-11-26

  • Communication in random geometric radio networks with positively correlated random faults

    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 fault-free 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:
    2008-11-26

  • Fast feature-based video segmentation and annotation

    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 10-30 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:
    2003-01-01

  • Distributed storage in disruption tolerant network

    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 store-and-forward 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:
    2010-08-27

  • On the role of the input power constraint in the beamforming optimality range in TIMO channels

    Resource Type:
    Conference Proceeding
    Creator:
    Yanikomeroglu, Halim and Al-Ahmadi, Saad
    Date Created:
    2009-10-19

  • Object-level recombination of commodity applications

    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 well-known 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:
    2010-08-27

  • Multiple password interference in text passwords and click-based graphical passwords

    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 click-based graphical passwords. In a one-hour session (short-term), 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, click-based graphical passwords were significantly less susceptible to multiple password interference in the short-term, while having comparable usability to text passwords in most other respects. Copyright 2009 ACM.
    Date Created:
    2009-12-01

  • Facebooking in "face": Complex identities meet simple databases

    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 self-presentation 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 one-dimensional. 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:
    2015-01-01

  • Hacking with Multi-touch for Java (MT4j)

    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 multi-user input is harder. The Multi-Touch 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 co-located 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 multi-user touch based applications.
    Date Created:
    2016-10-21

  • Anomaly detection using weak estimators

    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 state-of-the-art 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 time-varying. 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 non-stationary 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:
    2012-09-22