Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Graph similarity search on large uncertain graph databases
Yuan Y., Wang G., Chen L., Wang H. The VLDB Journal: The International Journal on Very Large Data Bases24 (2):271-296,2015.Type:Article
Date Reviewed: Mar 22 2016

Have you ever, as a developer, come across problems and algorithms involving searching for patterns in a graph database? Are you interested in network science, for example, social network analysis, planning and designing optimal telecommunications networks, or the analysis of time-series data for discovering interesting patterns?

This paper will provide you with the fundamentals of how you can query and search a graph. The authors contribute a study of similarity graph containment search on large uncertain graph databases. These are graphs where the edges are assigned probabilities. The paper is also an attempt to “formally prove that subgraph or supergraph similarity search over uncertain graphs is #P-hard,” which is certainly better than NL-completeness.

Despite this highly specialized focus on uncertain graphs, the paper will mostly interest new researchers addressing graph-based querying or matching, information retrieval, and similarity search, as it provides an excellent list of references. It also provides a wealth of formalisms and theorems, which may also guide new researchers in how to embed formalisms in their own papers.

From a broader educational point of view, some text passages and references can be used for teaching purposes in advanced master’s level courses related to algorithms and complexity, as well as to information retrieval and search.

Reviewer:  Epaminondas Kapetanios Review #: CR144249 (1606-0416)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Logical Design (H.2.1 )
 
 
Graphs And Networks (E.1 ... )
 
 
Graph Theory (G.2.2 )
 
 
Data Structures (E.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Logical Design": Date
Database analysis and design (2nd ed.)
Hawryszkiewycz I., Macmillan Press Ltd., Basingstoke, UK, 1991. Type: Book (9780023518515)
Jul 1 1993
The semantics of incomplete databases as an expression of preferences
Royer V. Theoretical Computer Science 78(1): 113-136, 1991. Type: Article
Mar 1 1992
A note on lossless database decompositions
Vardi M. Information Processing Letters 18(5): 257-260, 1984. Type: Article
Oct 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy