NDLI: Graph sketches: sparsification, spanners, and subgraphs

Please wait, while we are loading the content...

What next?: a half-dozen data management research goals for big data and the cloud

Graph sketches: sparsification, spanners, and subgraphs

The ACM PODS Alberto O. Mendelzon test-of-time award 2012

Linguistic foundations for bidirectional transformations: invited tutorial

The power of the dinur-nissim algorithm: breaking privacy of statistical and graph databases

Space-efficient range reporting for categorical data

Approximate computation and implicit regularization for very large-scale data analysis

Query-based data pricing

The wavelet trie: maintaining an indexed sequence of strings in compressed space

Classification of annotation semirings over query containment

Space-efficient estimation of statistics over sub-sampled streams

Approximating and testing k-histogram distributions in sub-linear time

Worst-case optimal join algorithms: [extended abstract]

A rigorous and customizable framework for privacy

Dynamic top-k range reporting in external memory

Max-Sum diversification, monotone submodular functions and dynamic updates

Local transformations and conjunctive-query equivalence

On the optimality of clustering properties of space filling curves

Efficient approximations of conjunctive queries

Rectangle-efficient aggregation in spatial data streams

Mergeable summaries

Deterministic regular expressions in linear time

Static analysis and optimization of semantic web queries

Indexability of 2D range search revisited: constant redundancy and weak indivisibility

A dichotomy in the complexity of deletion propagation with functional dependencies

Nearest-neighbor searching under uncertainty

On the complexity of package recommendation problems

Randomized algorithms for tracking distributed count, frequencies, and ranks

The complexity of evaluating path expressions in SPARQL

Continuous distributed counting for non-monotonic streams

Graph sketches: sparsification, spanners, and subgraphs

Content Provider	ACM Digital Library
Author	Ahn, Kook Jin Guha, Sudipto McGregor, Andrew
Abstract	When processing massive data sets, a core task is to construct synopses of the data. To be useful, a synopsis data structure should be easy to construct while also yielding good approximations of the relevant properties of the data set. A particularly useful class of synopses are sketches, i.e., those based on linear projections of the data. These are applicable in many models including various parallel, stream, and compressed sensing settings. A rich body of analytic and empirical work exists for sketching numerical data such as the frequencies of a set of entities. Our work investigates graph sketching where the graphs of interest encode the relationships between these entities. The main challenge is to capture this richer structure and build the necessary synopses with only linear measurements. In this paper we consider properties of graphs including the size of the cuts, the distances between nodes, and the prevalence of dense sub-graphs. Our main result is a sketch-based sparsifier construction: we show that $Õ(nε^{-2})$ random linear projections of a graph on n nodes suffice to (1+ε) approximate all cut values. Similarly, we show that $Õ(ε^{-2})$ linear projections suffice for (additively) approximating the fraction of induced sub-graphs that match a given pattern such as a small clique. Finally, for distance estimation we present sketch-based spanner constructions. In this last result the sketches are adaptive, i.e., the linear projections are performed in a small number of batches where each projection may be chosen dependent on the outcome of earlier sketches. All of the above results immediately give rise to data stream algorithms that also apply to dynamic graph streams where edges are both inserted and deleted. The non-adaptive sketches, such as those for sparsification and subgraphs, give us single-pass algorithms for distributed data streams with insertion and deletions. The adaptive sketches can be used to analyze MapReduce algorithms that use a small number of rounds.
Starting Page	5
Ending Page	14
Page Count	10
File Format	PDF
ISBN	9781450312486
DOI	10.1145/2213556.2213560
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Spanners Subgraphs Data streams Sparsification Graph sketching
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Spanners and sparsifiers in dynamic streams

Graph sketches: sparsification, spanners, and subgraphs (2012)

Vertex and Hyperedge Connectivity in Dynamic Graph Streams

Graph sketches: sparsification, spanners, and subgraphs (2012)

Sketching unaggregated data streams for subpopulation-size queries

Fast Manhattan sketches in data streams

Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams

Sketching asynchronous streams over a sliding window

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

Graph sketches: sparsification, spanners, and subgraphs

Similar Documents

Spanners and sparsifiers in dynamic streams

Graph sketches: sparsification, spanners, and subgraphs (2012)

Vertex and Hyperedge Connectivity in Dynamic Graph Streams

Graph sketches: sparsification, spanners, and subgraphs (2012)

Sketching unaggregated data streams for subpopulation-size queries

Fast Manhattan sketches in data streams

Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams

Sketching asynchronous streams over a sliding window

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

Graph sketches: sparsification, spanners, and subgraphs