Mid Sweden University

miun.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Maintaining Stream Data Distribution Over Sliding Window
Mid Sweden University, Faculty of Science, Technology and Media, Department of Information Systems and Technology.
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In modern applications, it is a big challenge that analyzing the order statistics about the most recent parts of the high-volume and high velocity stream data. There are some online quantile algorithms that can

keep the sketch of the data in the sliding window and they can answer the quantile or rank query in a very short time. But most of them take the

GK algorithm as the subroutine, which is not known to be mergeable. In this paper, we propose another algorithm to keep the sketch that maintains the order statistics over sliding windows. For the fixed-size window, the existing algorithms can’t maintain the correctness in the process of updating the sliding window. Our algorithm not only can maintain the correctness but also can achieve similar performance of the optimal algorithm. Under the basis of maintaining the correctness, the insert time and query time are close to the best results, while others can't maintain the correctness. In addition to the fixed-size window algorithm, we also provide the time-based window algorithm that the window size varies over time. Last but not least, we provide the window aggregation algorithm which can help extend our algorithm into the distributed system.

Place, publisher, year, edition, pages
2018. , p. 55
Keywords [en]
Datastream, online algorithm, quantile problem, online analysis
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:miun:diva-35321Local ID: DT-V18-A2-003OAI: oai:DiVA.org:miun-35321DiVA, id: diva2:1273441
Subject / course
Computer Engineering DT1
Supervisors
Examiners
Available from: 2018-12-21 Created: 2018-12-21 Last updated: 2018-12-21Bibliographically approved

Open Access in DiVA

fulltext(2125 kB)365 downloads
File information
File name FULLTEXT01.pdfFile size 2125 kBChecksum SHA-512
c57eea3ed3d92fb3c4436bef7eee483ea2d134fdc0d53d0eebce1bb61cc4589c0849de1efa230a4a7f88851166ca9cbd9e0937a9096c620f9f989becd55ae815
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Chen, Jian
By organisation
Department of Information Systems and Technology
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 365 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 238 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf