Processing exact results for sliding window joins over data streams using disk storage. (4th October 2010)

• Record Type: Journal Article
• Authors: Chakraborty, Abhirup; Singh, Ajit
• Is Part Of: International journal of intelligent information and database systems. Volume 4:Number 5(2010)
• Page Start: 462
• Page End: 486
• Publication Date: 2010-10-04
• Subjects: data streams -- join processing -- sliding windows -- performance -- disk storage -- memory limitations -- exact window join -- disk storage -- archive -- memory blocks; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

Abstract

We consider the problem of processing exact results for sliding window joins over data streams with limited memory. Existing approaches deal with memory limitations by shedding loads, and therefore cannot provide exact or even highly accurate results for sliding window joins over data streams showing time varying rate of data arrivals. We provide an exact window join (EWJ) algorithm incorporating disk storage as an archive. Our algorithm spills window data onto the disk on a periodic basis, refines the output result by properly retrieving the disk resident data, and maximises output rate by employing techniques to manage the memory blocks. The problem of managing the window blocks in memory – similar in nature to the caching issue – captures both the temporal and frequency related properties of the stream arrivals. We provide experimental results demonstrating the performance and effectiveness of the proposed algorithm.