Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 705402

Time- and Space-Efficient Sliding Window Top-k Query Processing


Pripužić, Krešimir; Podnar Žarko, Ivana; Aberer, Karl
Time- and Space-Efficient Sliding Window Top-k Query Processing // ACM transactions on database systems, 40 (2015), 1; 1-1 doi:10.1145/2736701 (međunarodna recenzija, članak, znanstveni)


CROSBI ID: 705402 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

Naslov
Time- and Space-Efficient Sliding Window Top-k Query Processing

Autori
Pripužić, Krešimir ; Podnar Žarko, Ivana ; Aberer, Karl

Izvornik
ACM transactions on database systems (0362-5915) 40 (2015), 1; 1-1

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
data stream processing; continuous top-k queries; sliding windows

Sažetak
A sliding window top-k (top-k/w) query monitors incoming data stream objects within a sliding window of size w to identify the k best-ranked objects with respect to a given scoring function over time. Processing of such queries is challenging because, even when an object is not a top-k/w object at the time when it enters the processing system, it might become one in future. Thus a set of potential top-k/w objects has to be stored in memory while its size should be minimized to efficiently cope with high data streaming rates. Existing approaches typically store top-k/w and candidate sliding window objects in a k-skyband over a two-dimensional score-time space. However, due to continuous changes of the k-skyband, its maintenance is quite costly. Probabilistic k-skyband is a novel data structure storing data stream objects from a sliding window with significant probability to become top-k/w objects in future. Continuous probabilistic k- skyband maintenance offers considerably improved runtime performance compared to k-skyband maintenance, especially for large values of k, at the expense of a small and controllable probability of error. We propose two possible probabilistic k-skyband usages: (i) When it is used to process all sliding window objects, the resulting top-k/w algorithm is approximate and adequate for processing random-order data streams. (ii) When probabilistic k-skyband is used to process only a subset of most recent sliding window objects, it can improve the runtime performance of continuous k-skyband maintenance resulting in a novel exact top-k/w algorithm. Our experimental evaluation systematically compares different top-k/w processing algorithms and shows that while competing algorithms offer either time efficiency at the expanse of space efficiency, or vice-versa, our algorithms based on the probabilistic k-skyband are both time and space efficient.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Elektrotehnika, Računarstvo



POVEZANOST RADA


Ustanove:
Fakultet elektrotehnike i računarstva, Zagreb

Poveznice na cjeloviti tekst rada:

doi dl.acm.org

Citiraj ovu publikaciju:

Pripužić, Krešimir; Podnar Žarko, Ivana; Aberer, Karl
Time- and Space-Efficient Sliding Window Top-k Query Processing // ACM transactions on database systems, 40 (2015), 1; 1-1 doi:10.1145/2736701 (međunarodna recenzija, članak, znanstveni)
Pripužić, K., Podnar Žarko, I. & Aberer, K. (2015) Time- and Space-Efficient Sliding Window Top-k Query Processing. ACM transactions on database systems, 40 (1), 1-1 doi:10.1145/2736701.
@article{article, year = {2015}, pages = {1-1-1-44}, DOI = {10.1145/2736701}, keywords = {data stream processing, continuous top-k queries, sliding windows}, journal = {ACM transactions on database systems}, doi = {10.1145/2736701}, volume = {40}, number = {1}, issn = {0362-5915}, title = {Time- and Space-Efficient Sliding Window Top-k Query Processing}, keyword = {data stream processing, continuous top-k queries, sliding windows} }
@article{article, year = {2015}, pages = {1-1-1-44}, DOI = {10.1145/2736701}, keywords = {data stream processing, continuous top-k queries, sliding windows}, journal = {ACM transactions on database systems}, doi = {10.1145/2736701}, volume = {40}, number = {1}, issn = {0362-5915}, title = {Time- and Space-Efficient Sliding Window Top-k Query Processing}, keyword = {data stream processing, continuous top-k queries, sliding windows} }

Časopis indeksira:


  • Current Contents Connect (CCC)
  • Web of Science Core Collection (WoSCC)
    • Science Citation Index Expanded (SCI-EXP)
    • SCI-EXP, SSCI i/ili A&HCI
  • Scopus


Citati:





    Contrast
    Increase Font
    Decrease Font
    Dyslexic Font