Concepedia

Graph Sketches

Graph Sketches is a compact probabilistic data structure that summarizes the topology of a graph in a space-efficient manner, enabling approximate queries about vertex connectivity, neighborhood, and subgraph patterns while minimizing storage and computational overhead.

52

Publications

6.2K

Citations

120

Authors

61

Institutions

Publications per year

2017–2026

10

Parents

Publications

52

An algorithm for drawing general undirected graphs

Tomihisa Kamada, Satoru Kawai · Information Processing Letters · 1989 · 2.8K citations

, , +12

Algorithms for drawing graphs: an annotated bibliography

Giuseppe Di Battista, Peter Eades, Roberto Tamassia et al. · Computational Geometry · 1994 · 860 citations

, , +11

Graph sketches

Kook Jin Ahn, Sudipto Guha, Andrew McGregor · 2012 · 223 citations

, , +16

Analyzing graph structure via linear measurements

Kook Jin Ahn, Sudipto Guha, Andrew McGregor · Scholarly Commons (University of Pennsylvania) · 2012 · 215 citations · Full text

, , +10

Explicit construction of graphs with an arbitrary large girth and of large size

Felix Lazebnik, V. A. Ustimenko · Discrete Applied Mathematics · 1995 · 179 citations

, , +12

1–5 of 52

Authors

120

  1. AM
    Andrew McGregor

    University of Massachusetts Amherst, United States

    5 publications · 634 citations

    5

    h-index

  2. CC
    Charų C. Aggarwal

    IBM (United States), United States

    5 publications · 196 citations

    5

    h-index

  3. SG
    Sudipto Guha

    University of Pennsylvania, United States

    5 publications · 634 citations

    5

    h-index

  4. EC
    Edith Cohen

    AT&T (United States), United States

    3 publications · 131 citations

    3

    h-index

  5. PZ
    Peixiang Zhao

    University of Illinois Urbana-Champaign, United States

    3 publications · 153 citations

    3

    h-index

1–5 of 120

Institutions

61

  1. IBM (United States)

    Armonk, United States

    4 h-index

    4 publications

    178 citations

  2. University of Massachusetts Amherst

    Amherst Center, United States

    4 h-index

    5 publications

    593 citations

  3. University of Pennsylvania

    Philadelphia, United States

    4 h-index

    6 publications

    974 citations

  4. Nanyang Technological University

    Singapore, Singapore

    3 h-index

    3 publications

    53 citations

  5. Microsoft (United States)

    Redmond, United States

    3 h-index

    8 publications

    494 citations

  6. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    3 publications

    188 citations

  7. AT&T (United States)

    Bedminster, United States

    2 h-index

    4 publications

    200 citations

  8. Carnegie Mellon University

    Pittsburgh, United States

    2 h-index

    4 publications

    102 citations

1–8 of 61

Venues

  1. arXiv (Cornell University)

    Repository · 4 publications · 62 citations

    4

    h-index

  2. Proceedings of the VLDB Endowment

    PVLDB · 3 publications · 175 citations

    3

    h-index

  3. IEEE Transactions on Knowledge and Data Engineering

    TKDE · 2 publications · 87 citations

    2

    h-index

  4. Algorithmica

    2 publications · 105 citations

    2

    h-index

  5. Journal of Combinatorial Theory Series B

    1 publications · 25 citations

    1

    h-index

1–5