Research Article
BibTex RIS Cite
Year 2022, Volume: 5 Issue: 4, 240 - 244, 01.12.2022
https://doi.org/10.33401/fujma.1091736

Abstract

References

  • [1] M. X. Punithan, S. Seo, King’s graph-based neighbor-vehicle mapping framework, IEEE trans Intell Transp Syst, 14 (2013), 1313–1330.
  • [2] O. Favaron, G. H. Fricke, D. Pritikin, J. Puech, Irredundance and domination in kings graphs, Discrete Math. Elsevier, 262 (2003), 131–147 .
  • [3] E. J. Ionascu, D. Pritikin, S. E. Wright, k-Dependence and domination in kings graphs, Amer. Math. Monthly, 115 (2008), 820–836.
  • [4] R. Dantas, F. Havet, R. M. Sampaio, Minimum density of identifying codes of king grids, Discrete Math., 341 (2018), 2708–2719.
  • [5] G. C. Kayaturan, Representing Shortest Paths in Graphs Using Bloom Filters without False Positives and Applications to Routing in Computer Networks, Ph.D thesis, Univeristy of Essex, UK, 2018.
  • [6] B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Commun. ACM, 13 (1970), 422–426.
  • [7] Y. Lu, B. Prabhakar, F. Bonomi, Perfect hashing for network applications, IEEE Int. Symp. Inf. Theory - Proc., (2006), 2774–2778.
  • [8] C. E. Rothenberg, C. Macapuna, B. Alberto, M. F. Magalh˜aes, F. L. Verdi, A. Wiesmaier, In-packet Bloom filters: Design and networking applications, Comput. Netw., Elsevier, 55 (2011), 1364–1378.
  • [9] X. Yang, A. Vernitski, L. Carrea, An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters, Eur. J. Oper. Res. 252 (2016), 985–994.
  • [10] A. Saha, N. Sengupta, M. Ramanath, Reachability in large graphs using bloom filters, Proceedings - 2019 IEEE Trans Knowl Data Eng, ICDEW 2019, (2019), 217–224.
  • [11] M. Mitzenmacher, Compressed bloom filters, IEEE ACM Trans Netw., 10 (2002), 604–612.
  • [12] A. Broder, M. Mitzenmacher, Network applications of bloom filters: A survey, Internet Math., Taylor & Francis , 1 (2004), 485–509.
  • [13] L. Carrea, A. Vernitski, M. Reed, Optimized hash for network path encoding with minimized false positives, Comput. Netw., 58 (2014), 180–191.
  • [14] G. C. Kayaturan, A. Vernitski, A Way of eliminating errors when using Bloom filters for routing in computer networks, Comput. Electr. Eng. (CEEC), 2016 8th, (2016), 95–100.
  • [15] G. C. Kayaturan, A. Vernitski, Routing in hexagonal computer networks: How to present paths by Bloom filters without false positives, Netw., ICN2016. , (2016), 52–57.
  • [16] G. C. Kayaturan, A. Vernitski, Encoding shortest paths in triangular grids for delivery without errors, Proceedings - ICFNDS, (2017), 7.
  • [17] S. Tarkoma, C. E. Rothenberg, E. Lagerspetz, Theory and practice of bloom filters for distributed systems, IEEE Commun. Surv. Tutor., 14, (2012), 131–155.

Error Elimination From Bloom Filters in Computer Networks Represented by Graphs

Year 2022, Volume: 5 Issue: 4, 240 - 244, 01.12.2022
https://doi.org/10.33401/fujma.1091736

Abstract

An undirected mathematical graph, $G = (V, E)$ where $V$ is a set of vertices and $E = V \times V$ is the set of edges, can model a computer network. By this consideration we search for solutions to real computer network problems with a theoretical approach. This approach is based on labelling each edge by a subset of a universal set, and then encoding a path as the union of the labels of its edges. We label each vertex $v \in V$ by using a subset of universal set $U$, then we present a way to encode shortest paths in the graph $G$ by using a way optimizing the data. By mathematical approach, it is provable that the labelling method we introduced eliminates the errors from the shortest paths in the graph. We aim to obtain the results in a more efficient use of network resources and to reduce network traffic. This shows how our theoretical approach works in real world network systems.

