{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T11:17:24Z","timestamp":1784373444355,"version":"3.55.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T00:00:00Z","timestamp":1640044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2022,5,31]]},"abstract":"<jats:p>Time-evolving web and social network graphs are modeled as a set of pages\/individuals (nodes) and their arcs (links\/relationships) that change over time. Due to their popularity, they have become increasingly massive in terms of their number of nodes, arcs, and lifetimes. However, these graphs are extremely sparse throughout their lifetimes. For example, it is estimated that Facebook has over a billion vertices, yet at any point in time, it has far less than 0.001% of all possible relationships. The space required to store these large sparse graphs may not fit in most main memories using underlying representations such as a series of adjacency matrices or adjacency lists.<\/jats:p>\n          <jats:p>We propose building a compressed data structure that has a compressed binary tree corresponding to each row of each adjacency matrix of the time-evolving graph. We do not explicitly construct the adjacency matrix, and our algorithms take the time-evolving arc list representation as input for its construction. Our compressed structure allows for directed and undirected graphs, faster arc and neighborhood queries, as well as the ability for arcs and frames to be added and removed directly from the compressed structure (streaming operations). We use publicly available network data sets such as Flickr, Yahoo!, and Wikipedia in our experiments and show that our new technique performs as well or better than our benchmarks on all datasets in terms of compression size and other vital metrics.<\/jats:p>","DOI":"10.1145\/3495012","type":"journal-article","created":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T19:47:39Z","timestamp":1640116059000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Queryable Compression on Time-evolving Web and Social Networks with Streaming"],"prefix":"10.1145","volume":"16","author":[{"given":"Michael","family":"Nelson","sequence":"first","affiliation":[{"name":"University of Oklahoma, Norman, OK, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sridhar","family":"Radhakrishnan","sequence":"additional","affiliation":[{"name":"University of Oklahoma, Norman, OK, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chandra","family":"Sekharan","sequence":"additional","affiliation":[{"name":"Loyola University of Chicago, Chicago, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amlan","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"California State University Dominguez Hills, Carson, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudhindra Gopal","family":"Krishna","sequence":"additional","affiliation":[{"name":"University of Oklahoma, Norman, OK, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,21]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"J\u00e9r\u00f4me Kunegis. KONECT \u2013 The Koblenz Network Collection. 2020. Point contact Wikipedia articles edited. http:\/\/konect.uni-koblenz.de\/."},{"key":"e_1_3_1_3_2","unstructured":"The Max Planck Institute for Software Systems. 2020. User-to-user link crawled on Flickr Social Network. http:\/\/socialnetworks.mpi-sws.org\/data-www2009.html."},{"key":"e_1_3_1_4_2","unstructured":"Yahoo! Research. 2020. Yahoo! Network Flows Data version 1.0. http:\/\/webscope.sandbox.yahoo.com\/catalog.php?datatype=g."},{"key":"e_1_3_1_5_2","first-page":"342","volume-title":"Data Compression Conference","author":"\u00c1lvarez-Garc\u00eda S.","year":"2014","unstructured":"S. \u00c1lvarez-Garc\u00eda, N. R. Brisaboa, G. D. Bernardo, and G. Navarro. 2014. Interleaved K2-Tree: Indexing and navigating ternary relations. In Data Compression Conference. 342\u2013351. DOI:https:\/\/doi.org\/10.1109\/DCC.2014.56"},{"key":"e_1_3_1_6_2","first-page":"477","volume-title":"Data Compression Conference","author":"Bernardo G. D.","year":"2013","unstructured":"G. D. Bernardo, N. R. Brisaboa, D. Caro, and M. A. Rodr\u00edguez. 2013. Compact data structures for temporal graphs. In Data Compression Conference. 477\u2013477. DOI:https:\/\/doi.org\/10.1109\/DCC.2013.59"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_1_8_2","volume-title":"International Symposium on String Processing and Information Retrieval","author":"Brisaboa Nieves R.","year":"2014","unstructured":"Nieves R. Brisaboa, Diego Caro, Antonio Fari\u00f1a, and M. Andrea Rodr\u00edguez. 2014. A compressed suffix-array strategy for temporal-graph indexing. In International Symposium on String Processing and Information Retrieval."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.08.003"},{"key":"e_1_3_1_10_2","volume-title":"SIAM J. Comput.","author":"Brodnik Andrej","year":"1999","unstructured":"Andrej Brodnik and J. Ian Munro. 1999. Membership in constant time and almost-minimum space. SIAM J. Comput. 28, 5 (1999). Society for Industrial and Applied Mathematics. DOI:https:\/\/doi.org\/10.1137\/S0097539795294165"},{"key":"e_1_3_1_11_2","volume-title":"Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks","author":"Bui-Xuan Binh-Minh","year":"2002","unstructured":"Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. 2002. Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks. Technical Report RR-4589. INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00071996."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.02.002"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0908-6"},{"key":"e_1_3_1_14_2","volume-title":"A Note on Models, Algorithms, and Data Structures for Dynamic Communication Networks","author":"Ferreira Afonso","year":"2002","unstructured":"Afonso Ferreira and Laurent Viennot. 2002. A Note on Models, Algorithms, and Data Structures for Dynamic Communication Networks. Research Report RR-4403. INRIA. Retrieved from https:\/\/hal.inria.fr\/inria-00072185."},{"key":"e_1_3_1_15_2","first-page":"841","volume-title":"14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Grossi Roberto","year":"2003","unstructured":"Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. In 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). Society for Industrial and Applied Mathematics, Philadelphia, PA, 841\u2013850. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=644108.644250."},{"key":"e_1_3_1_16_2","first-page":"997","article-title":"Efficient snapshot retrieval over historical graph data","author":"Khurana Udayan","year":"2013","unstructured":"Udayan Khurana and Amol Deshpande. 2013. Efficient snapshot retrieval over historical graph data. In IEEE 29th International Conference on Data Engineering (ICDE). 997\u20131008.","journal-title":"I"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-014-7140-3"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2779797"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662053"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258020"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622386"},{"key":"e_1_3_1_22_2","article-title":"Graph metrics for temporal networks","volume":"1306","author":"Nicosia Vincenzo","year":"2013","unstructured":"Vincenzo Nicosia, John Kit Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, and Vito Latora. 2013. Graph metrics for temporal networks. CoRR abs\/1306.0493 (2013).","journal-title":"CoRR"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402713"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495012","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3495012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:49:19Z","timestamp":1750193359000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,21]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,31]]}},"alternative-id":["10.1145\/3495012"],"URL":"https:\/\/doi.org\/10.1145\/3495012","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,21]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}