Fast Similarity Graph Construction via Data Sketching Techniques

Simple item page
dc.contributor.advisorAn, Aijun
dc.contributor.advisorPapangelis, Manos
dc.contributor.authorMarefat. Hoorieh
dc.date.accessioned2022-03-03T13:57:46Z
dc.date.available2022-03-03T13:57:46Z
dc.date.copyright2021-09
dc.date.issued2022-03-03
dc.date.updated2022-03-03T13:57:45Z
dc.degree.disciplineComputer Science
dc.degree.levelMaster's
dc.degree.nameMSc - Master of Science
dc.description.abstractGraphs are mathematical structures used to model objects and their pairwise relationships. Due to their simple but expressive abstract representation, they are commonly used to model various types of relations and processes in technological, social or biological systems and have found numerous applications. A special type of graph is the similarity graph in which nodes represent entities and there is an edge connecting two nodes if the two entities are similar based on some similarity measure. In a typical scenario, raw data of entities are provided in the form of a relational dataset, matrix or a tensor and a similarity graph is built to facilitate graph-based analysis like node importance, node classification, link prediction, community detection, outlier detection, and more. The ability to construct similarity graphs fast is important and with a potential for high impact, thus several approximation techniques have been proposed. In this work, we propose data sketching based methods for fast approximate similarity graph construction. Data sketching techniques are applied on the raw data and are designed to achieve desired error guarantees. They can drastically reduce the size of raw data on which we operate, allowing for faster construction and analysis of similarity graphs, but with approximate results. This is a desirable tradeoff for many applications in diverse domains. Through a thorough experimental evaluation, we demonstrate that our sketching methods outperform sensible baselines and competitor methods proposed for the problem. First, they are much faster than exact methods while maintaining high accuracy in constructing the similarity graph. Furthermore, our methods demonstrate significantly higher accuracy than competitive methods on generic graph analysis tasks. We demonstrate the effectiveness of our methods on different real-world graph applications.
dc.identifier.urihttp://hdl.handle.net/10315/39059
dc.languageen
dc.rightsAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.
dc.subjectComputer science
dc.subject.keywordsData mining
dc.subject.keywordsGraphs
dc.subject.keywordsSimilarity graphs
dc.subject.keywordsData sketching
dc.subject.keywordsData sampling
dc.titleFast Similarity Graph Construction via Data Sketching Techniques
dc.typeElectronic Thesis or Dissertation

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Marefat_Hoorieh_2021_Masters.pdf
Size:
4.36 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
license.txt
Size:
1.87 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
YorkU_ETDlicense.txt
Size:
3.39 KB
Format:
Plain Text
Description:
Download

Collections

Computer Science

All items in the YorkSpace institutional repository are protected by copyright, with all rights reserved except where explicitly noted.