Lawrence Cayton

Research Scientist

Alumni

Empirical Inference

Overview
Publications

Please visit my homepage at http://people.kyb.tuebingen.mpg.de/lcayton

4 results (View BibTeX file of all listed publications)

2012

GLIDE: GPU-Based Linear Regression for Detection of Epistasis

Kam-Thong, T., Azencott, C., Cayton, L., Pütz, B., Altmann, A., Karbalai, N., Sämann, P., Schölkopf, B., Müller-Myhsok, B., Borgwardt, K.

Human Heredity, 73(4):220-236, September 2012 (article)

Abstract

Due to recent advances in genotyping technologies, mapping phenotypes to single loci in the genome has become a standard technique in statistical genetics. However, one-locus mapping fails to explain much of the phenotypic variance in complex traits. Here, we present GLIDE, which maps phenotypes to pairs of genetic loci and systematically searches for the epistatic interactions expected to reveal part of this missing heritability. GLIDE makes use of the computational power of consumer-grade graphics cards to detect such interactions via linear regression. This enabled us to conduct a systematic two-locus mapping study on seven disease data sets from the Wellcome Trust Case Control Consortium and on in-house hippocampal volume data in 6 h per data set, while current single CPU-based approaches require more than a year’s time to complete the same task.

Web [BibTex]

2012

Kam-Thong, T., Azencott, C., Cayton, L., Pütz, B., Altmann, A., Karbalai, N., Sämann, P., Schölkopf, B., Müller-Myhsok, B., Borgwardt, K. GLIDE: GPU-Based Linear Regression for Detection of Epistasis Human Heredity, 73(4):220-236, September 2012 (article)

Web [BibTex]

Accelerating Nearest Neighbor Search on Manycore Systems

Cayton, L.

In Parallel Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International, pages: 402-413, IPDPS, May 2012 (inproceedings)

Abstract

We develop methods for accelerating metric similarity search that are effective on modern hardware. Our algorithms factor into easily parallelizable components, making them simple to deploy and efficient on multicore CPUs and GPUs. Despite the simple structure of our algorithms, their search performance is provably sublinear in the size of the database, with a factor dependent only on its intrinsic dimensionality. We demonstrate that our methods provide substantial speedups on a range of datasets and hardware platforms. In particular, we present results on a 48-core server machine, on graphics hardware, and on a multicore desktop.

Web DOI Project Page [BibTex]

Cayton, L. Accelerating Nearest Neighbor Search on Manycore Systems In Parallel Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International, pages: 402-413, IPDPS, May 2012 (inproceedings)

Web DOI Project Page [BibTex]

2010

A Nearest Neighbor Data Structure for Graphics Hardware

Cayton, L.

In Proceedings of the First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2010), pages: 1-6, First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS), September 2010 (inproceedings)

Abstract

Nearest neighbor search is a core computational task in database systems and throughout data analysis. It is also a major computational bottleneck, and hence an enormous body of research has been devoted to data structures and algorithms for accelerating the task. Recent advances in graphics hardware provide tantalizing speedups on a variety of tasks and suggest an alternate approach to the problem: simply run brute force search on a massively parallel sys- tem. In this paper we marry the approaches with a novel data structure that can effectively make use of parallel systems such as graphics cards. The architectural complexities of graphics hardware - the high degree of parallelism, the small amount of memory relative to instruction throughput, and the single instruction, multiple data design- present significant challenges for data structure design. Furthermore, the brute force approach applies perfectly to graphics hardware, leading one to question whether an intelligent algorithm or data structure can even hope to outperform this basic approach. Despite these challenges and misgivings, we demonstrate that our data structure - termed a Random Ball Cover - provides significant speedups over the GPU- based brute force approach.

PDF Web [BibTex]

2010

Cayton, L. A Nearest Neighbor Data Structure for Graphics Hardware In Proceedings of the First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2010), pages: 1-6, First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS), September 2010 (inproceedings)

PDF Web [BibTex]

2009

Efficient Bregman Range Search

Cayton, L.

In Advances in Neural Information Processing Systems 22, pages: 243-251, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

Abstract

We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence. The range search task is to return all points in a potentially large database that are within some specified distance of a query. It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval. In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks. Here we describe an algorithm for range search for an arbitrary Bregman divergence. This broad class of dissimilarity measures includes the relative entropy, Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences. Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality. We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences.

PDF Web Project Page [BibTex]

2009

Cayton, L. Efficient Bregman Range Search In Advances in Neural Information Processing Systems 22, pages: 243-251, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

PDF Web Project Page [BibTex]

Lawrence Cayton

2012

GLIDE: GPU-Based Linear Regression for Detection of Epistasis

2012

Accelerating Nearest Neighbor Search on Manycore Systems

2010

A Nearest Neighbor Data Structure for Graphics Hardware

2010

2009

Efficient Bregman Range Search

2009

Latest News

Links

Contact Us