Pith. sign in

REVIEW

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1209.5791 v1 pith:3KU24FYU submitted 2012-09-25 cs.DS

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges

Michael J. Bannister , Christopher DuBois , David Eppstein , Padhraic Smyth This is my paper
classification cs.DS
keywords numberdataedgesverticescomponentscontiguousnetworkqueries
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.