2018/10/29 by Jiecao Chen, Qin Zhang, Chen, Jiecao +1
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Quality and Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1810.12388
openalex publication_date 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study how to perform distinct sampling in the streaming model where data contain near-duplicates. The goal of distinct sampling is to return a distinct element uniformly at random from the universe of elements, given that all the near-duplicates are treated as the same element. We also extend the result to the sliding window cases in which we are only interested in the most recent items. We present algorithms with provable theoretical guarantees for datasets in the Euclidean space, and also verify their effectiveness via an extensive set of experiments.