Search Constraints
Filtering by:
Language
English
Remove constraint Language: English
Resource Type
Conference Proceeding
Remove constraint Resource Type: Conference Proceeding
« Previous |
1 - 100 of 118
|
Next »
Number of results to display per page
Search Results
-
- Resource Type:
- Conference Proceeding
- Creator:
- Papineau, Maya
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Plourde, André
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Robinson, Fiona
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bivens, Rena
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Hoque, Anna Shah
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Farrall, Joanne
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Khan, Hashmat U. and Gunn, Christopher M.
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Winer, Stanley L.
- Abstract:
- Few people have bothered to defend the Majoritarian, winner take all character of the current Canadian electoral system. This parliamentary system has been in existence in the same form since the founding of the modern state in 1867. In these remarks, I offer a defense of Majoritarianism in the Canadian context when the alternative is some form of Proportional Representation. These remarks were prepared as an opening statement in a debate on electoral reform at a Faculty of Public Affairs 75th Anniversary conference at Carleton University, March 3, 2017. The debate arose because of the Prime Minister's announced intention to replace the current system with some other during the election campaign that led to his victory in 2015. The debate occurred a few months after the release of a lengthy report on electoral reform by a special allparty committee of the House of Commons. A few weeks before the debate, the Prime Minister announced (independently of the debate, of course) that his government would no longer pursue electoral reform, perhaps because it looked like he would not be able to avoid a referendum, a process which is hard to control. In any event, and especially in the light of recent attempts to change the system both at the federal level and in some provinces, I think it is important for people to understand that the existing electoral system is a sensible one that likely will continue to serve us well.
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Schwartz, Karen and Robinson, Fiona
- Date Created:
- 2017-03-04
-
- Resource Type:
- Conference Proceeding
- Creator:
- Saideman, Stephen M.
- Date Created:
- 2017-03-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Irving, Dan
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cockram, Louise
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Przednowek, Anna, Montgomery, Lauren, Khan, Ridhwan, Orr, Steven, Bueckert, Michael, and FitzGerald Murphy, Maggie
- Date Created:
- 2017-03-04
-
- Resource Type:
- Conference Proceeding
- Creator:
- Thomas, Paul E.J.
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Heidrich, Pablo
- Date Created:
- 2017-03-04
-
- Resource Type:
- Conference Proceeding
- Creator:
- Aske, Sherry
- Date Created:
- 2017-03-04
-
- Resource Type:
- Conference Proceeding
- Creator:
- FitzGerald Murphy, Maggie
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kaliberda, Elena
- Date Created:
- 2017-03-04
-
- Resource Type:
- Conference Proceeding
- Creator:
- Ghandeharian, Sacha
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Szyszlo, Peter
- Abstract:
- The purpose of this article is to improve understanding of internationalization as a strategic response to the catalysts of globalization and the knowledge society. The paper will attempt to critically identify and interpret how the aforementioned elements are being recontextualized and translated into responsive internationalization policies and systemic institutional change. The article takes a critical analysis approach on current internationalization efforts and provides a conceptual framework for developing a performance indicator set through a combination of institutional change theory (North 1990) and the Delta cycle for internationalization (Rumbley 2010). Recommendations on future research areas are made at the conclusion of the article.
- Date Created:
- 2016-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Rosenbloom, Daniel
- Date Created:
- 2017-03-02
-
- Resource Type:
- Conference Proceeding
- Creator:
- Browning, Jennifer
- Abstract:
- The use of open linked data in libraries is quickly developing as means of connecting digital content from the web to local library collections. In the world of cataloguing, metadata, and authority control, using controlled vocabularies through open linked data presents the possibility of providing library patrons with access to a seemingly unlimited expanse of digital resources. Encouraged by this potential, the Carleton University Library is currently implementing open linked data models within its institutional repository in order to connect users to digital content within our repository, our ILS, and beyond. This poster presents the ideas and processes behind this innovative project, and hopes to inspire other libraries to implement open linked data concepts in order to enhance the discoverability of their own digital collections. Learning Outcomes: • Clear explanation of open linked data concepts using diagrams to illustrate key points • How libraries of all sizes can utilize linked data for authority control to expand access to digital collections • How libraries can use linked data to promote and expand access to OA publications
- Date Created:
- 2016-01-28
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bucking, Scott
- Abstract:
- Energy modeling and optimization studies can facilitate the design of cost-effective, low-energy buildings. However, this process inevitably involves uncertainties such as predicting occupant behavior, future climate, and econometric parameters. As presently practiced, energy modelers typically do not quantify the implications of these unknowns into performance outcomes. This paper describes an energy modeling approach to quantify economic risk and better inform decision makers of the economic feasibility of a project. The proposed methodology suggests how economic uncertainty can be quantified within an optimization framework. This approach improves modeling outcomes by factoring in the effect of variability in assumptions and improves confidence in simulation results. The methodology is demonstrated using a net zero energy commercial office building case study located in London, ON, Canada.
- Date Created:
- 2016-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cross, Emma, Schramm, Cheryl, Skerlak, Steve, and Tucci, Ryan
- Date Created:
- 2016-05-10
-
- Resource Type:
- Conference Proceeding
- Creator:
- Neely, Colleen, Rumig, Joanne, Taylor, Christine, and Sharp, David
- Abstract:
- Since 2014, Carleton University Library has been adding to the ways it practices collection development. In addition to the subject liaison firm order model, we have added 3 successful user-centred ways to acquire material. We ended our approval plan and used its selection framework to create a DDA plan. We started a textbook purchasing program in Reserves, and we instituted print purchase on demand procedures in ILL. This poster provides an overview and key takeaways for each initiative.
- Date Created:
- 2016-11-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- van de Sande, Adje and Schwartz, Karen
- Date Created:
- 2008-05-30
-
- Resource Type:
- Conference Proceeding
- Creator:
- Jackson, Edward T. and Schwartz, Karen
- Date Created:
- 2008-05-30
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bucking, Scott
- Abstract:
- Energy models are commonly used to examine the multitude of pathways to improve building performance. As presently practiced, a deterministic approach is used to evaluate incremental design improvements to achieve performance targets. However, significant insight can be gained by examining the implications of modeling assumptions using a probabilistic approach. Analyzing the effect of small perturbations on the inputs of energy and economic models can improve decision making and modeler confidence in building simulation results. This paper describes a reproducible methodology which AIDS modelers in identifying energy and economic uncertainties caused by variabilities in solar exposure. Using an optimization framework, uncertainty is quantified across the entire simulation solution space. This approach improves modeling outcomes by factoring in the effect of variability in assumptions and improves confidence in simulation results. The methodology is demonstrated using a net zero energy commercial office building case study.
- Date Created:
- 2017-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bucking, Scott and Cotton, James S.
- Abstract:
- Net zero energy (NZE) communities are becoming pivotal to the energy vision of developers. Communities that produce as much energy as they consume provide many benefits, such as reducing life-cycle costs and better resilience to grid outages. If deployed using smart-grid technology, NZE communities can act as a grid node and aid in balancing electrical demand. However, identifying cost-effective pathways to NZE requires detailed energy and economic models. Information required to build such models is not typically available at the early master-planning stages, where the largest energy and economic saving opportunities exist. Methodologies that expedite and streamline energy and economic modeling could facilitate early decision making. This paper describes a reproducible methodology that aids modelers in identifying energy and economic savings opportunities in the early community design stages. As additional information becomes available, models can quickly be recreated and evaluated. The proposed methodology is applied to the first-phase design of a NZE community under development in Southwestern Ontario.
- Date Created:
- 2015-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Tucci, Ryan
- Abstract:
- Libraries are quickly becoming spaces for more than just books and journals. At Carleton University MacOdrum Library, we used Minecraft to introduce elementary and high school students to the power of gaming as a tool to foster education, research and collaboration. In May 2015, we encouraged students to take part in a project that engaged them with a local project called the LeBreton Flats Redevelopment Project. The redevelopment project led by the National Capital Commission (NCC), shortlisted four developers and published their proposals for the community to see. Using the criteria presented by the four pre-qualified proponents, the students were asked to research and propose their own ideas for the space. Using a scale version of the space in Minecraft, the students built their proposed plan for the space in a 1:1 scale replica of LeBreton Flats.
- Date Created:
- 2016-01-29
-
- Resource Type:
- Conference Proceeding
- Creator:
- Tudin, Susan
- Abstract:
- Poster presented at the Teaching & Learning Symposium, Carleton University, May 11, 2016
- Date Created:
- 2016-05-11
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bucking, Scott
- Abstract:
- Net-zero energy is an influential idea in guiding the building stock towards renewable energy resources. Increasingly, this target is scaled to entire communities which may include dozens of buildings in each new development phase. Although building energy modelling processes and codes have been well developed to guide decision making, there is a lack of methodologies for community integrated energy masterplanning. The problem is further complicated by the availability of district systems which better harvest and store on-site renewable energy. In response to these challenges, this paper contributes an energy modelling methodology which helps energy masterplanners determine trade-offs between building energy saving measures and district system design. Furthermore, this paper shows that it is possible to mitigate electrical and thermal peaks of a net-zero energy community using minimal district equipment. The methodology is demonstrated using a cold-climate case-study with both significant heating/ cooling loads and solar energy resources.
- Date Created:
- 2017-07-25
-
- Resource Type:
- Conference Proceeding
- Creator:
- Duimovich, George
- Abstract:
- Presentation to Data Science Seminar at Carleton University, Institute for Data Science, May 11, 2016.
- Date Created:
- 2016-05-11
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cross, Emma
- Abstract:
- Resource Description and Access is the new content standard coming Spring 2013, with national libraries using RDA effective March 30, 2013. Libraries need to address training for staff in all departments on how to interpret, catalogue and use RDA records.
- Date Created:
- 2013-02-13
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cross, Emma and Merriam, Helena
- Date Created:
- 2017-05-12
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cross, Emma
- Date Created:
- 2017-05-31
-
- Resource Type:
- Conference Proceeding
- Creator:
- Neely, Colleen
- Abstract:
- Webinar presented to members of the Ontario Council of University Libraries, June 29, 2011.
- Date Created:
- 2011-06-29
-
- Resource Type:
- Conference Proceeding
- Creator:
- Whitehead, Anthony D.
- Abstract:
- There have been a number of steganography embedding techniques proposed over the past few years. In turn, there has been great interest in steganalysis techniques as the embedding techniques improve. Specifically, universal steganalysis techniques have become more attractive since they work independently of the embedding technique. In this work, we examine the effectiveness of a basic universal technique that relies on some knowledge about the cover media, but not the embedding technique. We consider images as a cover media, and examine how a single technique that we call steganographic sanitization performs on 26 different steganography programs that are publicly available on the Internet. Our experiments are completed using a number of secret messages and a variety of different levels of sanitization. However, since our intent is to remove covert communication, and not authentication information, we examine how well the sanitization process preserves authentication information such as watermarks and digital fingerprints.
- Date Created:
- 2005-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Opp, James and Whitehead, Anthony D.
- Abstract:
- In this work we discuss our efforts to use the ubiquity of smart phone systems and the mobility they provide to stream historical information about your current place on the earth to the end user. We propose the concept of timescapes to portray this historical significance of where they are standing and allow a brief travel through time. By combining GPS location, with a rich media interpretation of existing historical documents, historical facts become an on-demand resource available to travellers, school children, historians and any interested 3rd party. To our knowledge this is the first introduction of the term timescape to be used in the context of historical information pull. Copyright
- Date Created:
- 2013-09-05
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bucking, Scott, Zmeureanu, Radu, and Athienitis, Andreas
- Abstract:
- This paper presents a multi-objective redesign case study of an archetype solar house based on a near net zero energy (NZE) demonstration home located in Eastman, Quebec. Using optimization techniques, pathways are identified from the original design to both cost and energy optimal designs. An evolutionary algorithm is used to optimize trade-offs between passive solar gains and active solar generation, using two objective functions: net-energy consumption and life-cycle cost over a thirty-year life cycle. In addition, this paper explores different pathways to net zero energy based on economic incentives, such as feed-in tariffs for on-site electricity production from renewables. The main objective is to identify pathways to net zero energy that will facilitate the future systematic design of similar homes based on the concept of the archetype that combines passive solar design; energy-efficiency measures, including a geothermal heat pump; and a building-integrated photovoltaic system. Results from this paper can be utilized as follows: (1) systematic design improvements and applications of lessons learned from a proven NZE home design concept, (2) use of a methodology to understand pathways to cost and energy optimal building designs, and (3) to aid in policy development on economic incentives that can positively influence optimized home design.
- Date Created:
- 2014-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Chiasson, Sonia, Forget, Alain, Biddle, Robert, and Van Oorschot, Paul C.
- Abstract:
- Usable security has unique usability challenges because the need for security often means that standard human-computerinteraction approaches cannot be directly applied. An important usability goal for authentication systems is to support users in selecting better passwords, thus increasing security by expanding the effective password space. In click-based graphical passwords, poorly chosen passwords lead to the emergence of hotspots ' portions of the image where users are more likely to select click-points, allowing attackers to mount more successful dictionary attacks. We use persuasion to influence user choice in click-based graphical passwords, encouraging users to select more random, and hence more secure, click-points. Our approach is to introduce persuasion to the Cued Click-Points graphical password scheme (Chiasson, van Oorschot, Biddle, 2007). Our resulting scheme significantly reduces hotspots while still maintaining its usability.
- Date Created:
- 2008-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Walsh, John C.
- Date Created:
- 2011-05-31
-
- Resource Type:
- Conference Proceeding
- Creator:
- Hilton, Robert, Stoney, Christopher, and Shepherd, Robert
- Date Created:
- 2010-06-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Neely, Colleen, Davis, Kate, Jin, Lei, and Rykse, Harriet
- Abstract:
- Presented at Electronic Resources & Libraries Conference, Austin, TX, February 28, 2011.
- Date Created:
- 2011-02-28
-
- 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
-
- 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
-
- 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
-
- 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
-
- Resource Type:
- Conference Proceeding
- Creator:
- Yanikomeroglu, Halim and Al-Ahmadi, Saad
- Date Created:
- 2009-10-19
-
- 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
-
- 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
-
- 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
-
- Resource Type:
- Conference Proceeding
- Creator:
- Wiese, Andreas and Kranakis, Evangelos
- Date Created:
- 2008-11-26
-
- 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
-
- 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
-
- 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
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel and Gudmundsson, Joachim
- Date Created:
- 2013-09-24
-
- 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
-
- 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
-
- 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
-
- 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
-
- Resource Type:
- Conference Proceeding
- Creator:
- Zeh, Norbert, Hutchinson, David, and Maheshwari, Anil
- Abstract:
- We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.
- Date Created:
- 1999-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel, Maheshwari, Anil, Das, Sandip, and Banik, Aritra
- Abstract:
- Let P be a simple polygon with m vertices and let be a set of n points in P. We consider the points of to be users. We consider a game with two players and. In this game, places a point facility inside P, after which places another point facility inside P. We say that a user is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by, an optimal placement for can be computed in O(m + n(logn + logm)) time. We also provide a polynomial-time algorithm for computing an optimal placement for.
- Date Created:
- 2013-10-08
-
- Resource Type:
- Conference Proceeding
- Creator:
- Gardezi, Jaffer and Bertossi, Leopoldo
- Abstract:
- Matching Dependencies (MDs) are a recent proposal for declarative entity resolution. They are rules that specify, given the similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The clean answers to queries (which we call the resolved answers) are invariant under the resulting class of instances. In this paper, we investigate a query rewriting approach to obtaining the resolved answers (for certain classes of queries and MDs). The rewritten queries are specified in stratified Datalog not,s with aggregation. In addition to the rewriting algorithm, we discuss the semantics of the rewritten queries, and how they could be implemented by means of a DBMS.
- Date Created:
- 2012-10-10
-
- Resource Type:
- Conference Proceeding
- Creator:
- Ponce, Oscar Morales, Pacheco, Eduardo, Kranakis, Evangelos, Ga̧sieniec, Leszek, Czyzowicz, Jurek, and Kosowski, Adrian
- Abstract:
- A collection of n anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of position discovery, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same position detection algorithm, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots. Some initial configuration of robots are shown to be infeasible - no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction. If the less frequently used initial direction is given to k ≤ n/2 robots, the time until completion of the algorithm by the last robot is 1/2 ⌈n/k⌉. We prove that this time is optimal. By contrast to the case of the ring, for the unit segment we show that the family of infeasible configurations is exactly the set of so-called symmetric configurations. We give a position detection algorithm which works for all feasible configurations on the segment in time 2, and this algorithm is also proven to be optimal.
- Date Created:
- 2012-11-09
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel
- Date Created:
- 2009-10-16
-
- Resource Type:
- Conference Proceeding
- Creator:
- Jiang, Lei, Bertossi, Leopoldo, and Rizzolo, Flavio
- Abstract:
- We motivate, formalize and investigate the notions of data quality assessment and data quality query answering as context dependent activities. Contexts for the assessment and usage of a data source at hand are modeled as collections of external databases, that can be materialized or virtual, and mappings within the collections and with the data source at hand. In this way, the context becomes "the complement" of the data source wrt a data integration system. The proposed model allows for natural extensions, like considering data quality predicates, and even more expressive ontologies for data quality assessment.
- Date Created:
- 2011-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Loke, R. K.S. and Oommen, B. John
- Abstract:
- We consider a problem which can greatly enhance the areas of cursive script recognition and the recognition of printed character sequences. This problem involves recognizing words/strings by processing their noisy subsequences. Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We study the problem of estimating X* by processing Y, a noisy version of U. Y contains substitution, insertion, deletion and generalized transposition errors — the latter occurring when transposed characters are themselves subsequently substituted. We solve the noisy subsequence recognition problem by defining and using the constrained edit distance between X ε H and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Using these algorithms we present a syntactic Pattern Recognition (PR) scheme which corrects noisy text containing all these types of errors. Experimental results which involve strings of lengths between 40 and 80 with an average of 30.24 deleted characters and an overall average noise of 68.69 % demonstrate the superiority of our system over existing methods.
- Date Created:
- 1995-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Markou, Euripides, Kranakis, Evangelos, and Krizanc, Danny
- Abstract:
- We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n × m (respectively, n × n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a n × m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in such a network.
- Date Created:
- 2006-07-10
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos, Morin, Pat, and Krizanc, Danny
- Abstract:
- We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show that there exists a 2t state agent, which can achieve rendez-vous on an n node ring in expected time O( n 2/2 t ∈+∈2 t ) and that any t/2 state agent requires expected time Ω( n 2/2 t ). As a corollary we observe that Θ(loglogn) bits of memory are necessary and sufficient to achieve rendez-vous in linear time.
- Date Created:
- 2008-05-12
-
- Resource Type:
- Conference Proceeding
- Creator:
- Dujmović, Vida, Wood, David, and Bose, Prosenjit
- Abstract:
- We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.
- Date Created:
- 2005-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Mirandola, Raffaela, Grassi, Vincenzo, Sabetta, Antonino, and Petriu, Dorina C.
- Abstract:
- The verification of non-functional requirements of software models (such as performance, reliability, scalability, security, etc.) requires the transformation of UML models into different analysis models such as Petri nets, queueing networks, formal logic, etc., which represent the system at a higher level of abstraction. The paper proposes a new "abstraction-raising" transformation approach for generating analysis models from UML models. In general, such transformations must bridge a large semantic gap between the source and the target model. The proposed approach is illustrated by a transformation from UML to Klaper (Kernel LAnguage for PErformance and Reliability analysis of component-based systems).
- Date Created:
- 2006-07-06
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel and Gudmundsson, Joachim
- Abstract:
- Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every t with 1 1+1/t) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(tn1+2/(t+1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs.
- Date Created:
- 2006-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Biddle, Robert, Noble, James, Barr, Pippin, Fischer, Ronald, and Khaled, Rilla
- Abstract:
- Persuasive technologies are increasingly ubiquitous, but the strategies they utilise largely originate in America. Consumer behaviour research shows us that certain persuasion strategies will be more effective on some cultures than others. We claim that the existing strategies will be less effective on non-American audiences than they are on American audiences, and we use information from interviews to show that there exists much scope to develop persuasive technologies from a collectivism-focused perspective. To illustrate the development of such a tool, we describe the design of a collectivism-focused financial planning tool.
- Date Created:
- 2006-07-17
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos and Wiese, Andreas
- Abstract:
- We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting. The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.
- Date Created:
- 2008-07-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
- Abstract:
- Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)-spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)-spanner for P that has O(|P|) edges and chromatic number at most k. Finally, we consider an on-line variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
- Date Created:
- 2008-08-27
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos, Shi, Q., Bhattacharya, B., Wiese, A., Burmester, B., and Hu, Y.
- Abstract:
- Intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. They can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. We consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. We discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.
- Date Created:
- 2008-09-22
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
- Abstract:
- It is well-known that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in d-dimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
- Date Created:
- 2008-10-27
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos and Wiese, Andreas
- Abstract:
- We investigate the problem of locally coloring and constructing special spanners of location aware Unit Disk Graphs (UDGs). First we present a local approximation algorithm for the vertex coloring problem in UDGs which uses at most four times as many colors as required by an optimal solution. Then we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4-colorable spanner of a unit disk graph. The output consists of the spanner and the 4-coloring. The computed spanner also has the properties that it is planar, the degree of a vertex in the spanner is at most 5 and the angles between two edges are at least π/3. By enlarging the locality distance (i.e. the size of the neighborhood which a vertex has to explore in order to compute its color) we can ensure the total weight of the spanner to be arbitrarily close to the weight of a minimum spanning tree. We prove that a local algorithm cannot compute a bipartite spanner of a unit disk graph and therefore our algorithm needs at most one color more than any local algorithm for the task requires. Moreover, we prove that there is no local algorithm for 3-coloring UDGs or spanners of UDGs, even if the 3-colorability of the graph (or the spanner respectively) is guaranteed in advance.
- Date Created:
- 2008-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Petriu, Dorina C. and Tawhid, Rasha
- Abstract:
- The paper proposes to integrate performance analysis in the early phases of the model-driven development process for Software Product Lines (SPL). We start by adding generic performance annotations to the UML model representing the set of core reusable SPL assets. The annotations are generic and use the MARTE Profile recently adopted by OMG. A first model transformation realized in the Atlas Transformation Language (ATL), which is the focus of this paper, derives the UML model of a specific product with concrete MARTE performance annotations from the SPL model. A second transformation generates a Layered Queueing Network performance model for the given product by applying an existing transformation approach named PUMA, developed in previous work. The proposed technique is illustrated with an e-commerce case study that models the commonality and variability in both structural and behavioural SPL views. A product is derived and the performance of two design alternatives is compared.
- Date Created:
- 2008-11-28
-
- Resource Type:
- Conference Proceeding
- Creator:
- Dillabaugh, Craig, He, Meng, and Maheshwari, Anil
- Abstract:
- We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottom-up path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for top-down traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.
- Date Created:
- 2008-12-01
-
- 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 low-battery 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:
- 2009-09-28
-
- 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 non-contiguous 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 NP-complete and identify some instances which can be solved with our algorithms for sensors with unequal ranges.
- Date Created:
- 2009-10-19
-
- Resource Type:
- Conference Proceeding
- Creator:
- He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
- Date Created:
- 2009-12-01
-
- 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:
- 2009-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Barbeau, Michel, Kranakis, Evangelos, and Garcia-Alfaro, Joaquin
- Abstract:
- The design and implementation of security threat mitigation mechanisms in RFID systems, specially in low-cost RFID tags, are gaining great attention in both industry and academia. One main focus of research interests is the authentication and privacy techniques to prevent attacks targeting the insecure wireless channel of these systems. Cryptography is a key tool to address these threats. Nevertheless, strong hardware constraints, such as production costs, power consumption, time of response, and regulations compliance, makes the use of traditional cryptography in these systems a very challenging problem. The use of low-overhead procedures becomes the main approach to solve these challenging problems where traditional cryptography cannot fit. Recent results and trends, with an emphasis on lightweight techniques for addressing critical threats against low-cost RFID systems, are surveyed.
- Date Created:
- 2010-05-03
-
- Resource Type:
- Conference Proceeding
- Creator:
- Czyzowicz, Jurek, Opatrny, Jaroslav, Kranakis, Evangelos, Narayanan, Lata, Krizanc, Danny, Stacho, Ladislav, Urrutia, Jorge, Yazdani, Mohammadreza, and Lambadaris, Ioannis
- Abstract:
- A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned.
- Date Created:
- 2010-12-13
-
- Resource Type:
- Conference Proceeding
- Creator:
- Cervera, Gimer, Barbeau, Michel, Garcia-Alfaro, Joaquin, and Kranakis, Evangelos
- Abstract:
- The Hierarchical Optimized Link State Routing (HOLSR) protocol enhances the scalability and heterogeneity of traditional OLSR-based Mobile Ad-Hoc Networks (MANETs). It organizes the network in logical levels and nodes in clusters. In every cluster, it implements the mechanisms and algorithms of the original OLSR to generate and to distribute control traffic information. However, the HOLSR protocol was designed with no security in mind. Indeed, it both inherits, from OLSR, and adds new security threats. For instance, the existence of misbehaving nodes can highly affect important HOLSR operations, such as the cluster formation. Cluster IDentification (CID) messages are implemented to organize a HOLSR network in clusters. In every message, the hop count field indicates to the receiver the distance in hops to the originator. An attacker may maliciously alter the hop count field. As a consequence, a receiver node may join a cluster head farther away than it appears. Then, the scalability properties in a HOLSR network is affected by an unbalanced distribution of nodes per cluster. We present a solution based on the use of hash chains to protect mutable fields in CID messages. As a consequence, when a misbehaving node alters the hop count field in a CID message, the receiver nodes are able of detecting and discarding the invalid message.
- Date Created:
- 2012-01-27
-
- Resource Type:
- Conference Proceeding
- Creator:
- Van Walderveen, Freek, Davoodi, Pooya, and Smid, Michiel
- Abstract:
- Given a set of n points in the plane, range diameter queries ask for the furthest pair of points in a given axis-parallel rectangular range. We provide evidence for the hardness of designing space-efficient data structures that support range diameter queries by giving a reduction from the set intersection problem. The difficulty of the latter problem is widely acknowledged and is conjectured to require nearly quadratic space in order to obtain constant query time, which is matched by known data structures for both problems, up to polylogarithmic factors. We strengthen the evidence by giving a lower bound for an important subproblem arising in solutions to the range diameter problem: computing the diameter of two convex polygons, that are separated by a vertical line and are preprocessed independently, requires almost linear time in the number of vertices of the smaller polygon, no matter how much space is used. We also show that range diameter queries can be answered much more efficiently for the case of points in convex position by describing a data structure of size O(n log n) that supports queries in O(log n) time.
- Date Created:
- 2012-05-15
-
- Resource Type:
- Conference Proceeding
- Creator:
- Mannan, Mohammad, Barrera, David, Van Oorschot, Paul C., Lie, David, and Brown, Carson D.
- Abstract:
- Instead of allowing the recovery of original passwords, forgotten passwords are often reset using online mechanisms such as password verification questions (PVQ methods) and password reset links in email. These mechanisms are generally weak, exploitable, and force users to choose new passwords. Emailing the original password exposes the password to third parties. To address these issues, and to allow forgotten passwords to be securely restored, we present a scheme called Mercury. Its primary mode employs user-level public keys and a personal mobile device (PMD) such as a smart-phone, netbook, or tablet. A user generates a key pair on her PMD; the private key remains on the PMD and the public key is shared with different sites (e.g., during account setup). For password recovery, the site sends the (public key)-encrypted password to the user's pre-registered email address, or displays the encrypted password on a webpage, e.g., as a barcode. The encrypted password is then decrypted using the PMD and revealed to the user. A prototype implementation of Mercury is available as an Android application.
- Date Created:
- 2012-02-21
-
- Resource Type:
- Conference Proceeding
- Creator:
- Seidel, Raimund, Dehne, Frank, and Klein, Rolf
- Abstract:
- Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there is at most one local maximum.
- Date Created:
- 2002-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bose, Prosenjit and Van Renssen, André
- Abstract:
- We present tight upper and lower bounds on the spanning ratio of a large family of constrained θ-graphs. We show that constrained θ-graphs with 4k2 (k≥ 1 and integer) cones have a tight spanning ratio of 1+2 sin(θ/2), where θ is 2 π/ (4k+2). We also present improved upper bounds on the spanning ratio of the other families of constrained θ-graphs.
- Date Created:
- 2014-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Peleg, David, Krizanc, Danny, Kirousis, Lefteris M., Kranakis, Evangelos, Kaklamanis, Christos, and Bose, Prosenjit
- Abstract:
- In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius r, r < R, such that the signal originating from the center of the station is so strong that human habitation within distance r from the center p should be avoided. Thus every station determines a region which is an “annulus of permissible habitation". We consider the following station layout (SL) problem: Cover a given (say, rectangular) planar region which includes a collection of orthogonal buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no building is within the dangerous range of a station. We give algorithms for computing such station layouts in both the one-and two-dimensional cases.
- Date Created:
- 1999-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Maheshwari, Anil, Sack, Jörg-Rüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
- Date Created:
- 1998-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Krizanc, Danny, Kranakis, Evangelos, and Kirousis, Lefteris M.
- Abstract:
- Let φ be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that κ 3.
- Date Created:
- 1996-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Morin, Pat and Bose, Prosenjit
- Abstract:
- We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
- Date Created:
- 1999-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Maheshwari, Anil and Zeh, Norbert
- Abstract:
- We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a2-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
- Date Created:
- 1999-01-01