東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Fair and Scalable Algorithms on Mass...

Knittel, Marina,

Linked to FindBook

Google Book

Amazon

博客來

Fair and Scalable Algorithms on Massive Graphs /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Fair and Scalable Algorithms on Massive Graphs // Marina Knittel.
Author:	Knittel, Marina,
Description:	1 electronic resource (368 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-08, Section: A.
Contained By:	Dissertations Abstracts International85-08A.
Subject:	Computer science. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30692280
ISBN:	9798381694710

Fair and Scalable Algorithms on Massive Graphs /
Knittel, Marina,

Fair and Scalable Algorithms on Massive Graphs /Marina Knittel. - 1 electronic resource (368 pages)

Source: Dissertations Abstracts International, Volume: 85-08, Section: A.

The impact of massive data processing on our daily lives is becoming increasingly more clear. With this, we must guarantee that vital, data-driven decision-making systems mitigate the potential negative impacts of the technologies themselves and scale to the massive datasets we have access to today. We explore both of these facets by studying fairness and scalability for algorithms on large graphs.In Part I, we focus on on fair hierarchical clustering. Our first work on this topic [Ahmadian et al., 2020b] initiates the study of fair hierarchical clustering by extending Chierichetti et al.'s [Chierichetti et al., 2017] notion of representationally proportional flat clustering to the hierarchical setting. From there, we introduce the first approximation algorithms for three well studied hierarchical clustering optimization problems in the fair context: cost [Dasgupta, 2016], revenue [Moseley and Wang, 2017], and value [Cohen-Addad et al., 2018]. Our initial work studies all three fair optimization problems, and our follow-up works [Knittel et al., 2023a, Knittel et al., 2023b] dive deeper into the notoriously difficult cost optimization problem.Regarding scalability, we leverage the Massively Parallel Computation (MPC) model, as well as its recent successor Adaptive Massively Parallel Computation (AMPC), to develop efficient graph algorithms for big data. MPC, discussed in Part II, has been one of the most practically useful models for massively parallel algorithms in the past decade, influencing a number of major frameworks including MapReduce, Hadoop, Spark, and Flume. In this model, we present our work on edge coloring [Behnezhad et al., 2019b], hierarchical clustering [Hajiaghayi and Knittel, 2020], and tree embeddings [Ahanchi et al., 2023].AMPC improves upon the MPC model by adding access to a distributed hash table while still remaining highly implementable in practice. This allows it to overcome some shortcomings proposed in MPC literature, notably, the 1vs2Cycle Conjecture (i.e., that differentiating between a single cycle and two cycles is difficult in MPC). In Part III, we introduce a highly efficient and general tool for executing tree contractions in AMPC [Hajiaghayi et al., 2022b] and additionally exhibit the power of AMPC on minimum cut problems [Hajiaghayi et al., 2022a].

English

ISBN: 9798381694710Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Approximation algorithms

Fair and Scalable Algorithms on Massive Graphs /
LDR:03814nmm a22004333i 4500 001 2437654
005 20251124054952.5
006 m o d
007 cr|nu||||||||
008 261011s2023 miu||||||m |||||||eng d
020 $a 9798381694710
035 $a (MiAaPQD)AAI30692280
035 $a AAI30692280
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Knittel, Marina, $e author. $0 (orcid)0009-0008-1498-7519 $3 3828716
245 1 0 $a Fair and Scalable Algorithms on Massive Graphs / $c Marina Knittel.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2023
300 $a 1 electronic resource (368 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-08, Section: A.
500 $a Advisors: Hajiaghayi, MohammadTaghi; Dickerson, John Committee members: Kumar, Ravi; Mount, David; Barg, Alexander.
502 $b Ph.D. $c University of Maryland, College Park $d 2023.
520 $a The impact of massive data processing on our daily lives is becoming increasingly more clear. With this, we must guarantee that vital, data-driven decision-making systems mitigate the potential negative impacts of the technologies themselves and scale to the massive datasets we have access to today. We explore both of these facets by studying fairness and scalability for algorithms on large graphs.In Part I, we focus on on fair hierarchical clustering. Our first work on this topic [Ahmadian et al., 2020b] initiates the study of fair hierarchical clustering by extending Chierichetti et al.'s [Chierichetti et al., 2017] notion of representationally proportional flat clustering to the hierarchical setting. From there, we introduce the first approximation algorithms for three well studied hierarchical clustering optimization problems in the fair context: cost [Dasgupta, 2016], revenue [Moseley and Wang, 2017], and value [Cohen-Addad et al., 2018]. Our initial work studies all three fair optimization problems, and our follow-up works [Knittel et al., 2023a, Knittel et al., 2023b] dive deeper into the notoriously difficult cost optimization problem.Regarding scalability, we leverage the Massively Parallel Computation (MPC) model, as well as its recent successor Adaptive Massively Parallel Computation (AMPC), to develop efficient graph algorithms for big data. MPC, discussed in Part II, has been one of the most practically useful models for massively parallel algorithms in the past decade, influencing a number of major frameworks including MapReduce, Hadoop, Spark, and Flume. In this model, we present our work on edge coloring [Behnezhad et al., 2019b], hierarchical clustering [Hajiaghayi and Knittel, 2020], and tree embeddings [Ahanchi et al., 2023].AMPC improves upon the MPC model by adding access to a distributed hash table while still remaining highly implementable in practice. This allows it to overcome some shortcomings proposed in MPC literature, notably, the 1vs2Cycle Conjecture (i.e., that differentiating between a single cycle and two cycles is difficult in MPC). In Part III, we introduce a highly efficient and general tool for executing tree contractions in AMPC [Hajiaghayi et al., 2022b] and additionally exhibit the power of AMPC on minimum cut problems [Hajiaghayi et al., 2022a].
546 $a English
590 $a School code: 0117
650 4 $a Computer science. $3 523869
650 4 $a Computer engineering. $3 621879
650 4 $a Logic. $3 529544
653 $a Approximation algorithms
653 $a Fair algorithms
653 $a Graph algorithms
653 $a Parallel computing
690 $a 0984
690 $a 0464
690 $a 0395
710 2 $a University of Maryland, College Park. $b Computer Science. $e degree granting institution. $3 3819227
720 1 $a Hajiaghayi, MohammadTaghi $e degree supervisor.
720 1 $a Dickerson, John $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 85-08A.
790 $a 0117
791 $a Ph.D.
792 $a 2023
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30692280