170,316 research outputs found
Fair Coresets and Streaming Algorithms for Fair k-means
No full textWe study fair clustering problems as proposed by Chierichetti et al. [CKLV17]. Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable [IMMM14] and show how to compute them in a streaming setting. This yields a streaming PTAS for fair k-means in the case of two colors (and exact balances). Furthermore, we extend techniques due to Chierichetti et al. [CKLV17] to obtain an approximation algorithm for k-means, which leads to a constant factor algorithm in the streaming model when combined with the coreset
Estimating the weight of metric minimum spanning trees in sublinear time
No full textIn this paper we present a sublinear-time -approximation randomized algorithm to estimate the weight of the minimum spanning tree of an -point metric space. The running time of the algorithm is . Since the full description of an -point metric space is of size , the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in time the weight of the minimum spanning tree to within any factor. We also show that no deterministic algorithm can achieve a -approximation in time. Furthermore, it has been previously shown that no algorithm exists that returns a spanning tree whose weight is within a constant times the optimum
Harmonically mode-locked Ti:Er:LiNbO3 waveguide laser
No full textActive mode locking of an Er-diffusion-doped Ti:LiNbO3 waveguide laser by intracavity phase modulation to as
high as the fourth harmonic (5.12 GHz) of the axial-mode frequency spacing is reported. The diode-pumped,
pigtailed, and fully packaged laser with a monolithically integrated intracavity phase modulator has a threshold
of 9 mW (incident pump power Ep jj c) and emits transform-limited pulses of >3.8-ps width and <5.6-pJ pulse
energy (gain-switched mode locking) at 1602-nm wavelength (Es jj c). The relative change of the mode-locking
frequency with the temperature is 3.65 3 1025y±C. The mode-locking acceptance bandwidth is 675 kHz near the
axial-mode frequency spacing at approximately five times the threshold pump power
Testing hereditary properties of nonexpanding bounded-degree graphs
No full textWe study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered "far" if they differ in epsilon n edges for a positive constant epsilon), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
BICO: BIRCH meets coresets for k-means clustering
No full textWe design a data stream algorithm for the k-means problem, called BICO, that combines the data structure of the SIGMOD Test of Time award winning algorithm BIRCH with the theoretical concept of coresets for clustering problems. The k-means problem asks for a set C of k centers minimizing the sum of the squared distances from every point in a set P to its nearest center in C. In a data stream, the points arrive one by one in arbitrary order and there is limited storage space.
BICO computes high quality solutions in a time short in practice. First, BICO computes a summary S of the data with a provable quality guarantee: For every center set C, S has the same cost as P up to a (1 + ε)-factor, i. e., S is a coreset. Then, it runs k-means++ on S.
We compare BICO experimentally with popular and very fast heuristics (BIRCH, MacQueen) and with approximation algorithms (Stream-KM++, StreamLS) with the best known quality guarantees. We achieve the same quality as the approximation algorithms mentioned with a much shorter running time, and we get much better solutions than the heuristics at the cost of only a moderate increase in running time
Mitomycin C in highly myopic eyes - Author reply
No full textOphthalmology. 2005 Feb;112(2):208-18; discussion 219.
Mitomycin C modulation of corneal wound healing after photorefractive keratectomy in highly myopic eyes.
Gambato C, Ghirlando A, Moretto E, Busato F, Midena E.
SourceRefractive Surgery Service and Antimetabolite Therapy Research Unit, Department of Ophthalmology, University of Padova, Padova, Italy.
Abstract
PURPOSE: To evaluate the role of topical mitomycin C in corneal wound healing (CWH) after photorefractive keratectomy (PRK) in highly myopic eyes.
DESIGN: Prospective, double-masked, randomized clinical trial.
PARTICIPANTS: Seventy-two eyes of 36 patients affected by high (>7 diopters) myopia.
METHODS: In each patient, one eye was randomly assigned to PRK with intraoperative topical 0.02% mitomycin C application, and the fellow eye was treated with a placebo. Postoperatively, mitomycin C-treated eyes received artificial tears (3 times daily, tapered in 3 months), whereas the fellow eye was treated with fluorometholone sodium 2% and artificial tears (3 times daily, tapered in 3 months).
MAIN OUTCOME MEASURES: Uncorrected visual acuity (UCVA) and best-corrected visual acuity (BCVA), contrast sensitivity, manifest refraction, and biomicroscopy. Contrast sensitivity was determined using the Pelli-Robson chart. Corneal confocal microscopy documented CWH.
RESULTS: Mean follow-up was 18 months (range, 12-36). No side effects or toxic effects were documented. At 12-month follow-up examination, UCVAs (logarithm of the minimum angle of resolution) were 0.4+/-0.48 and 0.5+/-0.53 (P = .03) in mitomycin C-treated eyes and corticosteroid-treated eyes, respectively. At 1 year, corneal haze developed in 20% of corticosteroid-treated eyes, versus 0% of mitomycin C-treated eyes. At 12, 24, and 36 months, corneal confocal microscopy showed activated keratocytes and extracellular matrix significantly more evident in untreated eyes (Ps = 0.004, 0.024, and 0.046, respectively).
CONCLUSION: Topical intraoperative application of 0.02% mitomycin C can reduce haze formation in highly myopic eyes undergoing PRK.
Comment in
Ophthalmology. 2006 Feb;113(2):357; author reply 357-8
Dispelling the Myths Behind First-author Citation Counts
No full textWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Legacy StreamKM++ supplemental materials
No full textThis entry contains legacy code that was used to perform the experiments for the paper
Ackermann M.R., Märtens M., Raupach C., Swierkot K., Lammersen C., Sohler C., StreamKM++: A Clustering Algorithm for Data Streams, Journal of Experimental Algorithmics (JEA 2012) 17.1: 2-4.
This work has become popular, but the code that it refers to has been unavailable. I decided to archive the version that I still have, but I can give no warranty at all and there might be all sorts of issues. If you are just interested to run StreamKM++: the algorithm has been ported to several professional frameworks by now, for example MOA:
https://github.com/waikato/mo
- …
