A Geometric Data Structure from Neuroscience (Invited Talk)

Author Sanjoy Dasgupta



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.1.pdf
  • Filesize: 178 kB
  • 1 pages

Document Identifiers

Author Details

Sanjoy Dasgupta
  • Department of Computer Science and Engineering, University of California San Diego, CA, USA

Cite AsGet BibTex

Sanjoy Dasgupta. A Geometric Data Structure from Neuroscience (Invited Talk). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.1

Abstract

An intriguing geometric primitive, "expand-and-sparsify", has been found in the olfactory system of the fly and several other organisms. It maps an input vector to a much higher-dimensional sparse representation, using a random linear transformation followed by winner-take-all thresholding. I will show that this representation has a variety of formal properties, such as locality preservation, that make it an attractive data structure for algorithms and machine learning. In particular, mimicking the fly’s circuitry yields algorithms for similarity search and for novelty detection that have provable guarantees as well as having practical performance that is competitive with state-of-the-art methods. This talk is based on work with Saket Navlakha (Salk Institute), Chuck Stevens (Salk Institute), and Chris Tosh (Columbia).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • Geometric data structure
  • algorithm design
  • neuroscience

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail