EUVIMEDEUVIMED entdecken
Crossref

Quantile Estimation with Duplicates

Tianrui Xia, Ziling Chen, Shaoxu Song

Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-27

DOI: 10.1145/3786683 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Tianrui Xia und 2 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China, State Grid Ningxia Electric Power Co..

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Quantile estimation in data streams is a fundamental task in data analysis. Data structures named quantile sketches are constructed to summarize data and estimate quantiles using limited storage. Duplicate data records often occur in real-world data, while there is no relevant design or analysis in existing quantile sketches, including the best known method KLL sketch. In this paper, we present DupliSketch, a quantile sketch with optimizations for duplicates. The sketch compresses arrival duplicates into elements and performs randomized compaction operations to meet the space limit. To better summarize heavy-tailed data, DupliSketch maintains values frequent enough dynamically and counts them separately, while summarizes other values with weighted elements obtained from compactions. Analyses show its error in rank estimation, space complexity to provide error guarantees under input with duplicates, and time complexity. The approach is deployed as a user-defined function in a database Apache IoTDB. Extensive experiments support the theoretical analyses and compare DupliSketch with existing methods on real and synthetic datasets. On average, the error of the DupliSketch is 44% smaller than that of the baseline methods under the same space limit.

Förderung

  • National Key Research and Development Program of China
  • National Natural Science Foundation of China
  • State Grid Ningxia Electric Power Co.
  • Beijing National Research Center For Information Science And Technology

Zitieren

APA

Xia, T., Chen, Z., & Song, S. (2026). Quantile Estimation with Duplicates. Proceedings of the ACM on Management of Data, 4(1), 1-27. https://doi.org/10.1145/3786683

Vancouver

Xia T, Chen Z, Song S. Quantile Estimation with Duplicates. Proceedings of the ACM on Management of Data. 2026;4(1):1-27. doi:10.1145/3786683

BibTeX
@article{Xia2026,
  author = {Xia, Tianrui and Chen, Ziling and Song, Shaoxu},
  title = {Quantile Estimation with Duplicates},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {1},
  pages = {1--27},
  doi = {10.1145/3786683}
}
Kostenlos starten →