Search Constraints

Search Results

  • Sanction Royale à projet de loi C-81, Loi visant à faire du Canada un pays exempt d’obstacles : extraits

    Resource Type:
    Video
    Creator:
    Accommodation Councilors of Canada Network and AccessibiliTV
    Description:
    Highlights of documentary footage from June 21, 2019, proceedings of the Senate, when Bill C-81 received Royal Assent. In French with French subtitles.
    Date Created:
    2019

  • Royal Assent to Bill C-81, Accessible Canada Act: documentary footage and interviews

    Resource Type:
    Video
    Creator:
    Accommodation Councilors of Canada Network
    Description:
    Two and a half hours of documentary footage from June 21, 2019, proceedings of the Senate when Bill C-81 received Royal Assent. The footage takes viewers behind the scenes with individuals closely involved with ensuring the Act received Royal Assent and features interviews with the Honourable Carla Qualtrough, Senator Jim Munson, James van Raalte, Sinead Tuite, Bill Adair, and Frank Folino.
    Date Created:
    2019

  • Royal Assent to Bill C-81, Accessible Canada Act: highlights

    Resource Type:
    Video
    Creator:
    AccessibiliTV and Accommodation Councilors of Canada Network
    Description:
    Highlights of documentary footage from June 21, 2019, proceedings of the Senate, when Bill C-81 received Royal Assent. Subtitled in English.
    Date Created:
    2019

  • Fabrication of electron beam generated, chirped, phase mask (1070 . 11 – 1070 . 66 nm) for fiber Bragg grating dispersion compensator

    Resource Type:
    Article
    Creator:
    Hill, K.O., Johnson, D.C., Mihailov, S.J., McClelland, A.W., Stryckman, D., Bilodeau, F., Albert, Jacques, Carr, D.W., Hugues, B.J., Tiberio, R.C., and Rooks, M.J.
    Abstract:
    We report on the fabrication of a chirped, phase mask that was used to create a fiber Bragg grating(FBG)device for the compensation of chromatic dispersion in longhaul optical transmission networks.Electron beamlithography was used to expose the grating onto a resist-coated quartz plate. After etching, this phase mask was used to holographically expose an index grating into the fiber core [K. O. Hill, F. Bilodeau, D. C. Johnson, and J. Albert, Appl. Phys. Lett.62, 1035 (1993)]. The linear increase in the grating period, “chirp,” is only 0.55 nm over the 10 cm grating. This is too small to be defined by computer aided design and a digital deflection system. Instead, the chirp was incorporated by repeatedly rescaling the analog electronics used for field size calibration. Special attention must be paid to minimize any field stitching and exposure artifacts. This was done by using overlapping fields in a “voting” method. As a result, each grating line is exposed by the accumulation of three overlapping exposures at 1/3 dose. This translates any abrupt stitching error into a small but uniform change in the line-to-space ratio of the grating. The phase mask was used with the double-exposure photoprinting technique [K. O. Hill, F. Bilodeau, B. Malo, T. Kitagawa, S. Thériault, D. C. Johnson, J. Albert, and K. Takiguchi, Opt. Lett. 19, 1314 (1994)]: a KrF excimer laser holographically imprints an apodized chirped Bragg grating in a hydrogen loaded SMF-28 optical fiber. Our experiments have demonstrated a spectral delay of −1311 ps/nm with a linearity of +/−10 ps over the 3 dB bandwidth of the resonant wavelength of the FBG. The reflectance, centered on 1550 nm, shows a side-lobe suppression of −25 dB. Fabrication processes and optical characterization will be discussed.
    Date Created:
    1998-09-16

  • 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

  • A thin metal sheath lifts the EH to HE degeneracy in the cladding mode refractometric sensitivity of optical fiber sensors

    Resource Type:
    Article
    Creator:
    Albert, Jacques, Berini, P., Chen, Chengkun, Caucheteur, C., and Voisin, V.
    Abstract:
    The effective indices of the cladding modes of optical fibers depend on the refractive index of the medium surrounding the fiber. We show experimentally and theoretically that while cladding modes with similar effective indices normally have similar refractometric sensitivities, the addition of a 50 nm thick gold sheath enhances the sensitivity of some EH modes by more than one order of magnitude while nearly completely suppressing the sensitivity of neighbouring HE modes (by three orders of magnitude, down to insignificant levels). A differential sensitivity of ∼1000 nm/(refractive index unit) is experimentally reported between adjacent EH and HE grating resonances.
    Date Created:
    2011-07-25

  • Four-wave mixing in carbon nanotube-coated optical fiber gratings

    Resource Type:
    Article
    Creator:
    Shao, Li-Yang, Simard, Benoit, Albert, Jacques, Sun, Tingting, and Jakubinek, Michael B.
    Abstract:
    The observation of four-wave mixing (FWM) in single-walled carbon nanotubes (SWCNTs) deposited around a tilted fiber Bragg grating (TFBG) has been demonstrated. A thin, floating SWCNT film is manually wrapped around the outer cladding of the fiber and FWM occurs between two core-guided laser signals by TFBG-induced interaction of the core mode and cladding modes. The effective nonlinear coefficient is calculated to be 1.8 10 3W -1Km -1. The wavelength of generated idlers is tunable with a range of 7.8 nm.
    Date Created:
    2012-02-13

  • Bragg gratings fabricated in monomode photosensitive optical fiber by UV exposure through a phase mask

    Resource Type:
    Article
    Creator:
    Albert, Jacques, Bilodeau, F., Malo, B., Hill, K. O., and Johnson, D. C.
    Abstract:
    A photolithographic method is described for fabricating refractive index Bragg gratings in photosensitive optical fiber by using a special phase mask grating made of silica glass. A KrF excimer laser beam (249 nm) at normal incidence is modulated spatially by the phase mask grating. The diffracted light, which forms a periodic, high-contrast intensity pattern with half the phase mask grating pitch, photoimprints a refractive index modulation into the core of photosensitive fiber placed behind, in proximity, and parallel, to the mask; the phase mask grating striations are oriented normal to the fiber axis. This method of fabricating in-fiber Bragg gratings is flexible, simple to use, results in reduced mechanical sensitivity of the grating writing apparatus and is functional even with low spatial and temporal coherence laser sources.
    Date Created:
    1993-12-01

  • Simultaneous corona poling of multiple glass layers for enhanced effective second-order optical nonlinearities

    Resource Type:
    Article
    Creator:
    Blanchetiere, C., Jacob, S., Callender, C. L., Albert, Jacques, Yadav, Ksenia, and Smelser, Christopher W.
    Abstract:
    Silica-based thin-film multilayers are investigated as a means to enhance the effective second-order nonlinearity induced in silica glass structures by corona poling. Structures consisting of phosphorus-doped and undoped silica glass layers exhibit second harmonic generation (SHG) that is higher by an order of magnitude compared to the SHG in bulk silica glass poled under the same conditions. When the poled structure consists of two multilayered stacks separated in space, the stacks exhibit comparable poling-induced nonlinearities. This result suggests that the poling voltage is divided between the two stacks such that simultaneous poling of multiple regions within the sample is realized.
    Date Created:
    2011-07-18

  • Photosensitivity in phosphorus-doped silica glass and optical waveguides

    Resource Type:
    Article
    Creator:
    Hibino, Y., Hattori, K., Johnson, D. C., Hill, K. O., Kitagawa, T., Albert, Jacques, Bilodeau, F., Malo, B., and Gujrathi, S.
    Date Created:
    1994-12-01

  • 1 W tunable dual-wavelength emission from cascaded distributed feedback fiber lasers

    Resource Type:
    Article
    Creator:
    Zhu, X., Peyghambarian, N., Albert, Jacques, Li, L., Moloney, J. V., and Schülzgen, A.
    Date Created:
    2008-02-15

  • Difference in the behavior of oxygen deficient defects in Ge-doped silica optical fiber preforms under ArF and KrF excimer laser irradiation

    Resource Type:
    Article
    Creator:
    Essid, Mourad, Brebner, J.L., Awazu, K., and Albert, Jacques
    Abstract:
    Photobleaching of optical absorption bands in the 5 eV region and the creation of others at higher and lower energy have been examined in the case of ArF (6.4 eV) and KrF (5 eV) excimer laserirradiation of 3GeO2:97SiO2glasses. We report a difference in the transformation process of the neutral oxygen monovacancy and also of the germanium lone pair center (GLPC) into electron trap centers associated with fourfold coordinated Ge ions and Ge-E′ centers when we use one or the other laser. Correlations between absorption bands and electron spin resonance signals were made after different steps of laser irradiation. It was found that the KrF laser generates twice as many Ge-E′ centers as the ArF laser for the same dose of energy delivered. The main reason for this difference is found to be the more efficient bleaching of the GLPC (5.14 eV) by the KrF laser compared to that by the ArF laser.
    Date Created:
    1998-10-15

  • Si ion implantation-induced damage in fused silica probed by variable-energy positrons

    Resource Type:
    Article
    Creator:
    Simpson, P.J., Ilard, L.B., Brebner, J.L., Knights, A.P., and Albert, Jacques
    Abstract:
    Samples of synthetic fused silica have been implanted at room temperature with silicon ions of energy 1.5 MeV. Fluences ranged from 1011 to 1013 cm−2. Samples were probed using variable‐energy positron annihilation spectroscopy. The Doppler‐broadening S parameter corresponding to the implanted region decreased with increasing fluence and saturated at a fluence of 1013 cm−2. It is shown that the decrease in the S parameter is due to the suppression of positronium (Ps) which is formed in the preimplanted material, due to the competing process of implantation‐induced trapping of positrons. In order to satisfactorily model the positron data it was necessary to account for positron trapping due to defects created by both electronic and nuclear stopping of the implanted ions. Annealing of the 1013 cm−2 sample resulted in measurable recovery of the preimplanted S parameter spectrum at 350 °C and complete recovery to the preimplanted condition at 600 °C. Volume compaction was also observed afterimplantation. Upon annealing, the compaction was seen to decrease by 75%.
    Date Created:
    1996-06-16

  • Comparison of one-photon and two-photon effects in the photosensitivity of germanium-doped silica optical fibers exposed to intense ArF excimer laser pulses

    Resource Type:
    Article
    Creator:
    Johnson, D. C., Malo, B., Hill, K. O., Thériault, S., Bilodeau, F., and Albert, Jacques
    Date Created:
    1995-12-01

  • Route discovery with constant memory in oriented planar geometric networks

    Resource Type:
    Article
    Creator:
    Urrutia, J., Opatrny, J., Chávez, E., Dobrev, S., Stacho, L., and Kranakis, Evangelos
    Abstract:
    We address the problem of discovering routes in strongly connected planar geometric networks with directed links. Motivated by the necessity for establishing communication in wireless ad hoc networks in which the only information available to a vertex is its immediate neighborhood, we are considering routing algorithms that use the neighborhood information of a vertex for routing with constant memory only. We solve the problem for three types of directed planar geometric networks: Eulerian (in which every vertex has the same number of incoming and outgoing edges), Outerplanar (in which a single face contains all vertices of the network), and Strongly Face Connected, a new class of geometric networks that we define in the article, consisting of several faces, each face being a strongly connected outerplanar graph.
    Date Created:
    2006-08-01

  • An identification-robust test for time-varying parameters in the dynamics of energy prices

    Resource Type:
    Article
    Creator:
    Khalaf, Lynda A., Kichian, Maral, Bernard, Jean-Thomas, and Dufour, Jean-Marie
    Abstract:
    We test for the presence of time-varying parameters (TVP) in the long-run dynamics of energy prices for oil, natural gas and coal, within a standard class of mean-reverting models. We also propose residual-based diagnostic tests and examine out-of-sample forecasts. In-sample LR tests support the TVP model for coal and gas but not for oil, though companion diagnostics suggest that the model is too restrictive to conclusively fit the data. Out-of-sample analysis suggests a random-walk specification for oil price, and TVP models for both real-time forecasting in the case of gas and long-run forecasting in the case of coal.
    Date Created:
    2012-06-01

  • Age-at-arrival differences in home-ownership attainment among immigrants and their foreign-born offspring in Canada

    Resource Type:
    Article
    Creator:
    Mendez, Pablo
    Abstract:
    This paper asks whether age at arrival matters when it comes to home-ownership attainment among immigrants, paying particular attention to householders' self-identification as a visible minority. Combining methods that were developed separately in the immigrant housing and the immigrant offspring literatures, this study shows the importance of recognising generational groups based on age at arrival, while also accounting for the interacting effects of current age (or birth cohorts) and arrival cohorts. The paper advocates a (quasi-)longitudinal approach to studying home-ownership attainment among immigrants and their foreign-born offspring. Analysis of data from the Canadian Census reveals that foreign-born householders who immigrated as adults in the 1970s and the 1980s are more likely to be home-owners than their counterparts who immigrated at a younger age when they self-identify as South Asian or White, but not always so when they self-identify as Chinese or as ‘other visible minority’. The same bifurcated pattern recurs between householders who immigrated at secondary-school age and those who were younger upon arrival. Age at arrival therefore emerges as a variable of significance to help explain differences in immigrant housing outcomes, and should be taken into account in future studies of immigrant home-ownership attainment. Copyright © 2009 John Wiley & Sons, Ltd.
    Date Created:
    2009-01-01

  • Subterranean Commodification: Informal Housing and the Legalization of Basement Suites in Vancouver from 1928 to 2009

    Resource Type:
    Article
    Creator:
    Quastel, Noah and Mendez, Pablo
    Abstract:
    This article draws on Margaret Radin's theorization of 'contested commodities' to explore the process whereby informal housing becomes formalized while also being shaped by legal regulation. In seeking to move once-informal housing into the domain of official legality, cities can seldom rely on a simple legal framework of private-law principles of property and contract. Instead, they face complex trade-offs between providing basic needs and affordability and meeting public-law norms around living standards, traditional neighbourhood feel and the environment. This article highlights these issues through an examination of the uneven process of legal formalization of basement apartments in Vancouver, Canada. We chose a lengthy period-from 1928 to 2009-to explore how basement apartments became a vital source of housing often at odds with city planning that has long favoured a low-density residential built form. We suggest that Radin's theoretical account makes it possible to link legalization and official market construction with two questions: whether to permit commodification and how to permit commodification. Real-world commodification processes-including legal sanction-reflect hybridization, pragmatic decision making and regulatory compromise. The resolution of questions concerning how to legalize commodification are also intertwined with processes of market expansion.
    Date Created:
    2015-11-01

  • A geography-based critique of new US biofuels regulations

    Resource Type:
    Article
    Creator:
    Fast, Stewart, Saner, Marc, and Brklacich, Michael
    Abstract:
    The new renewable fuels standard (RFS 2) aims to distinguish corn-ethanol that achieves a 20% reduction in greenhouse gas (GHG) emissions compared with gasoline. Field data from Kim et al. (2009) and from our own study suggest that geographic variability in the GHG emissions arising from corn production casts considerable doubt on the approach used in the RFS 2 to measure compliance with the 20% target. If regulators wish to require compliance of fuels with specific GHG emission reduction thresholds, then data from growing biomass should be disaggregated to a level that captures the level of variability in grain corn production and the application of life cycle assessment to biofuels should be modified to capture this variability.
    Date Created:
    2012-05-01

  • Reframing the history of new religious movements

    Resource Type:
    Article
    Creator:
    Driedger, Michael and Wolfart, Johannes
    Abstract:
    In this special issue of Nova Religio four historians of medieval and early modern Christianities offer perspectives on basic conceptual frameworks widely employed in new religions studies, including modernization and secularization, radicalism/violent radicalization, and diversity/diversification. Together with a response essay by J. Gordon Melton, these articles suggest strong possibilities for renewed and ongoing conversation between scholars of "old" and "new" religions. Unlike some early discussions, ours is not aimed simply at questioning the distinction between old and new religions itself. Rather, we think such conversation between scholarly fields holds the prospect of productive scholarly surprise and perspectival shifts, especially via the disciplinary practice of historiographical criticism.
    Date Created:
    2018-05-01

  • Continuity and change in the home literacy environment as predictors of growth in vocabulary and reading

    Resource Type:
    Article
    Creator:
    LeFevre, Jo-Anne and Sénéchal, Monique
    Abstract:
    One hundred and ten English-speaking children schooled in French were followed from kindergarten to Grade 2 (Mage: T1 = 5;6, T2 = 6;4, T3 = 6;11, T4 = 7;11). The findings provided strong support for the Home Literacy Model (Sénéchal & LeFevre, 2002) because in this sample the home language was independent of the language of instruction. The informal literacy environment at home predicted growth in English receptive vocabulary from kindergarten to Grade 1, whereas parent reports of the formal literacy environment in kindergarten predicted growth in children's English early literacy between kindergarten and Grade 1 and growth in English word reading during Grade 1. Furthermore, 76% of parents adjusted their formal literacy practices according to the reading performance of their child, in support of the presence of a responsive home literacy curriculum among middle-class parents.
    Date Created:
    2014-01-01

  • Polarization-selective grating excitation of plasmons in cylindrical optical fibers

    Resource Type:
    Article
    Creator:
    Albert, Jacques, Dakka, Milad A., Shevchenko, Yanina, and Chen, Chengkun
    Abstract:
    We show that the tilted-grating-assisted excitation of surface plasmon polaritons on gold coated single-mode optical fibers depends strongly on the state of polarization of the core-guided light, even in fibers with cylindrical symmetry. Rotating the linear polarization of the guided light by 90° relative to the grating tilt plane is sufficient to turn the plasmon resonances on and off with more than 17 dB of extinction ratio. By monitoring the amplitude changes of selected individual cladding mode resonances we identify what we believe to be a new refractive index measurement method that is shown to be accurate to better than 5 × 10-5.
    Date Created:
    2010-03-01

  • The role of invented spelling on learning to read in low-phoneme awareness kindergartners: A randomized-control-trial study

    Resource Type:
    Article
    Creator:
    Lever, Rosemary, Ouellette, Gene, Pagan, Stephanie, and Sénéchal, Monique
    Abstract:
    The goal of the present intervention research was to test whether guided invented spelling would facilitate entry into reading for at-risk kindergarten children. The 56 participating children had poor phoneme awareness, and as such, were at risk of having difficulty acquiring reading skills. Children were randomly assigned to one of three training conditions: invented spelling, phoneme segmentation, or storybook reading. All children participated in 16 small group sessions over eight weeks. In addition, children in the three training conditions received letter-knowledge training and worked on the same 40 stimulus words that were created from an array of 14 letters. The findings were clear: on pretest, there were no differences between the three conditions on measures of early literacy and vocabulary, but, after training, invented spelling children learned to read more words than did the other children. As expected, the phoneme-segmentation and invented-spelling children were better on phoneme awareness than were the storybook-reading children. Most interesting, however, both the invented spelling and the phoneme-segmentation children performed similarly on phoneme awareness suggesting that the differential effect on learning to read was not due to phoneme awareness per se. As such, the findings support the view that invented spelling is an exploratory process that involves the integration of phoneme and orthographic representations. With guidance and developmentally appropriate feedback, invented spelling provides a milieu for children to explore the relation between oral language and written symbols that can facilitate their entry in reading.
    Date Created:
    2012-04-01

  • Anomalous permittivity and plasmon resonances of copper nanoparticle conformal coatings on optical fibers

    Resource Type:
    Article
    Creator:
    Shao, Li-Yang, Albert, Jacques, Coyle, Jason P., and Barry, Seán T.
    Abstract:
    The conformal coating of a 50 nm-thick layer of copper nanoparticles deposited with pulse chemical vapor deposition of a copper (I) guanidinate precursor on the cladding of a single mode optical fiber was monitored by using a tilted fiber Bragg grating (TFBG) photo-inscribed in the fiber core. The pulse-per-pulse growth of the copper nanoparticles is readily obtained from the position and amplitudes of resonances in the reflection spectrum of the grating. In particular, we confirm that the real part of the effective complex permittivity of the deposited nano-structured copper layer is an order of magnitude larger than that of a bulk copper film at an optical wavelength of 1550 nm. We further observe a transition in the growth behavior from granular to continuous film (as determined from the complex material permittivity) after approximately 20 pulses (corresponding to an effective thickness of 25 nm). Finally, despite the remaining granularity of the film, the final copper-coated optical fiber is shown to support plasmon waves suitable for sensing, even after the growth of a thin oxide layer on the copper surface.
    Date Created:
    2011-06-01

  • Towards a measure of biometric feature information

    Resource Type:
    Article
    Creator:
    Adler, Andy, Loyka, Sergey, and Youmaran, Richard
    Date Created:
    2009-01-01

  • A generalized Winternitz Theorem

    Resource Type:
    Article
    Creator:
    Morin, Pat, Hurtado, Ferran, Bose, Prosenjit, and Carmi, Paz
    Abstract:
    We prove that, for every simple polygon P having k ≥ 1 reflex vertices, there exists a point q ε P such that every half-polygon that contains q contains nearly 1/2(k + 1) times the area of P. We also give a family of examples showing that this result is the best possible.
    Date Created:
    2011-04-01

  • Atlas motion platform generalized kinematic model: Atlas motion platform

    Resource Type:
    Article
    Creator:
    Hayes, M. John, Langlois, Robert, and Weiss, Abraham
    Abstract:
    Conventional training simulators commonly use a hexapod configuration to provide motion cues. While widely used, studies have shown that hexapods are incapable of producing the range of motion required to achieve high fidelity simulation required in many applications. A novel alternative is the Atlas motion platform. This paper presents a new generalized kinematic model of the platform which can be applied to any spherical platform actuated by three omnidirectional wheels. In addition, conditions for slip-free and singularity-free motions are identified. Two illustrative examples are given for different omnidirectional wheel configurations.
    Date Created:
    2011-02-01

  • Parallel collision search with cryptanalytic applications

    Resource Type:
    Article
    Creator:
    Wiener, Michael J. and Van Oorschot, Paul C.
    Abstract:
    A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.
    Date Created:
    1999-01-01

  • Authentication and authenticated key exchanges

    Resource Type:
    Article
    Creator:
    Wiener, Michael J., Van Oorschot, Paul C., and Diffie, Whitfield
    Abstract:
    We discuss two-party mutual authentication protocols providing authenticated key exchange, focusing on those using asymmetric techniques. A simple, efficient protocol referred to as the station-to-station (STS) protocol is introduced, examined in detail, and considered in relation to existing protocols. The definition of a secure protocol is considered, and desirable characteristics of secure protocols are discussed.
    Date Created:
    1992-06-01

  • Near infrared electrochromic variable optical attenuator based on ruthenium complex and polycrystalline tungsten oxide

    Resource Type:
    Article
    Creator:
    Yan, Donghang, Wang, Zhiyuan, Yu, Hongan, Wu, Xianguo, and Zhang, Jidong
    Abstract:
    A near infrared (NIR) electrochromic attenuator based on a dinuclear ruthenium complex and polycrystalline tungsten oxide was fabricated and characterized. The results show that the use of the NIR-absorbing ruthenium complex as a counter electrode material can improve the device performance. By replacing the visible electrochromic ferrocene with the NIR-absorbing ruthenium complex, the optical attenuation at 1550 nm was enhanced from 19.1 to 30.0 dB and color efficiency also increased from 29.2 to 121.2 cm2/C.
    Date Created:
    2005-12-01

  • Feasibility of design in stereolithography

    Resource Type:
    Article
    Creator:
    Bose, Prosenjit, Overmars, M., Wilfong, G., Toussaint, G., Garcia-Lopez, J., Zhu, B., Asberg, B., and Blanco, G.
    Abstract:
    We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid causes the liquid to harden. In order to understand the power as well as the limitations of this manufacturing process better, we define a mathematical model of stereolithography (referred to as vertical stereolithography) and analyze the class of objects that can be constructed under the assumptions of the model. Given an object (modeled as a polygon or a polyhedron), we give algorithms that decide in O(n) time (where n is the number of vertices in the polygon or polyhedron) whether or not the object can be constructed by vertical stereolithography. If the answer is in the affirmative, the algorithm reports a description of all the orientations in which the object can be made. We also show that the objects built with vertical stereolithography are precisely those that can be made with a 3-axis NC machine. We then define a more flexible model that more accurately reflects the actual capabilities of stereolithography (referred to as variable-angle stereolithography) and again study the class of feasible objects for this model. We give an O(n)-time algorithm for polygons and O(n log n)- as well as O(n)-time algorithms for polyhedra. We show that objects formed with variable-angle stereolithography can also be constructed using another manufacturing process known as gravity casting. Furthermore, we show that the polyhedral objects formed by vertical stereolithography are closely related to polyhedral terrains which are important structures in geographic information systems (GIS) and computational geometry. In fact, an object built with variable-angle stereolithography resembles a terrain with overhangs, thus initiating the study of more realistic terrains than the standard ones considered in geographic information systems. Finally, we relate our results to the area of grasping in robotics by showing that the polygonal and polyhedral objects that can be built by vertical stereolithography can be clamped by parallel jaw grippers with any positive-sized gripper.
    Date Created:
    1997-01-01

  • Optimal parallel algorithms for rectilinear link-distance problems

    Resource Type:
    Article
    Creator:
    Sack, Jörg-Rüdiger, Maheshwari, Anil, and Lingas, A.
    Abstract:
    We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P. 2. Minimum rectilinear link paths from any segment inside P to all vertices of P. 3. The rectilinear window (histogram) partition of P. 4. Both covering radii and vertex intervals for any diagonal of P. 5. A data structure to support rectilinear link-distance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which used O(n log n) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
    Date Created:
    1995-09-01

  • Faulty node repair and dynamically spawned black hole search

    Resource Type:
    Conference Proceeding
    Creator:
    Peng, Mengfei, Shi, Wei, Croft, William Lee, and Corriveau, Jean-Pierre
    Abstract:
    New threats to networks are constantly arising. This justifies protecting network assets and mitigating the risk associated with attacks. In a distributed environment, researchers aim, in particular, at eliminating faulty network entities. More specifically, much research has been conducted on locating a single static black hole, which is defined as a network site whose existence is known a priori and that disposes of any incoming data without leaving any trace of this occurrence. However, the prevalence of faulty nodes requires an algorithm able to (a) identify faulty nodes that can be repaired without human intervention and (b) locate black holes, which are taken to be faulty nodes whose repair does require human intervention. In this paper, we consider a specific attack model that involves multiple faulty nodes that can be repaired by mobile software agents, as well as a virus v that can infect a previously repaired faulty node and turn it into a black hole. We refer to the task of repairing multiple faulty nodes and pointing out the location of the black hole as the Faulty Node Repair and Dynamically Spawned Black Hole Search. Wefirst analyze the attack model we put forth. We then explain (a) how to identify whether a node is either (1) a normal node or (2) a repairable faulty node or (3) the black hole that has been infected by virus v during the search/repair process and, (b) how to perform the correct relevant actions. These two steps constitute a complex task, which, we explain, significantly differs from the traditional Black Hole Search. We continue by proposing an algorithm to solve this problem in an asynchronous ring network with only one whiteboard (which resides in a node called the homebase). We prove the correctness of our solution and analyze its complexity by both theoretical analysis and experiment evaluation. We conclude that, using our proposed algorithm, b + 4 agents can repair all faulty nodes and locate the black hole infected by a virus v within finite time. Our algorithm works even when the number of faulty nodes b is unknown a priori.
    Date Created:
    2017-01-01

  • Multi-level adaptive active learning for scene classification

    Resource Type:
    Conference Proceeding
    Creator:
    Guo, Yuhong and Li, Xin
    Abstract:
    Semantic scene classification is a challenging problem in computer vision. In this paper, we present a novel multi-level active learning approach to reduce the human annotation effort for training robust scene classification models. Different from most existing active learning methods that can only query labels for selected instances at the target categorization level, i.e., the scene class level, our approach establishes a semantic framework that predicts scene labels based on a latent object-based semantic representation of images, and is capable to query labels at two different levels, the target scene class level (abstractive high level) and the latent object class level (semantic middle level). Specifically, we develop an adaptive active learning strategy to perform multi-level label query, which maintains the default label query at the target scene class level, but switches to the latent object class level whenever an "unexpected" target class label is returned by the labeler. We conduct experiments on two standard scene classification datasets to investigate the efficacy of the proposed approach. Our empirical results show the proposed adaptive multi-level active learning approach can outperform both baseline active learning methods and a state-of-the-art multi-level active learning method.
    Date Created:
    2014-01-01

  • Challenging established move ordering strategies with adaptive data structures

    Resource Type:
    Conference Proceeding
    Creator:
    Oommen, B. John and Polk, Spencer
    Abstract:
    The field of game playing is a particularly well-studied area within the context of AI, leading to the development of powerful techniques, such as the alpha-beta search, capable of achieving competitive game play against an intelligent opponent. It is well known that tree pruning strategies, such as alpha-beta, benefit strongly from proper move ordering, that is, searching the best element first. Inspired by the formerly unrelated field of Adaptive Data Structures (ADSs), we have previously introduced the History-ADS technique, which employs an adaptive list to achieve effective and dynamic move ordering, in a domain independent fashion, and found that it performs well in a wide range of cases. However, previous work did not compare the performance of the History-ADS heuristic to any established move ordering strategy. In an attempt to address this problem, we present here a comparison to two well-known, acclaimed strategies, which operate on a similar philosophy to the History-ADS, the History Heuristic, and the Killer Moves technique. We find that, in a wide range of two-player and multi-player games, at various points in the game’s progression, the History-ADS performs at least as well as these strategies, and, in fact, outperforms them in the majority of cases.
    Date Created:
    2016-01-01

  • Pattern recognition using the TTOCONROT

    Resource Type:
    Conference Proceeding
    Creator:
    Oommen, B. John and Astudillo, César A.
    Abstract:
    We present a method that employs a tree-based Neural Network (NN) for performing classification. The novel mechanism, apart from incorporating the information provided by unlabeled and labeled instances, re-arranges the nodes of the tree as per the laws of Adaptive Data Structures (ADSs). Particularly, we investigate the Pattern Recognition (PR) capabilities of the Tree-Based Topology-Oriented SOM (TTOSOM) when Conditional Rotations (CONROT) [8] are incorporated into the learning scheme. The learning methodology inherits all the properties of the TTOSOM-based classifier designed in [4]. However, we now augment it with the property that frequently accessed nodes are moved closer to the root of the tree. Our experimental results show that on average, the classification capabilities of our proposed strategy are reasonably comparable to those obtained by some of the state-of-the-art classification schemes that only use labeled instances during the training phase. The experiments also show that improved levels of accuracy can be obtained by imposing trees with a larger number of nodes.
    Date Created:
    2015-01-01

  • A novel clustering algorithm based on a non-parametric “anti-bayesian” paradigm

    Resource Type:
    Conference Proceeding
    Creator:
    Yazidi, Anis, Oommen, B. John, and Hammer, Hugo Lewi
    Abstract:
    The problem of clustering, or unsupervised classification, has been solved by a myriad of techniques, all of which depend, either directly or implicitly, on the Bayesian principle of optimal classification. To be more specific, within a Bayesian paradigm, if one is to compare the testing sample with only a single point in the feature space from each class, the optimal Bayesian strategy would be to achieve this based on the distance from the corresponding means or central points in the respective distributions. When this principle is applied in clustering, one would assign an unassigned sample into the cluster whose mean is the closest, and this can be done in either a bottom-up or a top-down manner. This paper pioneers a clustering achieved in an “Anti-Bayesian” manner, and is based on the breakthrough classification paradigm pioneered by Oommen et al. The latter relies on a radically different approach for classifying data points based on the non-central quantiles of the distributions. Surprisingly and counter-intuitively, this turns out to work equally or close-to-equally well to an optimal supervised Bayesian scheme, which thus begs the natural extension to the unexplored arena of clustering. Our algorithm can be seen as the Anti-Bayesian counter-part of the wellknown k-means algorithm (The fundamental Anti-Bayesian paradigm need not just be used to the k-means principle. Rather, we hypothesize that it can be adapted to any of the scores of techniques that is indirectly based on the Bayesian paradigm.), where we assign points to clusters using quantiles rather than the clusters’ centroids. Extensive experimentation (This paper contains the prima facie results of experiments done on one and two-dimensional data. The extensions to multi-dimensional data are not included in the interest of space, and would use the corresponding multi-dimensional Anti-Na¨ıve-Bayes classification rules given in [1].) demonstrates that our Anti-Bayesian clustering converges fast and with precision results competitive to a k-means clustering.
    Date Created:
    2015-01-01

  • On the online classification of data streams using weak estimators

    Resource Type:
    Conference Proceeding
    Creator:
    Tavasoli, Hanane, Oommen, B. John, and Yazidi, Anis
    Abstract:
    In this paper, we propose a novel online classifier for complex data streams which are generated from non-stationary stochastic properties. Instead of using a single training model and counters to keep important data statistics, the introduced online classifier scheme provides a real-time self-adjusting learning model. The learning model utilizes the multiplication-based update algorithm of the Stochastic Learning Weak Estimator (SLWE) at each time instant as a new labeled instance arrives. In this way, the data statistics are updated every time a new element is inserted, without requiring that we have to rebuild its model when changes occur in the data distributions. Finally, and most importantly, the model operates with the understanding that the correct classes of previously-classified patterns become available at a later juncture subsequent to some time instances, thus requiring us to update the training set and the training model. The results obtained from rigorous empirical analysis on multinomial distributions, is remarkable. Indeed, it demonstrates the applicability of our method on synthetic datasets, and proves the advantages of the introduced scheme.
    Date Created:
    2016-01-01

  • Enhancing history-based move ordering in game playing using adaptive data structures

    Resource Type:
    Conference Proceeding
    Creator:
    Polk, Spencer and Oommen, B. John
    Abstract:
    This paper pioneers the avenue of enhancing a well-known paradigm in game playing, namely the use of History-based heuristics, with a totally-unrelated area of computer science, the field of Adaptive Data Structures (ADSs). It is a well-known fact that highly-regarded game playing strategies, such as alpha-beta search, benefit strongly from proper move ordering, and from this perspective, the History heuristic is, probably, one of the most acclaimed techniques used to achieve AI-based game playing. Recently, the authors of this present paper have shown that techniques derived from the field of ADSs, which are concerned with query optimization in a data structure, can be applied to move ordering in multi-player games. This was accomplished by ranking opponent threat levels. The work presented in this paper seeks to extend the utility of ADS-based techniques to two-player and multi-player games, through the development of a new move ordering strategy that incorporates the historical advantages of the moves. The resultant technique, the History-ADS heuristic, has been found to produce substantial (i.e, even up to 70%) savings in a variety of two-player and multi-player games, at varying ply depths, and at both initial and midgame board states. As far as we know, results of this nature have not been reported in the literature before.
    Date Created:
    2015-01-01

  • Search-Based Software Engineering: 7th International Symposium, SSBSE 2015 Bergamo, Italy, September 5-7, 2015 Proceedings

    Resource Type:
    Conference Proceeding
    Creator:
    Labiche, Yvan and Barros, Márcio
    Date Created:
    2015-01-01

  • On the foundations of multinomial Sequence based estimation

    Resource Type:
    Conference Proceeding
    Creator:
    Oommen, B. John and Kim, Sang-Woon
    Abstract:
    This paper deals with the relatively new field of sequencebased estimation which involves utilizing both the information in the observations and in their sequence of appearance. Our intention is to obtain Maximum Likelihood estimates by “extracting” the information contained in the observations when perceived as a sequence rather than as a set. The results of [15] introduced the concepts of Sequence Based Estimation (SBE) for the Binomial distribution. This current paper generalizes these results for the multinomial “two-at-a-time” scenario. We invoke a novel phenomenon called “Occlusion” that can be described as follows: By “concealing” certain observations, we map the estimation problem onto a lower-dimensional binomial space. Once these occluded SBEs have been computed, we demonstrate how the overall Multinomial SBE (MSBE) can be obtained by mapping several lower-dimensional estimates onto the original higher-dimensional space. We formally prove and experimentally demonstrate the convergence of the corresponding estimates.
    Date Created:
    2016-01-01

  • A facility coloring problem in 1-D

    Resource Type:
    Conference Proceeding
    Creator:
    Maheshwari, Anil, Nandy, Ayan, Smid, Michiel, and Das, Sandip
    Abstract:
    Consider a line segment R consisting of n facilities. Each facility is a point on R and it needs to be assigned exactly one of the colors from a given palette of c colors. At an instant of time only the facilities of one particular color are 'active' and all other facilities are 'dormant'. For the set of facilities of a particular color, we compute the one dimensional Voronoi diagram, and find the cell, i.e, a segment of maximum length. The users are assumed to be uniformly distributed over R and they travel to the nearest among the facilities of that particular color that is active. Our objective is to assign colors to the facilities in such a way that the length of the longest cell is minimized. We solve this optimization problem for various values of n and c. We propose an optimal coloring scheme for the number of facilities n being a multiple of c as well as for the general case where n is not a multiple of c. When n is a multiple of c, we compute an optimal scheme in Θ(n) time. For the general case, we propose a coloring scheme that returns the optimal in O(n2logn) time.
    Date Created:
    2014-01-01

  • Multinomial sequence based estimation using contiguous subsequences of length three

    Resource Type:
    Conference Proceeding
    Creator:
    Kim, Sang-Woon and Oommen, B. John
    Abstract:
    The Maximum Likelihood (ML) and Bayesian estimation paradigms work within the model that the data, from which the parameters are to be estimated, is treated as a set rather than as a sequence. The pioneering paper that dealt with the field of sequence-based estimation [2] involved utilizing both the information in the observations and in their sequence of appearance. The results of [2] introduced the concepts of Sequence Based Estimation (SBE) for the Binomial distribution, where the authors derived the corresponding MLE results when the samples are taken two-at-a-time, and then extended these for the cases when they are processed three-at-a-time, four-at-a-time etc. These results were generalized for the multinomial “two-at-a-time” scenario in [3]. This paper (This paper is dedicated to the memory of Dr. Mohamed Kamel, who was a close friend of the first author.) now further generalizes the results found in [3] for the multinomial case and for subsequences of length 3. The strategy used in [3] (and also here) involves a novel phenomenon called “Occlusion” that has not been reported in the field of estimation. The phenomenon can be described as follows: By occluding (hiding or concealing) certain observations, we map the estimation problem onto a lower-dimensional space, i.e., onto a binomial space. Once these occluded SBEs have been computed, the overall Multinomial SBE (MSBE) can be obtained by combining these lower-dimensional estimates. In each case, we formally prove and experimentally demonstrate the convergence of the corresponding estimates.
    Date Created:
    2016-01-01

  • Characterizing and computing causes for query answers in databases from database repairs and repair programs

    Resource Type:
    Conference Proceeding
    Creator:
    Bertossi, Leopoldo
    Abstract:
    A correspondence between database tuples as causes for query answers in databases and tuple-based repairs of inconsistent databases with respect to denial constraints has already been established. In this work, answer-set programs that specify repairs of databases are used as a basis for solving computational and reasoning problems about causes. Here, causes are also introduced at the attribute level by appealing to a both null-based and attribute-based repair semantics. The corresponding repair programs are presented, and they are used as a basis for computation and reasoning about attribute-level causes.
    Date Created:
    2018-01-01

  • Local routing in spanners based on WSPDs

    Resource Type:
    Conference Proceeding
    Creator:
    Dujmović, Vida, De Carufel, Jean-Lou, Bose, Prosenjit, and Paradis, Frédérik
    Abstract:
    The well-separated pair decomposition (WSPD) of the complete Euclidean graph defined on points in ℝ2 (Callahan and Kosaraju [JACM, 42 (1): 67-90, 1995]) is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPD-spanner) is a 1 + 8/(s − 4)-spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive local-routing strategies exist for various spanners such as Yao-graphs, Θ-graphs, and variants of Delaunay graphs, few local-routing strategies are known for any WSPD-spanner. Our main contribution is a local-routing algorithm with a near-optimal competitive routing ratio of 1 + O(1/s) on a WSPD-spanner. Specifically, we present a 2-local and a 1-local routing algorithm on a WSPD-spanner with competitive routing ratios of 1+6/(s−2)+4/s and 1+6/(s−2)+ 6/s + 4/(s2 − 2s) + 8/s2respectively.
    Date Created:
    2017-01-01

  • Pro-active strategies for the frugal feeding problem in wireless sensor networks

    Resource Type:
    Conference Proceeding
    Creator:
    Lanthier, Mark, Velazquez, Elio, and Santoro, Nicola
    Abstract:
    This paper proposes a pro-active solution to the Frugal Feeding Problem (FFP) in Wireless Sensor Networks. The FFP attempts to find energy-efficient routes for a mobile service entity to rendezvous with each member of a team of mobile robots. Although the complexity of the FFP is similar to the Traveling Salesman Problem (TSP), we propose an efficient solution, completely distributed and localized for the case of a fixed rendezvous location (i.e., service facility with limited number of docking ports) and mobile capable entities (sensors). Our pro-active solution reduces the FFP to finding energy-efficient routes in a dynamic Compass Directed unit Graph (CDG). The proposed CDG incorporates ideas from forward progress routing and the directionality of compass routing in an energy-aware unit sub-graph. Navigating the CDG guarantees that each sensor will reach the rendezvous location in a finite number of steps. The ultimate goal of our solution is to achieve energy equilibrium (i.e., no further sensor losses due to energy starvation) by optimizing the use of the shared resource (recharge station). We also examine the impact of critical parameters such as transmission range, cost of mobility and sensor knowledge in the overall performance.
    Date Created:
    2011-11-14

  • Bi-directional representation learning for multi-label classification

    Resource Type:
    Conference Proceeding
    Creator:
    Guo, Yuhong and Li, Xin
    Abstract:
    Multi-label classification is a central problem in many application domains. In this paper, we present a novel supervised bi-directional model that learns a low-dimensional mid-level representation for multi-label classification. Unlike traditional multi-label learning methods which identify intermediate representations from either the input space or the output space but not both, the mid-level representation in our model has two complementary parts that capture intrinsic information of the input data and the output labels respectively under the autoencoder principle while augmenting each other for the target output label prediction. The resulting optimization problem can be solved efficiently using an iterative procedure with alternating steps, while closed-form solutions exist for one major step. Our experiments conducted on a variety of multi-label data sets demonstrate the efficacy of the proposed bi-directional representation learning model for multi-label classification.
    Date Created:
    2014-01-01

  • The impact of naive agents in heterogeneous trust-aware societies

    Resource Type:
    Conference Proceeding
    Creator:
    White, Anthony and Salehi-Abari, Amirali
    Abstract:
    Autonomous agents require trust and reputation concepts in order to identify communities of agents with which to interact reliably in ways analogous to humans. Agent societies are invariably heterogeneous, with multiple decision making policies and actions governing their behaviour. Through the introduction of naive agents, this paper shows empirically that while learning agents can identify malicious agents through direct interaction, naive agents compromise utility through their inability to discern malicious agents. Moreover, the impact of the proportion of naive agents on the society is analyzed. The paper demonstrates that there is a need for witness interaction trust to detect naive agents in addition to the need for direct interaction trust to detect malicious agents. By proposing a set of policies, the paper demonstrates how learning agents can isolate themselves from naive and malicious agents.
    Date Created:
    2010-07-20

  • Coarse grained parallel algorithms for detecting convex bipartite graphs

    Resource Type:
    Conference Proceeding
    Creator:
    Prencipe, Giuseppe, Cáceres, Edson, Chan, Albert, and Dehne, Frank
    Abstract:
    In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and the bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. Our algorithms require O(log p) and O(log2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N/p local memory per processor, N=|G|. The algorithms assume that N/ p ≥ p€ for some fixed€ > 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log2 p) supersteps, respectively, O(g log(p) N p) communication time, and O(log(p) N p) local computation time. Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutive-ones property for (0, 1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.
    Date Created:
    2000-01-01

  • External memory algorithms for outerplanar graphs

    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

  • Online routing in triangulations?

    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

  • Approximating the unsatisfiability threshold of random formulas: (Extended abstract)

    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

  • An ϵ - Approximation algorithm for weighted shortest paths on polyhedral surfaces

    Resource Type:
    Conference Proceeding
    Creator:
    Maheshwari, Anil, Sack, Jörg-Rüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
    Date Created:
    1998-01-01

  • Station layouts in the presence of location constraints

    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

  • Upper bounds on the spanning ratio of constrained theta-graphs

    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

  • Maximizing a voronoi region: The convex case

    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

  • Mercury: Recovering forgotten passwords using personal devices

    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

  • Two-dimensional range diameter queries

    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

  • Preventing the cluster formation attack against the hierarchical OLSR protocol

    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

  • On minimizing the sum of sensor movements for barrier coverage of a line segment

    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

  • Security threat mitigation trends in low-cost RFID systems

    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

  • Routing on delay tolerant sensor networks

    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

  • I/O and space-efficient path traversal in planar graphs

    Resource Type:
    Conference Proceeding
    Creator:
    He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
    Date Created:
    2009-12-01

  • On minimizing the maximum sensor movement for barrier coverage of a line segment

    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

  • Relative Span weighted localization of uncooperative nodes in wireless networks

    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

  • Succinct and I/O efficient data structures for traversal in trees

    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

  • Integrating performance analysis in the model driven development of software product lines

    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

  • Local construction and coloring of spanners of location aware unit disk graphs

    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

  • Computing the greedy spanner in near-quadratic time

    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

  • Optimal movement of mobile sensors for barrier coverage of a planar region (extended abstract)

    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

  • Geometric spanners with small chromatic number

    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

  • Local PTAS for independent set and vertex cover in location aware unit disk graphs (Extended Abstract)

    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

  • Our place or mine? Exploration into collectivism-focused persuasive technology design

    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

  • On spanners of geometric graphs

    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

  • Abstraction-raising transformation for generating analysis models

    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

  • Induced subgraphs of bounded degree and bounded treewidth

    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

  • Randomized rendez-vous with limited memory

    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

  • Mobile agent rendezvous in a synchronous torus

    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

  • Noisy subsequence recognition using constrained string editing involving substitutions, insertions, deletions and generalized transpositions

    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

  • Data quality is context dependent

    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

  • The weak gap property in metric spaces of bounded doubling dimension

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel
    Date Created:
    2009-10-16

  • Position discovery for a system of bouncing robots

    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

  • Query rewriting using datalog for duplicate resolution

    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

  • The discrete voronoi game in a simple polygon

    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

  • An external memory data structure for shortest path queries

    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

  • 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

  • Suburban ways of living and the geography of income: How homeownership, single-family dwellings and automobile use define the metropolitan social space

    Resource Type:
    Article
    Creator:
    Moos, Markus and Mendez, Pablo
    Abstract:
    Current research depicts suburbs as becoming more heterogeneous in terms of socio-economic status. Providing a novel analysis, this paper engages with that research by operationalising suburban ways of living (homeownership, single-family dwelling occupancy and automobile use) and relating them to the geography of income across 26 Canadian metropolitan areas. We find that suburban ways of living exist in new areas and remain associated with higher incomes even as older suburbs, as places, have become more diverse. In the largest cities the relationship between income and suburban ways of living is weaker due to the growth of condominiums in downtowns that allow higher income earners to live urban lifestyles. Homeownership is overwhelmingly more important than other variables in explaining the geography of income across 26 metropolitan areas.
    Date Created:
    2015-01-01

  • Art as a transformative practice: A participatory action research project with trans* youth

    Resource Type:
    Article
    Creator:
    Tierney, Cara, Lundy, Jess, Asakura, Kenta, and Black, Dillon
    Date Created:
    2019-10-03

  • The relationship between net energy use and the urban density of solar buildings

    Resource Type:
    Article
    Creator:
    Athienitis, Andreas K, Kesik, Ted J, Kennedy, Christopher A, and O'Brien, William
    Abstract:
    There is a paradoxical relationship between the density of solar housing and net household energy use. The amount of solar energy available per person decreases as density increases. At the same time, transportation energy, and to some extent, household operating energy decreases. Thus, an interesting question is posed: how does net energy use vary with housing density? This study attempts to provide insight into this question by examining three housing forms: low-density detached homes, medium-density townhouses, and high-density high-rise apartments in Toronto. The three major quantities of energy that are summed for each are building operational energy use, solar energy availability, and personal transportation energy use. Solar energy availability is determined on the basis of an effective annual collector efficiency. The results show that under the base case in which solar panels are applied to conventional homes, the high-density development uses one-third less energy than the low-density one. Improving the efficiency of the homes results in a similar trend. Only when the personal vehicle fleet or solar collectors are made to be extremely efficient does the trend reverse-the low-density development results in lower net energy.
    Date Created:
    2010-01-01

  • Scholarly and public engagement in Jewish politics: A journey through liminal space in ten short chapters

    Resource Type:
    Article
    Creator:
    Sucharov, Mira
    Abstract:
    This article interrogates the question of what it means to be a scholar-commentator in the digital age. Deploying an autoethnographic style, the essay asks about the role of power and responsibility in teaching, research, and public commentary, particularly in the context of studying and engaging in Jewish politics. The article addresses questions about the proper role of the scholar in the academy and the role of subjectivity and political commitments in structuring scholarship, pedagogy, and public engagement. It also examines how one’s view of the profession can seem to shift through the emergence of new writing outlets and new forums for public engagement. Finally, the author investigates how a scholar’s own political commitments can shift over time, how one seeks to shore up identification on social media while trying to change hearts and minds through the op-ed pages, and how community identification can serve as a buffer and motivator for particular forms of research and political action.
    Date Created:
    2018-12-01

  • Ca-ATPase activity and protein composition of sarcoplasmic reticulum membranes isolated from skeletal muscles of typical hibernator, the ground squirrel Spermophilus undulatus

    Resource Type:
    Article
    Creator:
    Lopina, Olga D., Storey, Kenneth B., Rubstov, Alexander M., and Malysheva, Anna N.
    Abstract:
    Ca-ATPase activity in sarcoplasmic reticulum (SR) membranes isolated from skeletal muscles of the typical hibernator, the ground squirrel Spermophilus undulatus, is about 2-fold lower than that in SR membranes of rats and rabbits and is further decreased 2-fold during hibernation. The use of carbocyanine anionic dye Stains-All has revealed that Ca-binding proteins of SR membranes, histidine-rich Ca-binding protein and sarcalumenin, in ground squirrel, rat, and rabbit SR have different electrophoretic mobility corresponding to apparent molecular masses 165, 155, and 170 kDa and 130, 145, and 160 kDa, respectively; the electrophoretic mobility of calsequestrin (63 kDa) is the same in all preparations. The content of these Ca-binding proteins in SR membranes of the ground squirrels is decreased 3–4 fold and the content of 55, 30, and 22 kDa proteins is significantly increased during hibernation.
    Date Created:
    2001-12-01