References

  • [1] M. X. Punithan, S. Seo, King’s graph-based neighbor-vehicle mapping framework, IEEE trans Intell Transp Syst, 14 (2013), 1313–1330.
  • [2] O. Favaron, G. H. Fricke, D. Pritikin, J. Puech, Irredundance and domination in kings graphs, Discrete Math. Elsevier, 262 (2003), 131–147 .
  • [3] E. J. Ionascu, D. Pritikin, S. E. Wright, k-Dependence and domination in kings graphs, Amer. Math. Monthly, 115 (2008), 820–836.
  • [4] R. Dantas, F. Havet, R. M. Sampaio, Minimum density of identifying codes of king grids, Discrete Math., 341 (2018), 2708–2719.
  • [5] G. C. Kayaturan, Representing Shortest Paths in Graphs Using Bloom Filters without False Positives and Applications to Routing in Computer Networks, Ph.D thesis, Univeristy of Essex, UK, 2018.
  • [6] B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Commun. ACM, 13 (1970), 422–426.
  • [7] Y. Lu, B. Prabhakar, F. Bonomi, Perfect hashing for network applications, IEEE Int. Symp. Inf. Theory - Proc., (2006), 2774–2778.
  • [8] C. E. Rothenberg, C. Macapuna, B. Alberto, M. F. Magalh˜aes, F. L. Verdi, A. Wiesmaier, In-packet Bloom filters: Design and networking applications, Comput. Netw., Elsevier, 55 (2011), 1364–1378.
  • [9] X. Yang, A. Vernitski, L. Carrea, An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters, Eur. J. Oper. Res. 252 (2016), 985–994.
  • [10] A. Saha, N. Sengupta, M. Ramanath, Reachability in large graphs using bloom filters, Proceedings - 2019 IEEE Trans Knowl Data Eng, ICDEW 2019, (2019), 217–224.
  • [11] M. Mitzenmacher, Compressed bloom filters, IEEE ACM Trans Netw., 10 (2002), 604–612.
  • [12] A. Broder, M. Mitzenmacher, Network applications of bloom filters: A survey, Internet Math., Taylor & Francis , 1 (2004), 485–509.
  • [13] L. Carrea, A. Vernitski, M. Reed, Optimized hash for network path encoding with minimized false positives, Comput. Netw., 58 (2014), 180–191.
  • [14] G. C. Kayaturan, A. Vernitski, A Way of eliminating errors when using Bloom filters for routing in computer networks, Comput. Electr. Eng. (CEEC), 2016 8th, (2016), 95–100.
  • [15] G. C. Kayaturan, A. Vernitski, Routing in hexagonal computer networks: How to present paths by Bloom filters without false positives, Netw., ICN2016. , (2016), 52–57.
  • [16] G. C. Kayaturan, A. Vernitski, Encoding shortest paths in triangular grids for delivery without errors, Proceedings - ICFNDS, (2017), 7.
  • [17] S. Tarkoma, C. E. Rothenberg, E. Lagerspetz, Theory and practice of bloom filters for distributed systems, IEEE Commun. Surv. Tutor., 14, (2012), 131–155.
There are 17 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Gokce Caylak Kayaturan 0000-0001-6823-7686

Publication Date December 1, 2022
Submission Date March 22, 2022
Acceptance Date October 14, 2022
Published in Issue Year 2022 Volume: 5 Issue: 4

Cite

APA Caylak Kayaturan, G. (2022). Error Elimination From Bloom Filters in Computer Networks Represented by Graphs. Fundamental Journal of Mathematics and Applications, 5(4), 240-244. https://doi.org/10.33401/fujma.1091736
AMA Caylak Kayaturan G. Error Elimination From Bloom Filters in Computer Networks Represented by Graphs. Fundam. J. Math. Appl. December 2022;5(4):240-244. doi:10.33401/fujma.1091736
Chicago Caylak Kayaturan, Gokce. “Error Elimination From Bloom Filters in Computer Networks Represented by Graphs”. Fundamental Journal of Mathematics and Applications 5, no. 4 (December 2022): 240-44. https://doi.org/10.33401/fujma.1091736.
EndNote Caylak Kayaturan G (December 1, 2022) Error Elimination From Bloom Filters in Computer Networks Represented by Graphs. Fundamental Journal of Mathematics and Applications 5 4 240–244.
IEEE G. Caylak Kayaturan, “Error Elimination From Bloom Filters in Computer Networks Represented by Graphs”, Fundam. J. Math. Appl., vol. 5, no. 4, pp. 240–244, 2022, doi: 10.33401/fujma.1091736.
ISNAD Caylak Kayaturan, Gokce. “Error Elimination From Bloom Filters in Computer Networks Represented by Graphs”. Fundamental Journal of Mathematics and Applications 5/4 (December 2022), 240-244. https://doi.org/10.33401/fujma.1091736.
JAMA Caylak Kayaturan G. Error Elimination From Bloom Filters in Computer Networks Represented by Graphs. Fundam. J. Math. Appl. 2022;5:240–244.
MLA Caylak Kayaturan, Gokce. “Error Elimination From Bloom Filters in Computer Networks Represented by Graphs”. Fundamental Journal of Mathematics and Applications, vol. 5, no. 4, 2022, pp. 240-4, doi:10.33401/fujma.1091736.
Vancouver Caylak Kayaturan G. Error Elimination From Bloom Filters in Computer Networks Represented by Graphs. Fundam. J. Math. Appl. 2022;5(4):240-4.

Creative Commons License
The published articles in Fundamental Journal of Mathematics and Applications are licensed under a