Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Stream Function01:20

Stream Function

2.1K
In two-dimensional incompressible fluid flow, the continuity equation is essential for ensuring mass conservation, meaning that any change in fluid entering or exiting a region is balanced by a corresponding change elsewhere. For incompressible flow, where density remains constant, this requirement simplifies to the condition that the divergence of the velocity field must be zero. Mathematically, this is expressed as,
2.1K
Ogive Graph01:07

Ogive Graph

6.7K
An ogive graph is sometimes called a cumulative frequency polygon. It is one type of frequency polygon that shows cumulative frequency. In other words, the cumulative percentages are added to the graph from left to right. An ogive graph plots cumulative frequency on the vertical y-axis and class boundaries along the horizontal x-axis. It’s very similar to a histogram; only instead of rectangles, an ogive displays a single point where the top right of the rectangle would be. Creating this...
6.7K
Graphing Antiderivatives01:30

Graphing Antiderivatives

52
The concept of an antiderivative is fundamental in calculus, describing how a function's values accumulate over time. This process is closely related to physical motion, such as the movement of a rolling ball. As the ball progresses, its position changes in response to variations in velocity, just as an antiderivative graph reflects the cumulative effect of the original function's values.Graphing an antiderivative requires interpreting how a function's values influence the shape of its...
52
Bar Graph01:07

Bar Graph

21.5K
A bar graph is also called a bar chart and consists of bars that are separated from each other. It either uses horizontal or vertical bars to show comparisons among categories. The bars can be rectangles, or they can be rectangular boxes (used in three-dimensional plots). One axis of the graph represents the specific categories being compared, and the other axis shows a discrete value. In this graph, the length of the bar for each category is proportional to the number or percent of individuals...
21.5K
Time-Series Graph00:54

Time-Series Graph

5.0K
A time-series graph is a line graph with repeated measurements taken at successive intervals of time. It is also called a time series chart. To construct a time-series graph, one must look at both pieces of a paired data set. The horizontal axis is used to plot the time increments, and the vertical axis is used to plot the values of the variable that one is measuring. By using the axes in this way, each point on the graph will correspond to time and a measured quantity. The points on the graph...
5.0K
Multiple Bar Graph01:07

Multiple Bar Graph

9.0K
As the name suggests, a multiple bar graph is the same as a bar graph but has multiple bars to depict relationships between different data values. One can include as many parameters as possible. However, each parameter must have the same unit of measurement.
Each bar or column in the multiple bar graph represents a data value. These graphs are used primarily in interrelating two or more sets of data. The categories of different kinds of data are listed along the horizontal or x-axis, whereas...
9.0K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Cross-level graph contrastive learning for community value prediction.

Neural networks : the official journal of the International Neural Network Society·2025
Same author

GNNFairViz: Visual Analysis for Graph Neural Network Fairness.

IEEE transactions on visualization and computer graphics·2025
Same author

I<sup>2</sup>HGNN: Iterative Interpretable HyperGraph Neural Network for semi-supervised classification.

Neural networks : the official journal of the International Neural Network Society·2024
Same author

Graph Batch Coarsening framework for scalable graph neural networks.

Neural networks : the official journal of the International Neural Network Society·2024
Same author

Exploiting Neighbor Effect: Conv-Agnostic GNN Framework for Graphs With Heterophily.

IEEE transactions on neural networks and learning systems·2023
Same author

Ghost imaging based on Y-net: a dynamic coding and decoding approach.

Optics express·2020
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Jan 25, 2026

In vitro Synthesis of Native, Fibrous Long Spacing and Segmental Long Spacing Collagen
07:54

In vitro Synthesis of Native, Fibrous Long Spacing and Segmental Long Spacing Collagen

Published on: September 20, 2012

14.2K

Dynamic Graph Stream Algorithms in o(n) Space.

Zengfeng Huang1, Pan Peng2

  • 11School of Data Science, Fudan University, Shanghai, China.

Algorithmica
|May 7, 2019
PubMed
Summary
This summary is machine-generated.

This study introduces novel single-pass algorithms for dynamic graph problems, significantly reducing space complexity below the typical O(n) bound for connected components and minimum spanning tree estimation. It also pioneers approximate graph property testing in dynamic streams using sublinear space.

Keywords:
Dynamic graph streamsGraph sketchingMinimum spanning treeProperty testing

More Related Videos

Multi-Stream Perfusion Bioreactor Integrated with Outlet Fractionation for Dynamic Cell Culture
10:00

Multi-Stream Perfusion Bioreactor Integrated with Outlet Fractionation for Dynamic Cell Culture

Published on: July 20, 2022

2.8K
Evaluating the Impact of Hydraulic Fracturing on Streams using Microbial Molecular Signatures
09:11

Evaluating the Impact of Hydraulic Fracturing on Streams using Microbial Molecular Signatures

Published on: April 4, 2021

3.5K

Related Experiment Videos

Last Updated: Jan 25, 2026

In vitro Synthesis of Native, Fibrous Long Spacing and Segmental Long Spacing Collagen
07:54

In vitro Synthesis of Native, Fibrous Long Spacing and Segmental Long Spacing Collagen

Published on: September 20, 2012

14.2K
Multi-Stream Perfusion Bioreactor Integrated with Outlet Fractionation for Dynamic Cell Culture
10:00

Multi-Stream Perfusion Bioreactor Integrated with Outlet Fractionation for Dynamic Cell Culture

Published on: July 20, 2022

2.8K
Evaluating the Impact of Hydraulic Fracturing on Streams using Microbial Molecular Signatures
09:11

Evaluating the Impact of Hydraulic Fracturing on Streams using Microbial Molecular Signatures

Published on: April 4, 2021

3.5K

Area of Science:

  • Computer Science
  • Graph Theory
  • Algorithms

Background:

  • Dynamic streaming model involves processing graph data with edge insertions/deletions.
  • Traditional algorithms often require O(n) space, which is prohibitive for large or sparse graphs.
  • Existing research focused on sublinear space algorithms, but a significant space barrier remained.

Purpose of the Study:

  • To develop single-pass algorithms that overcome the O(n) space barrier in the dynamic streaming model.
  • To enable efficient estimation of graph properties like connected components and minimum spanning tree weight.
  • To initiate the study of approximate graph property testing within the dynamic streaming paradigm.

Main Methods:

  • Designed o(n) space algorithms for estimating the number of connected components with additive error.
  • Developed o(n) space algorithms for approximating the minimum spanning tree weight in connected graphs.
  • Introduced algorithms for approximate graph property testing (k-edge connectivity, k-vertex connectivity, cycle-freeness, bipartiteness) using roughly o(n) space.

Main Results:

  • Achieved o(n) space complexity for estimating connected components and minimum spanning tree weight, improving upon prior work.
  • Demonstrated o(n) space algorithms for testing graph properties like connectivity and bipartiteness in the dynamic streaming model.
  • Established o(n) space lower bounds for these property testing problems, proving the necessity of the derived space complexity.

Conclusions:

  • The study successfully breaks the O(n) space barrier for fundamental dynamic graph problems.
  • New algorithms offer significant space savings for graph analysis in dynamic streaming settings.
  • The work establishes a foundation for approximate graph property testing in dynamic streams.