2016/06/03 by Reuven Cohen, Cohen, Reuven, Liran Katzir +3 · 1 citation
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1606.00996
openalex publication_date 2016/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years there has been a growing interest in developing "streaming\nalgorithms" for efficient processing and querying of continuous data streams.\nThese algorithms seek to provide accurate results while minimizing the required\nstorage and the processing time, at the price of a small inaccuracy in their\noutput. A fundamental query of interest is the intersection size of two big\ndata streams. This problem arises in many different application areas, such as\nnetwork monitoring, database systems, data integration and information\nretrieval. In this paper we develop a new algorithm for this problem, based on\nthe Maximum Likelihood (ML) method. We show that this algorithm outperforms all\nknown schemes and that it asymptotically achieves the optimal variance.\n