NDLI: Toward continuous pattern detection over evolving large graph with snapshot isolation

Content Provider	Springer Nature Link
Author	Gao, Jun Zhou, Chang Yu, Jeffrey Xu
Copyright Year	2015
Abstract	This paper studies continuous pattern detection over large evolving graphs, which plays an important role in monitoring-related applications. The problem is challenging due to the large size and dynamic updates of graphs, the massive search space of pattern detection and inconsistent query results on dynamic graphs. This paper first introduces a snapshot isolation requirement, which ensures that the query results come from a consistent graph snapshot instead of a mixture of partial evolving graphs. Second, we propose an SSD (single sink directed acyclic graph) plan friendly to vertex-centric-distributed graph processing frameworks. SSD plan can guide the message transformation and transfer among graph vertices, and determine the satisfaction of the pattern on graph vertices for the sink vertex. Third, we devise strategies for major steps in the SSD evaluation, including the location of valid messages to achieve snapshot isolation, AO-List to determine the satisfaction of transition rule over dynamic graph, and message-on-change policy to reduce outgoing messages. The experiments on billion-edge graphs using Giraph, an open source implementation of Pregel, illustrate the efficiency and effectiveness of our method.
Starting Page	269
Ending Page	290
Page Count	22
File Format	PDF
ISSN	10668888
Journal	The VLDB Journal
Volume Number	25
Issue Number	2
e-ISSN	0949877X
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2015-12-09
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dynamic graph Pattern detection Graph streaming Snapshot solation Database Management
Content Type	Text
Resource Type	Article
Subject	Information Systems Hardware and Architecture

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

Extending DBMSs with satellite databases

Answering pattern match queries in large graph databases via graph embedding

Distributed snapshot isolation: global transactions pay globally, local transactions pay locally

Efficiently processing snapshot and continuous reverse k nearest neighbors queries

Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data

Path-based holistic detection plan for multiple patterns in distributed graph frameworks

Tashkent:uniting durability with transaction ordering for high-performance scalable database replication

Efficient subsequence matching over large video databases

Incremental k-core decomposition: algorithms and evaluation

Toward continuous pattern detection over evolving large graph with snapshot isolation

Similar Documents

Extending DBMSs with satellite databases

Answering pattern match queries in large graph databases via graph embedding

Distributed snapshot isolation: global transactions pay globally, local transactions pay locally

Efficiently processing snapshot and continuous reverse k nearest neighbors queries

Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data

Path-based holistic detection plan for multiple patterns in distributed graph frameworks

Tashkent:uniting durability with transaction ordering for high-performance scalable database replication

Efficient subsequence matching over large video databases

Incremental k-core decomposition: algorithms and evaluation

Toward continuous pattern detection over evolving large graph with snapshot isolation