Improved triangle counting in graph streams: Neighborhood multi-sampling
dc.contributor.advisor | Pavankumar Aduri | |
dc.contributor.author | Mousavi Hanjani, Kiana | |
dc.contributor.department | Computer Science | |
dc.date | 2018-09-13T06:22:55.000 | |
dc.date.accessioned | 2020-06-30T03:12:34Z | |
dc.date.available | 2020-06-30T03:12:34Z | |
dc.date.copyright | Wed Aug 01 00:00:00 UTC 2018 | |
dc.date.embargo | 2001-01-01 | |
dc.date.issued | 2018-01-01 | |
dc.description.abstract | <p>In this thesis, we study the problem of estimating the number of triangles of an undirected graph in the data stream model. Some of the well-known streaming algorithms work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, the neighborhood sampling algorithm attempts to sample a triangle by randomly choosing a single edge e, a single neighbor f of e and waits for a third edge that completes the triangle. The basic sampling step in the algorithm is repeated multiple times to obtain an estimate for the global triangle count in the input graph stream. In this work, we propose a multi-sampling variant of this algorithm. We provide a theoretical analysis of the algorithm and prove that it improves upon the known space and accuracy bounds. We experimentally show that this algorithm outperforms several well-known triangle counting streaming algorithms.</p> | |
dc.format.mimetype | application/pdf | |
dc.identifier | archive/lib.dr.iastate.edu/etd/16644/ | |
dc.identifier.articleid | 7651 | |
dc.identifier.contextkey | 12816823 | |
dc.identifier.s3bucket | isulib-bepress-aws-west | |
dc.identifier.submissionpath | etd/16644 | |
dc.identifier.uri | https://dr.lib.iastate.edu/handle/20.500.12876/30827 | |
dc.language.iso | en | |
dc.source.bitstream | archive/lib.dr.iastate.edu/etd/16644/MousaviHanjani_iastate_0097M_17579.pdf|||Fri Jan 14 21:03:45 UTC 2022 | |
dc.subject.disciplines | Computer Sciences | |
dc.subject.keywords | big data | |
dc.subject.keywords | data mining | |
dc.subject.keywords | graph mining | |
dc.subject.keywords | streaming algorithms | |
dc.title | Improved triangle counting in graph streams: Neighborhood multi-sampling | |
dc.type | article | |
dc.type.genre | thesis | |
dspace.entity.type | Publication | |
relation.isOrgUnitOfPublication | f7be4eb9-d1d0-4081-859b-b15cee251456 | |
thesis.degree.discipline | Computer Science | |
thesis.degree.level | thesis | |
thesis.degree.name | Master of Science |
File
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- MousaviHanjani_iastate_0097M_17579.pdf
- Size:
- 474.49 KB
- Format:
- Adobe Portable Document Format
- Description: