| LDR | | 02468nmm uu200421 4500 |
| 001 | | 000000332794 |
| 005 | | 20240805171611 |
| 008 | | 181129s2018 |||||||||||||||||c||eng d |
| 020 | |
▼a 9780438018822 |
| 035 | |
▼a (MiAaPQ)AAI10809873 |
| 035 | |
▼a (MiAaPQ)purdue:22781 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 248032 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Zhou, Samson. |
| 245 | 10 |
▼a Approximating Properties of Data Streams. |
| 260 | |
▼a [S.l.] :
▼b Purdue University.,
▼c 2018 |
| 260 | 1 |
▼a Ann Arbor :
▼b ProQuest Dissertations & Theses,
▼c 2018 |
| 300 | |
▼a 135 p. |
| 500 | |
▼a Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B. |
| 500 | |
▼a Advisers: Greg N. Frederickson |
| 502 | 1 |
▼a Thesis (Ph.D.)--Purdue University, 2018. |
| 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 |
| 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 t |
| 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 exponentia |
| 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 proble |
| 590 | |
▼a School code: 0183. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 710 | 20 |
▼a Purdue University.
▼b Computer Sciences. |
| 773 | 0 |
▼t Dissertation Abstracts International
▼g 79-10B(E). |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0183 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2018 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T14997908
▼n KERIS |
| 980 | |
▼a 201812
▼f 2019 |
| 990 | |
▼a 관리자 |