## Abstract

The method of stable random projections is useful for efficiently approximating the ℓ_{α} distance (0 < α ≤2) in high dimension and it is naturally suitable for data streams. In this paper, we propose to use only the signs of the projected data and we analyze the probability of collision (i.e., when the two signs differ). Interestingly, when α = 1 (i.e., Cauchy random projections), we show that the probability of collision can be accurately approximated as functions of the chi-square (χ^{2}) similarity. In text and vision applications, the χ^{2} similarity is a popular measure when the features are generated from histograms (which are a typical example of data streams). Experiments confirm that the proposed method is promising for large-scale learning applications. The full paper is available at arXiv:1308.1009. There are many future research problems. For example, when α → 0, the collision probability is a function of the resemblance (of the binary-quantized data). This provides an effective mechanism for resemblance estimation in data streams.

Original language | English (US) |
---|---|

Journal | Advances in Neural Information Processing Systems |

State | Published - 2013 |

Event | 27th Annual Conference on Neural Information Processing Systems, NIPS 2013 - Lake Tahoe, NV, United States Duration: Dec 5 2013 → Dec 10 2013 |

## All Science Journal Classification (ASJC) codes

- Computer Networks and Communications
- Information Systems
- Signal Processing