東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Efficient Algorithms for Road Networ...

Ozel, Evrim,

Linked to FindBook

Google Book

Amazon

博客來

Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective // Evrim Ozel.
Author:	Ozel, Evrim,
Description:	1 electronic resource (124 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-02, Section: A.
Contained By:	Dissertations Abstracts International86-02A.
Subject:	Computer science. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31301216
ISBN:	9798383596722

Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective /
Ozel, Evrim,

Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective /Evrim Ozel. - 1 electronic resource (124 pages)

Source: Dissertations Abstracts International, Volume: 86-02, Section: A.

Experimental algorithmics, also referred to as algorithm engineering, is the principled approach of using empirical methods to complement traditional theoretical methods, both of which provide valuable insights for the analysis of algorithms. In this dissertation, we study various algorithmic problems for road networks and noisy sorting, analyzing them from both an experimental and theoretical perspective.We first study the problem of exact learning for road networks, and introduce an efficient randomized algorithm using simple distance queries, which can find missing roads and improve the quality of routing services. We provide a partial theoretical analysis based on a cluster degree parameter, dmax, then empirically show that this parameter is small for road networks by evaluating our algorithm on road network data for the U.S. and 4 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs. We also study the small-world navigability of the U.S. road network, inspired by the famous experiments done by Stanley Milgram which gave rise to the "six degrees of separation" expression. We introduce the Neighborhood Preferential Attachment Model, and perform extensive experiments with this model on U.S. road networks to show that our model outperforms other small-world models in terms of the average hop length, while having a more realistic scale-free degree distribution.We then study the problem of sorting n comparable distinct elements, subject to noisy comparison errors, such that the comparison of two elements returns the wrong answer according to a fixed probability pe > 1/2. We provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. We then experimentally compare our algorithms and other sorting algorithms. Lastly, we study the noisy sorting problem in an external-memory setting, providing new efficient methods that are in the external-memory model for sorting with comparison errors. Our algorithms achieve an optimal number of I/Os, in both cache-aware and cache-oblivious settings.

English

ISBN: 9798383596722Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Efficient algorithms

Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective /
LDR:03728nmm a22004453i 4500 001 2428561
005 20250414021856.5
006 m o d
007 cr|nu||||||||
008 261011s2024 miu||||||m |||||||eng d
020 $a 9798383596722
035 $a (MiAaPQD)AAI31301216
035 $a AAI31301216
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Ozel, Evrim, $e author. $3 3815861
245 1 0 $a Efficient Algorithms for Road Networks and Noisy Sorting: An Experimental and Theoretical Perspective / $c Evrim Ozel.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2024
300 $a 1 electronic resource (124 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: 86-02, Section: A.
500 $a Advisors: Goodrich, Michael T. Committee members: Dillencourt, Michael B.; Eppstein, David.
502 $b Ph.D. $c University of California, Irvine $d 2024.
520 $a Experimental algorithmics, also referred to as algorithm engineering, is the principled approach of using empirical methods to complement traditional theoretical methods, both of which provide valuable insights for the analysis of algorithms. In this dissertation, we study various algorithmic problems for road networks and noisy sorting, analyzing them from both an experimental and theoretical perspective.We first study the problem of exact learning for road networks, and introduce an efficient randomized algorithm using simple distance queries, which can find missing roads and improve the quality of routing services. We provide a partial theoretical analysis based on a cluster degree parameter, dmax, then empirically show that this parameter is small for road networks by evaluating our algorithm on road network data for the U.S. and 4 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs. We also study the small-world navigability of the U.S. road network, inspired by the famous experiments done by Stanley Milgram which gave rise to the "six degrees of separation" expression. We introduce the Neighborhood Preferential Attachment Model, and perform extensive experiments with this model on U.S. road networks to show that our model outperforms other small-world models in terms of the average hop length, while having a more realistic scale-free degree distribution.We then study the problem of sorting n comparable distinct elements, subject to noisy comparison errors, such that the comparison of two elements returns the wrong answer according to a fixed probability pe > 1/2. We provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. We then experimentally compare our algorithms and other sorting algorithms. Lastly, we study the noisy sorting problem in an external-memory setting, providing new efficient methods that are in the external-memory model for sorting with comparison errors. Our algorithms achieve an optimal number of I/Os, in both cache-aware and cache-oblivious settings.
546 $a English
590 $a School code: 0030
650 4 $a Computer science. $3 523869
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Information science. $3 554358
653 $a Efficient algorithms
653 $a Road networks
653 $a Noisy sorting
653 $a Preferential Attachment Models
653 $a Cache
690 $a 0984
690 $a 0642
690 $a 0800
690 $a 0723
710 2 $a University of California, Irvine. $b Computer Science. $e degree granting institution. $3 3815862
720 1 $a Goodrich, Michael T. $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-02A.
790 $a 0030
791 $a Ph.D.
792 $a 2024
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31301216