Systems and methods for reservoir sampling of streaming data and stream joins

US8392381B2 · kind B2 · utility

Assignee

• University of Vermont and State Agricultural College · US

Inventors

• Mohammed Al-Kateb · Colchester, US
• Byung Suk Lee · Ansan-si, KR
• Xiaoyang Wang · Shanghai, CN

Key dates

• Filing date: May 8, 2008
• Grant date: Mar 5, 2013
• Expiry date: Aug 2, 2028

Classification

• Technology area (CPC G): Physics
• CPC primary: G01D21/00
• WIPO field: Measurement
• WIPO sector: Instruments

Abstract

Algorithms and concepts for maintaining uniform random samples of streaming data and stream joins. These algorithms and concepts are used in systems and methods, such as wireless sensor networks and methods for implementing such networks, that generate and handle such streaming data and/or stream joins. The algorithms and concepts directed to streaming data allow one or more sample reservoirs to change size during sampling. When multiple reservoirs are maintained, some of the algorithms and concepts periodically reallocate memory among the multiple reservoirs to effectively utilize limited memory. The algorithms and concepts directed to stream joins allow reservoir sampling to proceed as a function of the probability of a join sampling operation. In memory limited situations wherein memory contains the sample reservoir and a join buffer, some of the stream join algorithms and concepts progressively increase the size of the sampling reservoir and reallocate memory from the join buffer to the reservoir.