Concepedia

Randomized Sketching

Randomized Sketching is a probabilistic dimensionality reduction technique in streaming algorithms that compactly summarizes high-dimensional data streams into a low-dimensional randomized sketch, preserving key structural properties with high probability while using limited memory and computational resources.

37

Publications

2.4K

Citations

93

Authors

49

Institutions

Publications per year

2017–2026

10

Parents

Publications

37

Stable distributions, pseudorandom generators, embeddings, and data stream computation

Piotr Indyk · Journal of the ACM · 2006 · 428 citations

, , +13

Fast and scalable polynomial kernels via explicit feature maps

Ninh Pham, Rasmus Pagh · 2013 · 326 citations

, , +15

Stable distributions, pseudorandom generators, embeddings and data stream computation

Piotr Indyk · 2002 · 244 citations

, , +11

Iterative hessian sketch: fast and accurate solution approximation for constrained least-squares

Mert Pilancı, Martin J. Wainwright · 2016 · 135 citations

, , +16

On the Exact Space Complexity of Sketching and Streaming Small Norms

Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 2010 · 126 citations · Full text

, , +17

1–5 of 37

Authors

93

  1. DP
    David P. Woodruff

    IBM Research - Almaden, United States

    5 publications · 254 citations

    5

    h-index

  2. RK
    Robert Krauthgamer

    Weizmann Institute of Science, Israel

    3 publications · 167 citations

    3

    h-index

  3. AA
    Alexandr Andoni

    Microsoft (United States), United States

    3 publications · 167 citations

    3

    h-index

  4. MK
    Michael Kapralov

    Stanford University, United States

    3 publications · 168 citations

    3

    h-index

  5. SP
    Shiva Prasad Kasiviswanathan

    Samsung (United States), United States

    2 publications · 61 citations

    2

    h-index

1–5 of 93

Institutions

49

  1. University of California, Berkeley

    Berkeley, United States

    4 h-index

    6 publications

    362 citations

  2. IBM Research - Almaden

    San Jose, United States

    4 h-index

    4 publications

    237 citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    7 publications

    265 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    8 publications

    461 citations

  5. Indian Institute of Technology Kanpur

    Kanpur, India

    2 h-index

    2 publications

    27 citations

  6. IIT@MIT

    Cambridge, United States

    2 h-index

    2 publications

    486 citations

  7. Princeton University

    Princeton, United States

    2 h-index

    2 publications

    176 citations

  8. IBM (United States)

    Armonk, United States

    2 h-index

    3 publications

    94 citations

1–8 of 49

Venues

  1. arXiv (Cornell University)

    Repository · 8 publications · 238 citations

    8

    h-index

  2. International Conference on Machine Learning

    Conference · 2 publications · 24 citations

    2

    h-index

  3. HAL (Le Centre pour la Communication Scientifique Directe)

    Repository · 1 publications · 16 citations

    1

    h-index

  4. Nature Computational Science

    1 publications · 43 citations

    1

    h-index

  5. Journal of Machine Learning Research

    JMLR · 1 publications · 30 citations

    1

    h-index

1–5