NDLI: Compact Data Structures for Temporal Graphs

Content Provider	IEEE Xplore Digital Library
Author	Bernardo, G.D. Brisaboa, N.R. Caro, D. Rodriguez, M.A.
Copyright Year	2013
Abstract	Summary form only given. In this paper we propose three compact data structures to answer queries on temporal graphs. We define a temporal graph as a graph whose edges appear or disappear along time. Possible queries are related to adjacency along time, for example, to get the neighbors of a node at a given time point or interval. A naive representation consists of a time-ordered sequence of graphs, each of them valid at a particular time instant. The main issue of this representation is the unnecessary use of space if many nodes and their connections remain unchanged during a long period of time. The work in this paper proposes to store only what changes at each time instant. The $ttk^{2}-tree$ is conceptually a dynamic $k^{2}-tree$ in which each leaf and internal node contains a change list of time instants when its bit value has changed. All the change lists are stored consecutively in a dynamic sequence. During query processing, the change lists are used to expand only valid regions in the dynamic $k^{2}-tree.$ It supports updates of the current or past states of the graph. The ltg-index is a set of snapshots and logs of changes between consecutive snapshots. The structure keeps a log for each node, storing the edge and the time where a change has been produced. To retrieve direct neighbors of a node, the previous snapshot is queried, and then the log is traversed adding or removing edges to the result. The differential $k^{2}-tree$ stores snapshots of some time instants in $k^{2}-trees.$ For the other time instants, a $k^{2}-tree$ is also built, but these are differential (they store the edges that differ from the last snapshot). To perform a query it accesses the k2-tree of the given time and the previous full snapshot. The edges that appear in exactly one of these two $k^{2}-trees$ will be the final results. We test our proposals using synthetic and real datasets. Our results show that the ltg-index obtains the smallest space in general. We also measure times for direct and reverse neighbor queries in a time instant or a time interval. For all these queries, the times of our best proposal range from tens of μs to several ms, depending on the size of the dataset and the number of results returned. The ltg-index is the fastest for direct queries (almost as fast as accessing a snapshot), but it is 5-20 times slower in reverse queries. The differential $k^{2}-tree$ is very fast in time instant queries, but slower in time interval queries. The $ttk^{2}-tree$ obtains similar times for direct and reverse queries and different time intervals, being the fastest in some reverse interval queries. It has also the advantage of being dynamic.
Sponsorship	Univ. Arizona
Starting Page	477
Ending Page	477
File Size	489614
Page Count	1
File Format	PDF
ISBN	9781467360371
ISSN	10680314
e-ISBN	9780769549651
DOI	10.1109/DCC.2013.59
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-03-20
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Data structures Educational institutions Proposals Data compression Query processing Time measurement IEEE Computer Society
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Interleaved K2-Tree: Indexing and Navigating Ternary Relations

NRMI: natural and efficient middleware

Faster Compressed Top-k Document Retrieval

Universal Text Preprocessing and Postprocessing for PPM Using Alphabet Adjustment

Efficient lossless compression of trees and graphs

Algorithms for Compressed Inputs

VLSI algorithms for compressed pattern search using tree based codes

Simple Linear-Time Off-Line Text Compression by Longest-First Substitution

Faster Compact Top-k Document Retrieval

Compact Data Structures for Temporal Graphs

Similar Documents

Interleaved K2-Tree: Indexing and Navigating Ternary Relations

NRMI: natural and efficient middleware

Faster Compressed Top-k Document Retrieval

Universal Text Preprocessing and Postprocessing for PPM Using Alphabet Adjustment

Efficient lossless compression of trees and graphs

Algorithms for Compressed Inputs

VLSI algorithms for compressed pattern search using tree based codes

Simple Linear-Time Off-Line Text Compression by Longest-First Substitution

Faster Compact Top-k Document Retrieval

Compact Data Structures for Temporal Graphs