{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/95257"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/95257","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Per-flow cardinality estimation based on virtual LogLog sketching","abstract":"Flow cardinality estimation is the problem of estimating the number of distinct elements in a data flow, often with a stringent memory constraint. It has wide applications in network traffic measurement and in database systems. The virtual LogLog algorithm proposed recently by Xiao, Chen, Chen and Ling estimates the cardinalities of a large number of flows with a compact memory. The purpose of this thesis is to explore two new perspectives on the estimation process of this algorithm. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator and evaluate the performance of the vHLL estimator compared to other estimators in this family. Secondly, we propose an alternative solution to the estimation problem by deriving a maximum-likelihood estimator. Empirical evidence from both perspectives suggests the near-optimality of the vHLL estimator for per-flow estimation, analogous to the near-optimality of the HLL estimator for single-flow estimation.","abstract_html":"Flow cardinality estimation is the problem of estimating the number of distinct elements in a data flow, often with a stringent memory constraint. It has wide applications in network traffic measurement and in database systems. The virtual LogLog algorithm proposed recently by Xiao, Chen, Chen and Ling estimates the cardinalities of a large number of flows with a compact memory. The purpose of this thesis is to explore two new perspectives on the estimation process of this algorithm. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator and evaluate the performance of the vHLL estimator compared to other estimators in this family. Secondly, we propose an alternative solution to the estimation problem by deriving a maximum-likelihood estimator. Empirical evidence from both perspectives suggests the near-optimality of the vHLL estimator for per-flow estimation, analogous to the near-optimality of the HLL estimator for single-flow estimation.","abstract_has_math":false,"creators":["Zhou, Zeyu"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hajek, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-03-01T15:45:48Z","date_published":"2017-03-01T15:45:48Z","updated_at":"2026-07-22T22:26:35Z","subjects":["Network traffic measurement","Per-flow cardinality estimation","Maximum-likelihood estimator","Virtual LogLog sketch"],"languages":["en"],"rights":["Copyright 2016 Zeyu Zhou"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/95257","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce"]},{"key":"dc:creator","label":"Author","values":["Zhou, Zeyu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-03-01T15:45:48Z","2016-08-12","2016-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Network traffic measurement","Per-flow cardinality estimation","Maximum-likelihood estimator","Virtual LogLog sketch"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Zeyu Zhou"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/95257"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Flow cardinality estimation is the problem of estimating the number of distinct elements in a data flow, often with a stringent memory constraint. It has wide applications in network traffic measurement and in database systems. The virtual LogLog algorithm proposed recently by Xiao, Chen, Chen and Ling estimates the cardinalities of a large number of flows with a compact memory. The purpose of this thesis is to explore two new perspectives on the estimation process of this algorithm. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator and evaluate the performance of the vHLL estimator compared to other estimators in this family. Secondly, we propose an alternative solution to the estimation problem by deriving a maximum-likelihood estimator. Empirical evidence from both perspectives suggests the near-optimality of the vHLL estimator for per-flow estimation, analogous to the near-optimality of the HLL estimator for single-flow estimation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Zeyu Zhou, accepted the attached license on 2016-08-11 at 21:28.","The student, Zeyu Zhou, submitted this Thesis for approval on 2016-08-11 at 21:36.","This Thesis was approved for publication on 2016-08-12 at 09:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10107 on 2017-02-28 at 14:45:11","Made available in DSpace on 2017-03-01T15:45:48Z (GMT). No. of bitstreams: 38 ZHOU-THESIS-2016.pdf: 1210821 bytes, checksum: ea34506969d95d203d6d128faff2a88d (MD5) ECE LaTeX Guide.pdf: 474070 bytes, checksum: e8e464e7ffe94df947bd1fce06837204 (MD5) IEEE_ECE.bst: 59476 bytes, checksum: 7668c5e97bcc2d22a9f8d4eab9b269ee (MD5) Zeyu_Zhou_master_thesis.tex: 6543 bytes, checksum: e94b4b14b24fbf774f873a46830e712a (MD5) Zipf_2_25.png: 38343 bytes, checksum: bf4047ba51253e7b7792b776aaa1b4dc (MD5) Zn_merge.jpg: 34661 bytes, checksum: e48ccccaf82f611ed566306441987a30 (MD5) abs.tex: 1007 bytes, checksum: 2b6004d3596cf0d266192998a46a6091 (MD5) ack.tex: 195 bytes, checksum: 26c4fe2191e9614bc383a06c66124cf3 (MD5) alpha_vs_theta.png: 35989 bytes, checksum: 249111fe11db887a0366aacc86b1cd4c (MD5) beta_vs_theta.png: 33706 bytes, checksum: 3576b44ed0c2bd9e0d44bf71a4467192 (MD5) bias_const_vs_cardinality_for_k1024.png: 50283 bytes, checksum: d72f3c6e06dce433bb5b21b68cdfb5c4 (MD5) bias_const_vs_cardinality_for_k256.png: 42495 bytes, checksum: 1282c6fe1f1641d35df9fd93abd7cbbe (MD5) bias_const_vs_cardinality_for_k512.png: 46128 bytes, checksum: 6dcea001fbfe18536ea09580873609be (MD5) ch1_introduction.tex: 9188 bytes, checksum: 8a3ea8ffeae739d43fa321c5468da068 (MD5) ch2_preliminaries.tex: 25604 bytes, checksum: 0f1ffcdf3af922cf492c2515db3b64f4 (MD5) ch3_generalize_theta.tex: 20877 bytes, checksum: 6e2f30fc307779505e97abe86d08baf4 (MD5) ch4_mle.tex: 25970 bytes, checksum: ce250a07b4e39d3ca56bad821cfbcec2 (MD5) ch5_conclusion.tex: 2409 bytes, checksum: 3a3e8845337498bba7c1c7837fe36a9d (MD5) mle_vs_vhll_on_bias.png: 29520 bytes, checksum: bc96955b74ac7a33f80aa7f8e5d7a932 (MD5) mle_vs_vhll_on_std_err.png: 42092 bytes, checksum: 3458673aef1e19a8e896890d701787b8 (MD5) std_err_vs_theta_n10000000.png: 36723 bytes, checksum: 73d3d86f08adcb105dea9775236eaeb3 (MD5) stream_and_sketch.jpg: 11371 bytes, checksum: 3f5e182581388c4169ab94aaaface030 (MD5) thesisrefs.bib: 8548 bytes, checksum: 06565e348c7472cd743b4b1e85f01215 (MD5) trace1_Z_cdf.png: 20633 bytes, checksum: d21e6fa9b800cdb6f0c9d7d764fa7f9d (MD5) trace1_Z_pmf.png: 22086 bytes, checksum: 4a8f6f6f1e359844c32df8e0dc2ef8c4 (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_1000.png: 30109 bytes, checksum: 2f67e2854e23fda5ab4bfb71688da7e0 (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_150.png: 29948 bytes, checksum: a23688a022a32f59f6f53a1c7632178c (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_31536.png: 29359 bytes, checksum: 3be0dc7ec8548cfbb87486dff211cc7a (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_611.png: 33763 bytes, checksum: 9f67f494254decc49723cad1db73986f (MD5) trace_flow_cardi_dist.png: 44969 bytes, checksum: a652f3402c32e9583a9f0f36dd3bf19f (MD5) uiucecethesis09.cls: 21648 bytes, checksum: c5f7737324f5e024f39a6443b2b00347 (MD5) vLL-1_est_vs_act.png: 59995 bytes, checksum: a8bf54ea051bb26e9fc59d1fb791954d (MD5) vLL_MLE_est_vs_act.png: 60107 bytes, checksum: 450d917f99f658768ae41080a9ca9a3b (MD5) virtual_estimator_example.jpg: 47658 bytes, checksum: 9218a8c1fd57fd3f8a4763de77afefce (MD5) wse_vs_theta.png: 34193 bytes, checksum: 97a86b596043a2d009e55032a45ab552 (MD5) wse_vs_theta_plus_mle.png: 36837 bytes, checksum: 7e03e95d92ca01477d867d1b465b3c02 (MD5) xi_vs_theta.png: 36105 bytes, checksum: a74091fdc6f25193d798c10664cc7f94 (MD5) LICENSE.txt: 4206 bytes, checksum: 77f348ec2dc5ff508307e85a73a2c5a2 (MD5) Previous issue date: 2016-08-12"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Per-flow cardinality estimation based on virtual LogLog sketching"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce"],"dc:creator":["Zhou, Zeyu"],"dc:date":["2017-03-01T15:45:48Z","2016-08-12","2016-12"],"dc:description":["Flow cardinality estimation is the problem of estimating the number of distinct elements in a data flow, often with a stringent memory constraint. It has wide applications in network traffic measurement and in database systems. The virtual LogLog algorithm proposed recently by Xiao, Chen, Chen and Ling estimates the cardinalities of a large number of flows with a compact memory. The purpose of this thesis is to explore two new perspectives on the estimation process of this algorithm. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator and evaluate the performance of the vHLL estimator compared to other estimators in this family. Secondly, we propose an alternative solution to the estimation problem by deriving a maximum-likelihood estimator. Empirical evidence from both perspectives suggests the near-optimality of the vHLL estimator for per-flow estimation, analogous to the near-optimality of the HLL estimator for single-flow estimation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Zeyu Zhou, accepted the attached license on 2016-08-11 at 21:28.","The student, Zeyu Zhou, submitted this Thesis for approval on 2016-08-11 at 21:36.","This Thesis was approved for publication on 2016-08-12 at 09:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10107 on 2017-02-28 at 14:45:11","Made available in DSpace on 2017-03-01T15:45:48Z (GMT). No. of bitstreams: 38 ZHOU-THESIS-2016.pdf: 1210821 bytes, checksum: ea34506969d95d203d6d128faff2a88d (MD5) ECE LaTeX Guide.pdf: 474070 bytes, checksum: e8e464e7ffe94df947bd1fce06837204 (MD5) IEEE_ECE.bst: 59476 bytes, checksum: 7668c5e97bcc2d22a9f8d4eab9b269ee (MD5) Zeyu_Zhou_master_thesis.tex: 6543 bytes, checksum: e94b4b14b24fbf774f873a46830e712a (MD5) Zipf_2_25.png: 38343 bytes, checksum: bf4047ba51253e7b7792b776aaa1b4dc (MD5) Zn_merge.jpg: 34661 bytes, checksum: e48ccccaf82f611ed566306441987a30 (MD5) abs.tex: 1007 bytes, checksum: 2b6004d3596cf0d266192998a46a6091 (MD5) ack.tex: 195 bytes, checksum: 26c4fe2191e9614bc383a06c66124cf3 (MD5) alpha_vs_theta.png: 35989 bytes, checksum: 249111fe11db887a0366aacc86b1cd4c (MD5) beta_vs_theta.png: 33706 bytes, checksum: 3576b44ed0c2bd9e0d44bf71a4467192 (MD5) bias_const_vs_cardinality_for_k1024.png: 50283 bytes, checksum: d72f3c6e06dce433bb5b21b68cdfb5c4 (MD5) bias_const_vs_cardinality_for_k256.png: 42495 bytes, checksum: 1282c6fe1f1641d35df9fd93abd7cbbe (MD5) bias_const_vs_cardinality_for_k512.png: 46128 bytes, checksum: 6dcea001fbfe18536ea09580873609be (MD5) ch1_introduction.tex: 9188 bytes, checksum: 8a3ea8ffeae739d43fa321c5468da068 (MD5) ch2_preliminaries.tex: 25604 bytes, checksum: 0f1ffcdf3af922cf492c2515db3b64f4 (MD5) ch3_generalize_theta.tex: 20877 bytes, checksum: 6e2f30fc307779505e97abe86d08baf4 (MD5) ch4_mle.tex: 25970 bytes, checksum: ce250a07b4e39d3ca56bad821cfbcec2 (MD5) ch5_conclusion.tex: 2409 bytes, checksum: 3a3e8845337498bba7c1c7837fe36a9d (MD5) mle_vs_vhll_on_bias.png: 29520 bytes, checksum: bc96955b74ac7a33f80aa7f8e5d7a932 (MD5) mle_vs_vhll_on_std_err.png: 42092 bytes, checksum: 3458673aef1e19a8e896890d701787b8 (MD5) std_err_vs_theta_n10000000.png: 36723 bytes, checksum: 73d3d86f08adcb105dea9775236eaeb3 (MD5) stream_and_sketch.jpg: 11371 bytes, checksum: 3f5e182581388c4169ab94aaaface030 (MD5) thesisrefs.bib: 8548 bytes, checksum: 06565e348c7472cd743b4b1e85f01215 (MD5) trace1_Z_cdf.png: 20633 bytes, checksum: d21e6fa9b800cdb6f0c9d7d764fa7f9d (MD5) trace1_Z_pmf.png: 22086 bytes, checksum: 4a8f6f6f1e359844c32df8e0dc2ef8c4 (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_1000.png: 30109 bytes, checksum: 2f67e2854e23fda5ab4bfb71688da7e0 (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_150.png: 29948 bytes, checksum: a23688a022a32f59f6f53a1c7632178c (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_31536.png: 29359 bytes, checksum: 3be0dc7ec8548cfbb87486dff211cc7a (MD5) trace1_log_likelihood_vs_n_with_actual_cardi_611.png: 33763 bytes, checksum: 9f67f494254decc49723cad1db73986f (MD5) trace_flow_cardi_dist.png: 44969 bytes, checksum: a652f3402c32e9583a9f0f36dd3bf19f (MD5) uiucecethesis09.cls: 21648 bytes, checksum: c5f7737324f5e024f39a6443b2b00347 (MD5) vLL-1_est_vs_act.png: 59995 bytes, checksum: a8bf54ea051bb26e9fc59d1fb791954d (MD5) vLL_MLE_est_vs_act.png: 60107 bytes, checksum: 450d917f99f658768ae41080a9ca9a3b (MD5) virtual_estimator_example.jpg: 47658 bytes, checksum: 9218a8c1fd57fd3f8a4763de77afefce (MD5) wse_vs_theta.png: 34193 bytes, checksum: 97a86b596043a2d009e55032a45ab552 (MD5) wse_vs_theta_plus_mle.png: 36837 bytes, checksum: 7e03e95d92ca01477d867d1b465b3c02 (MD5) xi_vs_theta.png: 36105 bytes, checksum: a74091fdc6f25193d798c10664cc7f94 (MD5) LICENSE.txt: 4206 bytes, checksum: 77f348ec2dc5ff508307e85a73a2c5a2 (MD5) Previous issue date: 2016-08-12"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/95257"],"dc:language":["en"],"dc:rights":["Copyright 2016 Zeyu Zhou"],"dc:subject":["Network traffic measurement","Per-flow cardinality estimation","Maximum-likelihood estimator","Virtual LogLog sketch"],"dc:title":["Per-flow cardinality estimation based on virtual LogLog sketching"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:35Z"}