Kueri Berkelanjutan untuk Interval Jumlah Maksimal Top-$K$ pada Data Streaming

Identifikasi berkelanjutan interval jumlah maksimal top-$k$ menggunakan jendela geser pada aliran data merupakan operasi penting untuk aplikasi di IoT dan lainnya. Interval jumlah maksimal adalah suburutan bersebelahan yang tidak tumpang tindih dengan jumlah maksimal dalam suatu urutan nilai bertanda. Algoritma yang ada tidak cocok untuk konteks streaming: algoritma tersebut要么 menghitung semua interval secara menyeluruh bahkan untuk nilai $k$ yang kecil, atau bergantung pada indeks yang memerlukan restrukturisasi yang sering dan mahal. Makalah ini mengatasi keterbatasan tersebut dengan mengusulkan strategi berbasis partisi yang baru.

Wawasan inti dari pendekatan yang diusulkan adalah skema partisi yang menjamin bahwa setiap interval jumlah maksimal sepenuhnya berada dalam satu partisi, sehingga memungkinkan pemrosesan independen dan paralel. Desain ini memberikan dua keuntungan utama: memungkinkan pemangkasan yang aman terhadap partisi yang tidak dapat berkontribusi pada hasil top-$k$, secara drastis mempersempit ruang pencarian, dan memungkinkan pemeliharaan inkremental yang efisien untuk interval jumlah maksimal di setiap partisi. Penulis mengembangkan algoritma untuk konstruksi partisi, pembaruan partisi inkremental, dan pencarian interval jumlah maksimal top-$k$ berbasis partisi.