{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T23:00:51Z","timestamp":1762210851027},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T00:00:00Z","timestamp":1451520000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10115-015-0908-6","type":"journal-article","created":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T10:59:42Z","timestamp":1451559582000},"page":"553-595","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Compressed $$\\text {k}\\mathsf {^d}\\text {-tree}$$ k d -tree for temporal graphs"],"prefix":"10.1007","volume":"49","author":[{"given":"Diego","family":"Caro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Andrea","family":"Rodr\u00edguez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nieves R.","family":"Brisaboa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Fari\u00f1a","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,31]]},"reference":[{"key":"908_CR1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert R, Barab\u00e1si A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74:47\u201397","journal-title":"Rev Mod Phys"},{"issue":"3","key":"908_CR2","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.3390\/a2031031","volume":"2","author":"A Apostolico","year":"2009","unstructured":"Apostolico A, Drovandi G (2009) Graph compression by BFS. Algorithms 2(3):1031\u20131044","journal-title":"Algorithms"},{"key":"908_CR3","unstructured":"\u00c1lvarez-Garc\u00eda S, Brisaboa NR, Fern\u00e1ndez JD, Mart\u00ednez-Prieto MA (2011) Compressed k2-triples for full-in-memory rdf engines. In: Proceedings of the Americas conference on information systems (AMCIS). Association for Information Systems"},{"key":"908_CR4","doi-asserted-by":"crossref","unstructured":"Aluru S, Sevilgen FE (1999) Dynamic compressed hypertoctrees with application to the N-body problem. In: Proceedings of the 19th conference on foundations of software technology and theoretical computer science. Springer, Berlin","DOI":"10.1007\/3-540-46691-6_2"},{"key":"908_CR5","doi-asserted-by":"crossref","unstructured":"Brisaboa NR, Caro D, Fari\u00f1a A, Rodr\u00edguez A (2014) A compressed suffix-array strategy for temporal-graph indexing. In: Moura E, Crochemore M (eds) String processing and information retrieval. Lecture notes in computer science. Springer International Publishing, pp 77\u201388","DOI":"10.1007\/978-3-319-11918-2_8"},{"key":"908_CR6","doi-asserted-by":"crossref","unstructured":"Brisaboa NR, de Bernardo G, Navarro G (2012) Compressed dynamic binary relations. In: Data compression conference (DCC). IEEE Computer Society, pp 52\u201361","DOI":"10.1109\/DCC.2012.13"},{"issue":"4","key":"908_CR7","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit D, Demaine ED, Ian Munro J, Raman R, Raman V, Srinivasa Rao S (2005) Representing trees of higher degree. Algorithmica 43(4):275\u2013292","journal-title":"Algorithmica"},{"key":"908_CR8","doi-asserted-by":"crossref","unstructured":"Brisaboa NR, Ladra S, Navarro G (2009) k2-trees for compact web graph representation. In: International symposium on string processing and information retrieval (SPIRE), vol 5721 of lecture notes in computer science. Springer, Berlin, pp 18\u201330","DOI":"10.1007\/978-3-642-03784-9_3"},{"issue":"1","key":"908_CR9","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","volume":"49","author":"NR Brisaboa","year":"2013","unstructured":"Brisaboa NR, Ladra S, Navarro G (2013) DACs: bringing direct access to variable-length codes. Inf Process Manag 49(1):392\u2013404","journal-title":"Inf Process Manag"},{"key":"908_CR10","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","volume":"39","author":"NR Brisaboa","year":"2014","unstructured":"Brisaboa NR, Ladra S, Navarro G (2014) Compact representation of web graphs with extended functionality. Inf Syst 39:152\u2013174","journal-title":"Inf Syst"},{"issue":"5","key":"908_CR11","doi-asserted-by":"crossref","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A Brodnik","year":"1999","unstructured":"Brodnik A, Ian Munro J (1999) Membership in constant time and almost-minimum space. SIAM J Comput 28(5):1627\u20131640","journal-title":"SIAM J Comput"},{"key":"908_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.is.2015.02.002","volume":"51","author":"D Caro","year":"2015","unstructured":"Caro D, Rodr\u00edguez MA, Brisaboa NR (2015) Data structures for temporal graphs based on compact sequence representations. Inf Syst 51:1\u201326","journal-title":"Inf Syst"},{"key":"908_CR13","doi-asserted-by":"crossref","unstructured":"Clarkson KL (1983) Fast algorithms for the all nearest neighbors problem. In: Proceedings of the 24th annual symposium on foundations of computer science (sfcs 1983). IEEE, pp 226\u2013232","DOI":"10.1109\/SFCS.1983.16"},{"key":"908_CR14","doi-asserted-by":"crossref","unstructured":"Cha M, Mislove A, Gummadi PK (2009) A measurement-driven analysis of information propagation in the flickr social network. In: International world wide web conference (WWW). ACM, pp 721\u2013730","DOI":"10.1145\/1526709.1526806"},{"key":"908_CR15","doi-asserted-by":"crossref","unstructured":"Claude F, Navarro G (2008) Practical rank\/select queries over arbitrary sequences. In: International symposium on string processing and information retrieval (SPIRE), vol 5280 of lecture notes in computer science. Springer, pp 176\u2013187","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"908_CR16","doi-asserted-by":"crossref","unstructured":"de Bernardo G, \u00c1lvarez-Garc\u00eda S, Brisaboa NR, Navarro G, Pedreira O (2013) Compact querieable representations of raster data. In: International symposium on string processing and information retrieval (SPIRE), vol 8214 of lecture notes in computer science. Springer, pp 96\u2013108","DOI":"10.1007\/978-3-319-02432-5_14"},{"key":"908_CR17","doi-asserted-by":"crossref","unstructured":"de Bernardo G, Brisaboa NR, Caro D, Rodr\u00edguez MA (2013) Compact data structures for temporal graphs. In: Data compression conference (DCC). IEEE, p 477","DOI":"10.1109\/DCC.2013.59"},{"key":"908_CR18","unstructured":"de Bernardo Roca G (2014) New data structures and algorithms for the efficient managementof large spatial datasets. PhD thesis, Universidade da Coru\u00f1a"},{"key":"908_CR19","unstructured":"Demetrescu C, Eppstein D, Galil Z, Italiano GF (2010) Algorithms and theory of computation handbook, chapter dynamic graph algorithms. Chapman & Hall\/CRC, pp 9-1\u20139-27"},{"key":"908_CR20","doi-asserted-by":"crossref","unstructured":"Eppstein D, Goodrich MT, Sun JZ (2005) The skip quadtree: a simple dynamic data structure for multidimensional data. In: SCG \u201905: proceedings of the twenty-first annual symposium on computational geometry. ACM Request Permissions","DOI":"10.1145\/1064092.1064138"},{"issue":"1","key":"908_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2094072.2094073","volume":"30","author":"A Fari\u00f1a","year":"2012","unstructured":"Fari\u00f1a A, Brisaboa N, Navarro G, Claude F, Places A, Rodr\u00edguez E (2012) Word-based self-indexes for natural language text. ACM TOIS 30(1):1","journal-title":"ACM TOIS"},{"key":"908_CR22","unstructured":"Ferreira A, Viennot L (2002) A note on models, algorithms, and data structures for dynamic communication networks. Technical Report RR-4403, INRIA"},{"key":"908_CR23","doi-asserted-by":"crossref","unstructured":"Gargantini I (1982) An effective way to represent quadtrees. In: Communications of the ACM, pp 1\u20136","DOI":"10.1145\/358728.358741"},{"key":"908_CR24","unstructured":"Garcia SA (2014) Compact and Efficient Representations of Graphs. PhD thesis, Universidade da Coru\u00f1a"},{"key":"908_CR25","doi-asserted-by":"crossref","unstructured":"Garcia SA, Brisaboa NR, de Bernardo G, Navarro G (2014) Interleaved K2-tree: indexing and navigating ternary relations. In: 2014 data compression conference (DCC). IEEE, pp 342\u2013351","DOI":"10.1109\/DCC.2014.56"},{"key":"908_CR26","doi-asserted-by":"crossref","unstructured":"Gog S, Beller T, Moffat A, Petri M (2014) From theory to practice: plug and play with succinct data structures. In: Proceedings of the 13th international symposium on experimental algorithms, (SEA 2014), pp 326\u2013337","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"908_CR27","unstructured":"Grossi R, Gupta A, Vitter JS (2003) High-order entropy-compressed text indexes. In: Proceedings of the annual ACM-SIAM symposium on discrete algorithms (SODA). ACM\/SIAM, pp 841\u2013850"},{"issue":"3","key":"908_CR28","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saram\u00e4ki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"908_CR29","unstructured":"Hudson B (2009) Succinct representation of well-spaced point clouds. Technical Report. arXiv:0909.3137"},{"key":"908_CR30","doi-asserted-by":"crossref","unstructured":"Jacobson G (1989) Space-efficient static trees and graphs. In: Proceedings of the 30th annual symposium on foundations of computer science (FOCS). IEEE Computer Society, pp 549\u2013554","DOI":"10.1109\/SFCS.1989.63533"},{"key":"908_CR31","doi-asserted-by":"crossref","unstructured":"Khurana U, Deshpande A (2013) Efficient snapshot retrieval over historical graph data. In: International conference on data engineering (ICDE). IEEE Computer Society, pp 997\u20131008","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"908_CR32","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd international conference on world wide web companion, WWW \u201913 Companion, pp 1343\u20131350, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee","DOI":"10.1145\/2487788.2488173"},{"key":"908_CR33","doi-asserted-by":"crossref","unstructured":"Labouseur AG, Birnbaum J, Olsen PW, Spillane SR, Vijayan J, Hwang J-H, Han W-S (2014) The G* graph database: efficiently managing large distributed dynamic graphs. Distrib Parallel Databases","DOI":"10.1007\/s10619-014-7140-3"},{"issue":"3","key":"908_CR34","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0734-189X(84)90215-9","volume":"26","author":"T Matsuyama","year":"1984","unstructured":"Matsuyama T, Hao LV, Nagao M (1984) A file organization for geographic information systems based on spatial proximity. Comput Vis Graph Image Process 26(3):303\u2013318","journal-title":"Comput Vis Graph Image Process"},{"key":"908_CR35","doi-asserted-by":"crossref","unstructured":"Nicosia V, Tang J, Mascolo C, Musolesi M, Russo G, Latora V (2013) Graph metrics for temporal networks. In: Temporal networks, understanding complex systems. Springer Berlin Heidelberg, pp 15\u201340","DOI":"10.1007\/978-3-642-36461-7_2"},{"key":"908_CR36","doi-asserted-by":"crossref","unstructured":"Pagh R (1999) Low redundancy in static dictionaries with O(1) worst case lookup time. In: ICAL \u201999: proceedings of the 26th international colloquium on automata, languages and programming. Springer, Berlin","DOI":"10.1007\/3-540-48523-6_56"},{"issue":"11","key":"908_CR37","doi-asserted-by":"crossref","first-page":"726","DOI":"10.14778\/3402707.3402713","volume":"4","author":"C Ren","year":"2011","unstructured":"Ren C, Lo E, Kao B, Zhu X, Cheng R (2011) On querying historical evolving graph sequences. Proc VLDB Endow (PVLDB) 4(11):726\u2013737","journal-title":"Proc VLDB Endow (PVLDB)"},{"key":"908_CR38","unstructured":"Raman R, Raman V, Srinivasa Rao S (2002) Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proceedings SODA\u201912, pp 233\u2013242"},{"issue":"2","key":"908_CR39","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K Sadakane","year":"2003","unstructured":"Sadakane K (2003) New text indexing functionalities of the compressed suffix arrays. J Algorithms 48(2):294\u2013313","journal-title":"J Algorithms"},{"key":"908_CR40","volume-title":"Foundations of multidimensional and metric data structures","author":"H Samet","year":"2006","unstructured":"Samet H (2006) Foundations of multidimensional and metric data structures. Morgan Kaufmann, Burlington, MA"},{"issue":"02","key":"908_CR41","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"BB Xuan","year":"2003","unstructured":"Xuan BB, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(02):267\u2013285","journal-title":"Int J Found Comput Sci"},{"key":"908_CR42","unstructured":"Yahoo! Labs (2014) Yahoo! network flows data, version 1.0. http:\/\/webscope.sandbox.yahoo.com\/catalog.php?datatype=g"},{"key":"908_CR43","doi-asserted-by":"crossref","unstructured":"Zukowski M, H\u00e9man S, Nes N, Boncz PA (2006) Super-scalar ram-cpu cache compression. In: Proceedings ICDE\u201906, p 59","DOI":"10.1109\/ICDE.2006.150"},{"key":"908_CR44","doi-asserted-by":"crossref","unstructured":"Zhang J, Long X, Suel T (2008) Performance of compressed inverted list caching in search engines. In: Proceedings WWW\u201908, pp 387\u2013396","DOI":"10.1145\/1367497.1367550"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-015-0908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-015-0908-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-015-0908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-015-0908-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,13]],"date-time":"2020-09-13T11:36:19Z","timestamp":1599996979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-015-0908-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,31]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["908"],"URL":"https:\/\/doi.org\/10.1007\/s10115-015-0908-6","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,31]]}}}