國立虎尾科技大學 |

Approximating Properties of Data Streams.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Approximating Properties of Data Streams./
作者:	Zhou, Samson.
面頁冊數:	1 online resource (135 pages)
附註:	Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Contained By:	Dissertation Abstracts International79-10B(E).
標題:	Computer science. -
電子資源:	click for full text (PQDT)
ISBN:	9780438018822

Approximating Properties of Data Streams.
Zhou, Samson.

Approximating Properties of Data Streams. - 1 online resource (135 pages)

Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.

Thesis (Ph.D.)--Purdue University, 2018.

Includes bibliographical references

In this dissertation, we present algorithms that approximate properties in the data stream model, where elements of an underlying data set arrive sequentially, but algorithms must use space sublinear in the size of the underlying data set.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780438018822Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Approximating Properties of Data Streams.
LDR:03606ntm a2200373Ki 4500 001 919186
005 20181116131021.5
006 m o u
007 cr mn||||a|a||
008 190606s2018 xx obm 000 0 eng d
020 $a 9780438018822
035 $a (MiAaPQ)AAI10809873
035 $a (MiAaPQ)purdue:22781
035 $a AAI10809873
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Zhou, Samson. $3 1193697
245 1 0 $a Approximating Properties of Data Streams.
264 0 $c 2018
300 $a 1 online resource (135 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: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
500 $a Advisers: Greg N. Frederickson; Elena Grigorescu.
502 $a Thesis (Ph.D.)--Purdue University, 2018.
504 $a Includes bibliographical references
520 $a In this dissertation, we present algorithms that approximate properties in the data stream model, where elements of an underlying data set arrive sequentially, but algorithms must use space sublinear in the size of the underlying data set.
520 $a We first study the problem of finding all k-periods of a length-n string S, presented as a data stream. S is said to have k-period p if its prefix of length n-p differs from its suffix of length n-p in at most k locations. We give algorithms to compute the k-periods of a string S using poly(k, log n) bits of space and we complement these results with comparable lower bounds.
520 $a We then study the problem of identifying a longest substring of strings S and T of length n that forms a d-near-alignment under the edit distance, in the simultaneous streaming model. In this model, symbols of strings S and T are streamed at the same time and form a d-near-alignment if the distance between them in some given metric is at most d. We give several algorithms, including an exact one-pass algorithm that uses O(d 2 + d log n) bits of space.
520 $a We then consider the distinct elements and lP problems in the sliding window model, where only the most recent n elements in the data stream form the underlying set. We first introduce the composable histogram , a simple twist on the exponential (Datar et al., SODA 2002) and smooth histograms (Braverman and Ostrovsky, FOCS 2007) that may be of independent interest. We then show that the composable histogram along with a careful combination of existing techniques to track either the identity or frequency of a few specific items suffices to obtain algorithms for both distinct elements and lP-heavy hitters that is nearly optimal in both n and epsilon .
520 $a Finally, we consider the problem of estimating the maximum weighted matching of a graph whose edges are revealed in a streaming fashion. We develop a reduction from the maximum weighted matching problem to the maximum cardinality matching problem that only doubles the approximation factor of a streaming algorithm developed for the maximum cardinality matching problem. As an application, we obtain an estimator for the weight of a maximum weighted matching in bounded-arboricity graphs and in particular, a (48+ epsilon)-approximation estimator for the weight of a maximum weighted matching in planar graphs.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Purdue University. $b Computer Sciences. $3 1179390
773 0 $t Dissertation Abstracts International $g 79-10B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10809873 $z click for full text (PQDT)