Skip to main content
Erschienen in: Peer-to-Peer Networking and Applications 2/2021

13.11.2020

Revisiting the coupon collector’s problem to unveil users’ online sessions in networked systems

verfasst von: Weverton Cordeiro, Luciano Gaspary, Rafael Beltran, Kayuã Paim, Rodrigo Mansilha

Erschienen in: Peer-to-Peer Networking and Applications | Ausgabe 2/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Accuratecomprehension of users’ behavior is paramount for understanding the dynamics of several systems, such as e-commerce platforms, social networks, and mobile computing. To this end, several strategies have been proposed to obtain data sets based on the capture of usage information, which can then serve for user analytics. A popular strategy consists of taking periodic snapshots of online users, a practical instance of the coupon collector’s problem tailored to users monitoring in networked systems. Due to system-specific limitations, however, users may fail to appear in some snapshots, although online. To bridge this gap, we present a methodology to correct ill-collected snapshots and build more accurate data sets. In summary, we formally model user snapshotting as an instance of the coupon collector’s problem, estimate the probability that some users are missing in a given snapshot following a Bernoulli process, and correct those snapshots should the probability exceed a given threshold.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
2
Link to the Github repo with scripts and source code of the software used in this work: https://​github.​com/​ComputerNetworks​-UFRGS/​TraceCollection/​
 
