394 research outputs found
Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
No full textApproximate nearest neighbor search (ANN) data structures have widespread applications in machine learning, computational biology, and text processing. The goal of ANN is to preprocess a set S so that, given a query q, we can find a point y whose distance from q approximates the smallest distance from q to any point in S. For most distance functions, the best-known ANN bounds for high-dimensional point sets are obtained using techniques based on locality-sensitive hashing (LSH).
Unfortunately, space efficiency is a major challenge for LSH-based data structures. Classic LSH techniques require a very large amount of space, oftentimes polynomial in |S|. A long line of work has developed intricate techniques to reduce this space usage, but these techniques suffer from downsides: they must be hand tailored to each specific LSH, are often complicated, and their space reduction comes at the cost of significantly increased query times.
In this paper we explore a new way to improve the space efficiency of LSH using function inversion techniques, originally developed in (Fiat and Naor 2000).
We begin by describing how function inversion can be used to improve LSH data structures. This gives a fairly simple, black box method to reduce LSH space usage.
Then, we give a data structure that leverages function inversion to improve the query time of the best known near-linear space data structure for approximate nearest neighbor search under Euclidean distance: the ALRW data structure of (Andoni, Laarhoven, Razenshteyn, and Waingarten 2017). ALRW was previously shown to be optimal among "list-of-points" data structures for both Euclidean and Manhattan ANN; thus, in addition to giving improved bounds, our results imply that list-of-points data structures are not optimal for Euclidean or Manhattan ANN
Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
No full textEdit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread database applications. The goal of the problem is to preprocess n strings of length d, to quickly answer queries q of the form: if there is a database string within edit distance r of q, return a database string within edit distance cr of q.
Previous approaches to this problem either rely on very large (superconstant) approximation ratios c, or very small search radii r. Outside of a narrow parameter range, these solutions are not competitive with trivially searching through all n strings.
In this work we give a simple and easy-to-implement hash function that can quickly answer queries for a wide range of parameters. Specifically, our strategy can answer queries in time Õ(d3^rn^{1/c}). The best known practical results require c ≫ r to achieve any correctness guarantee; meanwhile, the best known theoretical results are very involved and difficult to implement, and require query time that can be loosely bounded below by 24^r. Our results significantly broaden the range of parameters for which there exist nontrivial theoretical bounds, while retaining the practicality of a locality-sensitive hash function
Adaptive MapReduce Similarity Joins
No full textSimilarity joins are a fundamental database operation. Given data sets S and R, the goal of a similarity join is to find all points x ∈ S and y ∈ R with distance at most r. Recent research has investigated how locality-sensitive hashing (LSH) can be used for similarity join, and in particular two recent lines of work have made exciting progress on LSH-based join performance. Hu, Tao, and Yi (PODS 17) investigated joins in a massively parallel setting, showing strong results that adapt to the size of the output. Meanwhile, Ahle, Aumüller, and Pagh (SODA 17) showed a sequential algorithm that adapts to the structure of the data, matching classic bounds in the worst case but improving them significantly on more structured data.We show that this adaptive strategy can be adapted to the parallel setting, combining the advantages of these approaches. In particular, we show that a simple modification to Hu et al.'s algorithm achieves bounds that depend on the density of points in the dataset as well as the total outsize of the output. Our algorithm uses no extra parameters over other LSH approaches (in particular, its execution does not depend on the structure of the dataset), and is likely to be efficient in practice
Recall this Book 25: A Conversation with Stephen McCauley
No full textOn March 20th, John talked to Stephen McCauley, author of such brilliant comic novels as Object of My Affection (also a Jennifer Aniston movie) and most recently My Ex-Life. Steve brings light to dark corners in this the second installment of Books in Dark Times. He sings the praises of Charles Dickens, of Anthony Trollope (Elizabeth, offstage, chuckles delightedly) and the world-escaping delights of both Waugh's Brideshead Revisited and the Mapp and Lucia novels of E. F. Benson. He concludes with sweet words for the sour genius of a trio of late 20th century American pessimists: Joan Didion, Dorothy Baker and Iris Owens
Non-Cooperative Rational Interactive Proofs
No full textInteractive-proof games model the scenario where an honest party interacts with powerful but strategic provers, to elicit from them the correct answer to a computational question. Interactive proofs are increasingly used as a framework to design protocols for computation outsourcing.
Existing interactive-proof games largely fall into two categories: either as games of cooperation such as multi-prover interactive proofs and cooperative rational proofs, where the provers work together as a team; or as games of conflict such as refereed games, where the provers directly compete with each other in a zero-sum game. Neither of these extremes truly capture the strategic nature of service providers in outsourcing applications. How to design and analyze non-cooperative interactive proofs is an important open problem.
In this paper, we introduce a mechanism-design approach to define a multi-prover interactive-proof model in which the provers are rational and non-cooperative - they act to maximize their expected utility given others' strategies. We define a strong notion of backwards induction as our solution concept to analyze the resulting extensive-form game with imperfect information.
We fully characterize the complexity of our proof system under different utility gap guarantees. (At a high level, a utility gap of u means that the protocol is robust against provers that may not care about a utility loss of 1/u.) We show, for example, that the power of non-cooperative rational interactive proofs with a polynomial utility gap is exactly equal to the complexity class P^{NEXP}
McCauley, Samuel A., 1837- : Confederate Service Record, 1907.
No full textThis service record is an account of military actions during the American Civil War by veteran Samuel A. McCaulay (1837- ), dated from 1907.1 leaf ; 2 pdf pages.All descriptive lists and service records in this United Confederate (Civil War) Veterans manuscript collection believed to be based out of Robert E. Lee Camp #158 of the United Confederate Veterans (Fort Worth, Tex.).
United Confederate Veterans. R.E. Lee Camp No. 158 (Fort Worth, Tex.)The Southwest Collection Manuscript Record can be accessed at the following URL: http://www.lib.utexas.edu/taro/ttusw/00119/tsw-00119.htm
Gill, Stalinism; Mccauley, Gorbachev
No full textThese two books examine the history of the Soviet Union/Russia over the last half-century. Their approach is quite different, however. While Graeme Gill in Stalinism attempts to study a phenomenon, Martin McCauley focuses his attention on a personality. Thus, it is difficult to assess the books in a comparative manner.
Stalinism appears here in its second edition. The author indicates that he has not changed the arguments that were presented in the earlier volume. In fact, new archival information has been provided to support those arguments. He has added a chapter, however, and updated the bibliography to include material that was not available at the time of the first edition
A hiker's guide to the Oregon Coast Trail: [Columbia River to Tillamook Bay]
No full textby David E.M. Bucy and Mary C. McCauley ; ill. and photos. by Mary McCauley and David Bucy unless otherwise noted.This archived document is maintained by the State Library of Oregon as part of the Oregon Documents Depository Program. It is for informational purposes and may not be suitable for legal purposes.Includes bibliographical references (pages 148-150).Electronic reproduction. Salem, Or. : State Library of Oregon, 2022 Electronic reproduction from print version OrMode of access: Internet from the Oregon Government Publications Collection.Text in English
Radical attitudes and jihad: a commentary on the article by Clark McCauley (2012) Testing theories of radicalization in polls of U.S. Muslims
No full textMcCauley\u27s research adds to what we know about sympathy for elements of the “global jihad frame” among the wider U.S. Muslim population and establishes the need for a targeted and differentiated approach to persuasive communication aimed at undermining sympathy for terrorism. This commentary aims to supplement McCauley\u27s paper with a brief discussion of the distinction between radical thought and action, and what this means for the “war on ideas.
The Art Historian as Ethnographer: Ananda Coomaraswamy's Photographic Archives
No full textConference paper presented March 25-26, 2011.The difficulty of reading the extant photographic archive of any
individual or institution as an intentional and consistent creation is
readily apparent in the case of Ananda Coomaraswamy. A self-taught art
historian with a Ph.D. in geology, Coomaraswamy has been celebrated for
his contributions to the study of Indian art and civilization in the
United States and his career as the first curator (and source) of the
collection in the Boston Museum of Fine Arts. His use of photography
originated with the remarkable photographs taken by his wife, Ethel,
between 1903-06 that were used to illustrate his first book, 'Medieval
Sinhalese Art' (1908), which undoubtedly sensitized him to the demands
of printing, cropping, and masking. Like most art historians, he
continued to amass commercial photographs of Indian sculpture, wall
painting, and architecture, but also took up the medium himself after
his divorce from Ethel in 1910, which allowed him to make copies of the
prints he purchased as well as shoot his own images during subsequent
travels to Asia. After characterizing the ways that Coomaraswamy's
publications were indebted to his photographic archive, this talk will
focus more specifically on the presence of ethnographic photographs of
Indian craftsmen (taken by Ethel) and the large number of images of
dancers, musicians and entertainers that distinguish the archive from
those of other art historians in the early twentieth century.
Coomaraswamy's belief in the racial continuities between contemporary
folk practices and traditional Indian sculpture and his ideas about the
sources of sculptural poses in dance informed his collection as well as
his field research. Parallel to but quite different from Aby Warburg's
'Bilderatlas' and concept of 'Pathosformel', Coomaraswamy's use of
popular photographs ranging from tourist postcards to dance programs
become the visible equivalents of his early political support for Indian
nationalism and Guild Socialism.Conference supported by the Samuel H. Kress Foundation, the NYU
Humanities Initiative, the IFA Visual Resources Collections, and
Princeton University, Department of Art and Archaeology, Visual
Resources Collection
- …
