We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Using Treaps for Optimization of Graph Storage

by Dharya Arora, Shalini Batra
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 41 - Number 14
Year of Publication: 2012
Authors: Dharya Arora, Shalini Batra
10.5120/5612-7888

Dharya Arora, Shalini Batra . Using Treaps for Optimization of Graph Storage. International Journal of Computer Applications. 41, 14 ( March 2012), 41-44. DOI=10.5120/5612-7888

@article{ 10.5120/5612-7888,
author = { Dharya Arora, Shalini Batra },
title = { Using Treaps for Optimization of Graph Storage },
journal = { International Journal of Computer Applications },
issue_date = { March 2012 },
volume = { 41 },
number = { 14 },
month = { March },
year = { 2012 },
issn = { 0975-8887 },
pages = { 41-44 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume41/number14/5612-7888/ },
doi = { 10.5120/5612-7888 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:29:37.414898+05:30
%A Dharya Arora
%A Shalini Batra
%T Using Treaps for Optimization of Graph Storage
%J International Journal of Computer Applications
%@ 0975-8887
%V 41
%N 14
%P 41-44
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Adjacency matrix is an effective technique used to represent a graph or a Social network comprising of large number of vertices and edges. The intent is of this paper is to optimize the graph storage and mapping without using a large adjacency matrix to represent a large graph. A special data structure Treap, a combination of binary search tree and heaps has been used as a replacement to a large adjacency matrix. It has been experimentally evaluated that the proposed approach significantly improves the space occupied by adjacency matrix and helps the graph to grow dynamically without affecting the current data structure.

References
  1. J. B. Shearer and R. J. McEliece. 1977: "There is no Mac Williams identity for convolutional codes"; IEEE Trans. Inform. Theory, IT-23:775-776.
  2. Bernard Elspas and James Turner. 1970: "Graphs with circulant adjacency matrices", 297
  3. A. Cohen and V. Lefebvre. 1988: "Optimization of storage mappings for graphs" Technical Report 1998/46, PRiSM, U. of Versailles.
  4. H. Orsila, E. Salminen, M. H¨annik¨ainen, T. D. H¨am¨al¨ainen. 2007: "Optimal Subset Mapping And Convergence Evaluation of Mapping Algorithms for Distributing Task Graphs on Multiprocessor"; SoC, Symposium on SoC.
  5. Chris Lattner: "Heap Data Structure Analysis and Optimization ", Ph. D. Thesis
  6. R. W. Irving and L. Love. 2003: "The suffix binary search tree and suffix AVL tree"; J. Discrete Algorithms, 1(5-6):387-408.
  7. G. D. Forney and M. D. Trott. 2004: "The Dynamics of Group Codes: Dual Abelian Group Codes and Systems"; IEEE Trans. Inform. Theory, IT-50:2935-2965.
  8. A. A. Nanavati, S. Gurumurthy, G. Das, D. Chakraborty, K. Dasgupta, S. Mukherjee, A. Joshi. 2006: "On the structural properties of massive telecom call graphs: findings and implications"; In CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management, New York, NY, USA, ACM, 435–444
  9. M. Newman, A. -L. Barabasi, D. J. Watts. 2006: "The Structure and Dynamics of Networks"
  10. G. Pike. 2002; "Reordering and Storage Optimizations for graphs"; PhD thesis, University of California, Berkeley.
  11. Frank O. 1981; "A Survey of Statistical Methods for Graph Analysis. Sociological Methodology", 110-155.
  12. Brewer, D. D. , Webster, C. M. . 1999; "Forgetting of friends and its effects on measuring friendship networks. Social Networks" 21, 361–373.
  13. Pattison, P. E. , Robins, G. L. 2002; "Neighbourhood-based models for social networks. Sociological Methodology" 32, 301–337.
  14. Watts, D. J. 1999; "Small Worlds: The Dynamics of Networks between Order and Randomness"; Princeton University Press, Princeton, NJ.
  15. Handcock, M. S. , Hunter, D. R. , Butts, C. T. , Goodreau, S. M. , Morris, M. 2008. Statnet: "Software Tools for the Representation, Visualization, Analysis and Simulation of Network Data"; Journal of Statistical Software 24 (1), URL, http://www. jstatsoft. org/v24/i01.
  16. A. Cohen. 1999; "Parallelization via constrained storage mapping optimization";
  17. A. Cohen and V. Lefebvre. 1988; "Optimization of storage mappings for parallel programs"; Technical Report 1998/46, PRiSM, U. of Versailles.
  18. P. Feautrier. 2001; "The use of farkas lemma in memory optimization".
  19. A. W. Lim, S. -W. 2001; "Liao, and M. S. Lam. Blocking and array contraction across arbitrarily nested loops using affine partitioning"; In Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, pages 103-112, ACM Press.
  20. W. Thies, F. Vivien, J. Sheldon, and S. Amarasinghe. 2001; "A unified framework for schedule and storage optimization"; In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, pages 232-242, ACM Press.
  21. Blelloch, Guy E, Reid-Miller, Margaret, (1998), "Fast set operations using Treaps", Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, pp. 16–26.
  22. Martinez, Conrado, Roura, Salvador. 1997, "Randomized binary search trees", Journal of the ACM 45 (2): 288–323
  23. R. Seidel and C. R. Aragon. 1996; "Randomized search trees"; Algorithmica, 16:464-497.
  24. D. D. Sleator and R. E. Tarjan. 1985; "Self-adjusting binary trees"; Journal of the Association for Computing Machinery, 32(3):652-686.
Index Terms

Computer Science
Information Sciences

Keywords

Storage Optimization Graph Mapping Treap Data Structure Adjacency Matrix

Powered by PhDFocusTM