Literatur
1.
Zurück zum Zitat Vasilakos AV, Li Z, Simon G, You W (2015) Information centric network: Research challenges and opportunities. J Netw Comput Appl 52:1–10CrossRef Vasilakos AV, Li Z, Simon G, You W (2015) Information centric network: Research challenges and opportunities. J Netw Comput Appl 52:1–10CrossRef
2.
Zurück zum Zitat Han J, Choi D, Chung T, Chuah C-N, Kim H-C, Kwon TT (2019) Predicting content consumption from content-to-content relationships. J Netw Comput Appl 132:1–9CrossRef Han J, Choi D, Chung T, Chuah C-N, Kim H-C, Kwon TT (2019) Predicting content consumption from content-to-content relationships. J Netw Comput Appl 132:1–9CrossRef
3.
Zurück zum Zitat Tokuyama K, Miyoshi N (2018) Data rate and handoff rate analysis for user mobility in cellular networks. In: 2018 IEEE wireless communications and networking conference (WCNC). IEEE, pp 1–6 Tokuyama K, Miyoshi N (2018) Data rate and handoff rate analysis for user mobility in cellular networks. In: 2018 IEEE wireless communications and networking conference (WCNC). IEEE, pp 1–6
4.
Zurück zum Zitat Lareida A, Hoßfeld T, Stiller B (2017) The bittorrent peer collector problem. In: 2017 IFIP/IEEE symposium on integrated network and service management (IM). IEEE, pp 449–455 Lareida A, Hoßfeld T, Stiller B (2017) The bittorrent peer collector problem. In: 2017 IFIP/IEEE symposium on integrated network and service management (IM). IEEE, pp 449–455
5.
Zurück zum Zitat Zannettou S, Caulfield T, Blackburn J, De Cristofaro E, Sirivianos M, Stringhini G, Suarez-Tangil G (2018), NY, USA Zannettou S, Caulfield T, Blackburn J, De Cristofaro E, Sirivianos M, Stringhini G, Suarez-Tangil G (2018), NY, USA
6.
Zurück zum Zitat Hoßfeld T, Lehrieder F, Hock D, Oechsner S, Despotovic Z, Kellerer W, Michel M (2011) Characterization of BitTorrent swarms and their distribution in the Internet. Comput Netw 55(5):1197–1215CrossRef Hoßfeld T, Lehrieder F, Hock D, Oechsner S, Despotovic Z, Kellerer W, Michel M (2011) Characterization of BitTorrent swarms and their distribution in the Internet. Comput Netw 55(5):1197–1215CrossRef
8.
Zurück zum Zitat Cuevas R, Kryczka M, Cuevas A, Kaune S, Guerrero C, Rejaie R (2010) Is content publishing in BitTorrent altruistic or profit-driven?. In: 6Th international conference on emerging networking EXperiments and technologies (co-NEXT’10) Cuevas R, Kryczka M, Cuevas A, Kaune S, Guerrero C, Rejaie R (2010) Is content publishing in BitTorrent altruistic or profit-driven?. In: 6Th international conference on emerging networking EXperiments and technologies (co-NEXT’10)
9.
Zurück zum Zitat Yoshida M, Nakao A (2011) Measuring BitTorrent swarms beyond reach. In: IEEE international conference on peer-to-peer computing (P2P 2011), pp 220–229 Yoshida M, Nakao A (2011) Measuring BitTorrent swarms beyond reach. In: IEEE international conference on peer-to-peer computing (P2P 2011), pp 220–229
10.
Zurück zum Zitat Mansilha RB, Bays LR, Lehmann MB, Mezzomo A, Facchini G, Gaspary LP, Barcellos MP (2011) Observing the bittorrent universe through telescopes. In: 2011 IFIP/IEEE international symposium on integrated network management Mansilha RB, Bays LR, Lehmann MB, Mezzomo A, Facchini G, Gaspary LP, Barcellos MP (2011) Observing the bittorrent universe through telescopes. In: 2011 IFIP/IEEE international symposium on integrated network management
11.
Zurück zum Zitat Nyang D, Shin D (2016) Recyclable counter with confinement for real-time per-flow measurement. IEEE/ACM Trans Netw 24(5):3191–3203CrossRef Nyang D, Shin D (2016) Recyclable counter with confinement for real-time per-flow measurement. IEEE/ACM Trans Netw 24(5):3191–3203CrossRef
12.
Zurück zum Zitat Tan R, Kong X, Zhang Y, Tan Q, Lu H, Li M, Sun Y (2019) Bitcoin network size estimation based on coupon collection model. In: International conference on artificial intelligence and security. Springer, pp 298–307 Tan R, Kong X, Zhang Y, Tan Q, Lu H, Li M, Sun Y (2019) Bitcoin network size estimation based on coupon collection model. In: International conference on artificial intelligence and security. Springer, pp 298–307
14.
Zurück zum Zitat Flores H, Hui P, Nurmi P, Lagerspetz E, Tarkoma S, Manner J, Kostakos V, Li Y, Su X (2017) Evidence-aware mobile computational offloading. IEEE Trans Mob Comput 17(8):1834–1850CrossRef Flores H, Hui P, Nurmi P, Lagerspetz E, Tarkoma S, Manner J, Kostakos V, Li Y, Su X (2017) Evidence-aware mobile computational offloading. IEEE Trans Mob Comput 17(8):1834–1850CrossRef
15.
Zurück zum Zitat Lareida A, Stiller B (2018) Big torrent measurement: a country-, network-, and content-centric analysis of video sharing in bittorrent. In: NOMS 2018–2018 IEEE/IFIP network operations and management symposium. IEEE, pp 1–9 Lareida A, Stiller B (2018) Big torrent measurement: a country-, network-, and content-centric analysis of video sharing in bittorrent. In: NOMS 2018–2018 IEEE/IFIP network operations and management symposium. IEEE, pp 1–9
16.
Zurück zum Zitat Padmanabhan R, Schulman A, Levin D, Spring N (2019) Residential links under the weather. In: Proceedings of the ACM special interest group on data communication, SIGCOMM ’19. ACM, New York, pp 145–158 Padmanabhan R, Schulman A, Levin D, Spring N (2019) Residential links under the weather. In: Proceedings of the ACM special interest group on data communication, SIGCOMM ’19. ACM, New York, pp 145–158
17.
Zurück zum Zitat Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G (2016) Accurate recovery of internet traffic data: A tensor completion approach. In: IEEE INFOCOM 2016 - the 35th annual IEEE international conference on computer communications, pp 1–9 Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G (2016) Accurate recovery of internet traffic data: A tensor completion approach. In: IEEE INFOCOM 2016 - the 35th annual IEEE international conference on computer communications, pp 1–9
20.
Zurück zum Zitat Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G, Cao J, Zhang D (2018) Accurate recovery of internet traffic data: A sequential tensor completion approach. IEEE/ACM Trans Netw 26 (2):793–806CrossRef Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G, Cao J, Zhang D (2018) Accurate recovery of internet traffic data: A sequential tensor completion approach. IEEE/ACM Trans Netw 26 (2):793–806CrossRef
22.
Zurück zum Zitat Xie K, Chen Y, Wang X, Xie G, Cao J, Wen J (2020) Accurate and fast recovery of network monitoring data: A gpu accelerated matrix completion. IEEE/ACM Trans Netw:1–14 Xie K, Chen Y, Wang X, Xie G, Cao J, Wen J (2020) Accurate and fast recovery of network monitoring data: A gpu accelerated matrix completion. IEEE/ACM Trans Netw:1–14
23.
Zurück zum Zitat Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G, Cao J, Zhang D (2019) Accurate recovery of missing network measurement data with localized tensor completion. IEEE/ACM Trans Netw 27 (6):2222–2235CrossRef Xie K, Wang L, Wang X, Xie G, Wen J, Zhang G, Cao J, Zhang D (2019) Accurate recovery of missing network measurement data with localized tensor completion. IEEE/ACM Trans Netw 27 (6):2222–2235CrossRef
25.
Zurück zum Zitat Wang J, Shen J, Li P, Xu H (2017) Online matrix completion for signed link prediction. In: Proceedings of the tenth acm international conference on web search and data mining, WSDM ’17, association for computing machinery, New York, pp 475–484. https://doi.org/10.1145/3018661.3018681 Wang J, Shen J, Li P, Xu H (2017) Online matrix completion for signed link prediction. In: Proceedings of the tenth acm international conference on web search and data mining, WSDM ’17, association for computing machinery, New York, pp 475–484. https://​doi.​org/​10.​1145/​3018661.​3018681
26.
Zurück zum Zitat Izal M, Urvoy-Keller G, Biersack E, Felber P, Al Hamra A, Garcés-Erice L. (2004) Dissecting bittorrent: Five months in a torrent’s lifetime. In: Passive and active network measurement, vol 3015. Springer, Berlin, pp 1–11 Izal M, Urvoy-Keller G, Biersack E, Felber P, Al Hamra A, Garcés-Erice L. (2004) Dissecting bittorrent: Five months in a torrent’s lifetime. In: Passive and active network measurement, vol 3015. Springer, Berlin, pp 1–11
27.
Zurück zum Zitat Guo L, Chen S, Xiao Z, Tan E, Ding X, Zhang X (2005) Measurements, analysis, and modeling of bittorrent-like systems. In: 5th ACM SIGCOMM conference on internet measurement, IMC ’05. USENIX Association, Berkeley, pp 4–4 Guo L, Chen S, Xiao Z, Tan E, Ding X, Zhang X (2005) Measurements, analysis, and modeling of bittorrent-like systems. In: 5th ACM SIGCOMM conference on internet measurement, IMC ’05. USENIX Association, Berkeley, pp 4–4
28.
Zurück zum Zitat Steiner M, En-Najjary T, Biersack EW (2009) Long term study of peer behavior in the kad dht. IEEE/ACM Trans Netw 17(5):1371–1384CrossRef Steiner M, En-Najjary T, Biersack EW (2009) Long term study of peer behavior in the kad dht. IEEE/ACM Trans Netw 17(5):1371–1384CrossRef
29.
Zurück zum Zitat Jiang J-Y, Li C-T, Chen Y, Wang W (2018) Identifying users behind shared accounts in online streaming services. In: The 41st international ACM SIGIR conference on research & development in information retrieval, SIGIR ’18. ACM, New York, pp 65–74 Jiang J-Y, Li C-T, Chen Y, Wang W (2018) Identifying users behind shared accounts in online streaming services. In: The 41st international ACM SIGIR conference on research & development in information retrieval, SIGIR ’18. ACM, New York, pp 65–74
30.
Zurück zum Zitat Sottocornola G., Symeonidis P., Zanker M. (2018) Session-based news recommendations. In: Companion Proceedings of the The Web Conference 2018, WWW ’18, pp 1395–1399 Sottocornola G., Symeonidis P., Zanker M. (2018) Session-based news recommendations. In: Companion Proceedings of the The Web Conference 2018, WWW ’18, pp 1395–1399
31.
Zurück zum Zitat Zhang C, Dhungel P, Wu D, Ross KW (2011) Unraveling the bittorrent ecosystem. IEEE Trans Parallel Distrib Syst 22(7):1164–1177CrossRef Zhang C, Dhungel P, Wu D, Ross KW (2011) Unraveling the bittorrent ecosystem. IEEE Trans Parallel Distrib Syst 22(7):1164–1177CrossRef
39.
Zurück zum Zitat Yao Z, Wang X, Leonard D, Loguinov D Node isolation model and age-based neighbor selection in unstructured p2p networks. IEEE/ACM Trans Netw:17(1) Yao Z, Wang X, Leonard D, Loguinov D Node isolation model and age-based neighbor selection in unstructured p2p networks. IEEE/ACM Trans Netw:17(1)
Metadaten
Titel
Revisiting the coupon collector’s problem to unveil users’ online sessions in networked systems
verfasst von
Weverton Cordeiro
Luciano Gaspary
Rafael Beltran
Kayuã Paim
Rodrigo Mansilha
Publikationsdatum
13.11.2020
Verlag
Springer US
Erschienen in
Peer-to-Peer Networking and Applications / Ausgabe 2/2021
Print ISSN: 1936-6442
Elektronische ISSN: 1936-6450
DOI
https://doi.org/10.1007/s12083-020-01012-2

Weitere Artikel der Ausgabe 2/2021

Peer-to-Peer Networking and Applications 2/2021 Zur Ausgabe