Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Knowledge and Information Systems
Erschienen in: Knowledge and Information Systems 2/2016

01.11.2016 | Regular Paper

Compressed \(\text {k}\mathsf {^d}\text {-tree}\) for temporal graphs

verfasst von: Diego Caro, M. Andrea Rodríguez, Nieves R. Brisaboa, Antonio Fariña

Erschienen in: Knowledge and Information Systems | Ausgabe 2/2016

Einloggen

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

search-config
loading …

Abstract

Temporal graphs represent vertices and binary relations that change along time. The work in this paper proposes to represent temporal graphs as cells in a 4D binary matrix: two dimensions to represent extreme vertices of an edge and two dimensions to represent the temporal interval when the edge exists. This strategy generalizes the idea of the adjacency matrix for storing static graphs. The proposed structure called Compressed \(\text {k}\mathsf {^d}\text {-tree}\) (\(\text {ck}\mathsf {^d}\text {-tree}\)) is capable of dealing with unclustered data with a good use of space. The \(\text {ck}\mathsf {^d}\text {-tree}\) uses asymptotically the same space than the (worst case) lower bound for storing cells in a 4D binary matrix, without considering any regularity. Techniques that group leaves into buckets and compress nodes with few children show to improve the performance in time and space. An experimental evaluation compares the \(\text {ck}\mathsf {^d}\text {-tree}\) with \(\text {k}\mathsf {^d}\text {-tree}\) (the d-dimensional extension of the \(\text {k}\mathsf {^2}\text {-tree}\)) and with other up-to-date compressed data structures based on inverted indexes and \(\mathsf {Wavelet}\text { Tree}\)s, showing the potential use of the \(\text {ck}\mathsf {^d}\text {-tree}\) for different types of temporal graphs.
Vorheriger Artikel Approximating behavioral equivalence for scaling solutions of I-DIDs
Nächster Artikel On efficiently mining high utility sequential patterns

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
We use the term time instant and time point indistinctly.
 
2
Holme and Saramäki defined this as a contact sequence, but we renamed the concept to point-contact temporal contact.
 
3
We assume that the boundary is closed at the upper-left corner and open at the lower-right corner.
 
4
Other orders have been proposed, but they do not make any improvement on the space or the navigation time [18].
 
5
When the input is small, the sorting method is faster than creating a hash table to remove duplicated items.
 
11
The structures were implemented by Susana Ladra (\(\text {k}\mathsf {^2}\text {-tree}\)), Guillermo de Bernardo and Sandra Álvarez (\(\text {ik}\mathsf {^2}\text {-tree}\)).
 
12
In this section, we will use B with a suffix to denote the size of the bucket in the \(\text {bck}\mathsf {^d}\text {-tree}\) and b (without a suffix) to denote the block size in bitmaps.
 
13
The program used to create the structures failed when the lifetime of the graph is greater than 10,000 instants.
 
Literatur
1.
2.
3.
Álvarez-García S, Brisaboa NR, Fernández JD, Martínez-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
4.
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
5.
Brisaboa NR, Caro D, Fariña A, Rodríguez 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–88
6.
Brisaboa NR, de Bernardo G, Navarro G (2012) Compressed dynamic binary relations. In: Data compression conference (DCC). IEEE Computer Society, pp 52–61
7.
Benoit D, Demaine ED, Ian Munro J, Raman R, Raman V, Srinivasa Rao S (2005) Representing trees of higher degree. Algorithmica 43(4):275–292MathSciNetCrossRefMATH
8.
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–30
9.
Brisaboa NR, Ladra S, Navarro G (2013) DACs: bringing direct access to variable-length codes. Inf Process Manag 49(1):392–404CrossRef
10.
Brisaboa NR, Ladra S, Navarro G (2014) Compact representation of web graphs with extended functionality. Inf Syst 39:152–174CrossRef
11.
12.
Caro D, Rodríguez MA, Brisaboa NR (2015) Data structures for temporal graphs based on compact sequence representations. Inf Syst 51:1–26CrossRef
13.
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–232
14.
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–730
15.
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–187
16.
de Bernardo G, Álvarez-García 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–108
17.
de Bernardo G, Brisaboa NR, Caro D, Rodríguez MA (2013) Compact data structures for temporal graphs. In: Data compression conference (DCC). IEEE, p 477
18.
de Bernardo Roca G (2014) New data structures and algorithms for the efficient managementof large spatial datasets. PhD thesis, Universidade da Coruña
19.
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–9-27
20.
Eppstein D, Goodrich MT, Sun JZ (2005) The skip quadtree: a simple dynamic data structure for multidimensional data. In: SCG ’05: proceedings of the twenty-first annual symposium on computational geometry. ACM Request Permissions
21.
Fariña A, Brisaboa N, Navarro G, Claude F, Places A, Rodríguez E (2012) Word-based self-indexes for natural language text. ACM TOIS 30(1):1CrossRef
22.
Ferreira A, Viennot L (2002) A note on models, algorithms, and data structures for dynamic communication networks. Technical Report RR-4403, INRIA
23.
Gargantini I (1982) An effective way to represent quadtrees. In: Communications of the ACM, pp 1–6
24.
Garcia SA (2014) Compact and Efficient Representations of Graphs. PhD thesis, Universidade da Coruña
25.
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–351
26.
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–337
27.
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–850
28.
Holme P, Saramäki J (2012) Temporal networks. Phys Rep 519(3):97–125CrossRef
29.
30.
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–554
31.
Khurana U, Deshpande A (2013) Efficient snapshot retrieval over historical graph data. In: International conference on data engineering (ICDE). IEEE Computer Society, pp 997–1008
32.
Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd international conference on world wide web companion, WWW ’13 Companion, pp 1343–1350, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee
33.
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
34.
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–318CrossRef
35.
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–40
36.
Pagh R (1999) Low redundancy in static dictionaries with O(1) worst case lookup time. In: ICAL ’99: proceedings of the 26th international colloquium on automata, languages and programming. Springer, Berlin
37.
Ren C, Lo E, Kao B, Zhu X, Cheng R (2011) On querying historical evolving graph sequences. Proc VLDB Endow (PVLDB) 4(11):726–737
38.
Raman R, Raman V, Srinivasa Rao S (2002) Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proceedings SODA’12, pp 233–242
39.
40.
Samet H (2006) Foundations of multidimensional and metric data structures. Morgan Kaufmann, Burlington, MAMATH
41.
Xuan BB, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(02):267–285MathSciNetCrossRefMATH
42.
43.
Zukowski M, Héman S, Nes N, Boncz PA (2006) Super-scalar ram-cpu cache compression. In: Proceedings ICDE’06, p 59
44.
Zhang J, Long X, Suel T (2008) Performance of compressed inverted list caching in search engines. In: Proceedings WWW’08, pp 387–396
Metadaten
Titel
Compressed for temporal graphs
verfasst von
Diego Caro
M. Andrea Rodríguez
Nieves R. Brisaboa
Antonio Fariña
Publikationsdatum
01.11.2016
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 2/2016
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-015-0908-6

Weitere Artikel der Ausgabe 2/2016

Knowledge and Information Systems 2/2016 Zur Ausgabe

Regular Paper

Approximating behavioral equivalence for scaling solutions of I-DIDs

Regular Paper

Neighborhood system S-approximation spaces and applications

Regular Paper

A feature location approach supported by time-aware weighting of terms associated with developer expertise profiles

Regular Paper

Query intent inference via search engine log

Regular Paper

On efficiently mining high utility sequential patterns

Regular Paper

Improving a multi-objective evolutionary algorithm to discover quantitative association rules