Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks
122
0
0.0
(
0
)
Added by
Minhao Jiang
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of point-to-point distance querying for massive scale-free graphs, which is important for numerous applications. Given a directed or undirected graph, we propose to build an index for answering such queries based on a hop-doubling labeling technique. We derive bounds on the index size, the computation costs and I/O costs based on the properties of unweighted scale-free graphs. We show that our method is much more efficient compared to the state-of-the-art technique, in terms of both querying time and indexing time. Our empirical study shows that our method can handle graphs that are orders of magnitude larger than existing methods.
rate research
Read More
Many man-made networks support each other to provide efficient services and resources to the customers, despite that this support produces a strong interdependency between the individual networks. Thus an initial failure of a fraction $1-p$ of nodes in one network, exposes the system to cascade of failures and, as a consequence, to a full collapse of the overall system. Therefore it is important to develop efficient strategies to avoid the collapse by increasing the robustness of the individual networks against failures. Here, we provide an exact theoretical approach to study the evolution of the cascade of failures on interdependent networks when a fraction $alpha$ of the nodes with higher connectivity in each individual network are autonomous. With this pattern of interdependency we found, for pair of heterogeneous networks, two critical percolation thresholds that depend on $alpha$, separating three regimes with very different networks final sizes that converge into a triple point in the plane $p-alpha$. Our findings suggest that the heterogeneity of the networks represented by high degree nodes is the responsible of the rich phase diagrams found in this and other investigations.
The phenomenal growth of graph data from a wide variety of real-world applications has rendered graph querying to be a problem of paramount importance. Traditional techniques use structural as well as node similarities to find matches of a given query graph in a (large) target graph. However, almost all existing techniques have tacitly ignored the presence of relationships in graphs, which are usually encoded through interactions between node and edge labels. In this paper, we propose RAQ -- Relationship-Aware Graph Querying, to mitigate this gap. Given a query graph, RAQ identifies the $k$ best matching subgraphs of the target graph that encode similar relationships as in the query graph. To assess the utility of RAQ as a graph querying paradigm for knowledge discovery and exploration tasks, we perform a user survey on the Internet Movie Database (IMDb), where an overwhelming 86% of the 170 surveyed users preferred the relationship-aware match over traditional graph querying. The need to perform subgraph isomorphism renders RAQ NP-hard. The querying is made practical through beam stack search. Extensive experiments on multiple real-world graph datasets demonstrate RAQ to be effective, efficient, and scalable.
We aim to study the set of color sets of continuous regions of an image given as a matrix of $m$ rows over $ngeq m$ columns where each element in the matrix is an integer from $[1,sigma]$ named a {em color}. The set of distinct colors in a region is called fingerprint. We aim to compute, index and query the fingerprints of all rectangular regions named rectangles. The set of all such fingerprints is denoted by ${cal F}$. A rectangle is {em maximal} if it is not contained in a greater rectangle with the same fingerprint. The set of all locations of maximal rectangles is denoted by $mathcal{L}.$ We first explain how to determine all the $|mathcal{L}|$ maximal locations with their fingerprints in expected time $O(nm^2sigma)$ using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic $O(nm^2sigmalog(frac{|mathcal{L}|}{nm^2}+2))$ time. We then show how to build a data structure which occupies $O(nmlog n+mathcal{|L|})$ space such that a query which asks for all the maximal locations with a given fingerprint $f$ can be answered in time $O(|f|+loglog n+k)$, where $k$ is the number of maximal locations with fingerprint $f$. If the query asks only for the presence of the fingerprint, then the space usage becomes $O(nmlog n+|{cal F}|)$ while the query time becomes $O(|f|+loglog n)$. We eventually consider the special case of squared regions (squares).
Spatial Online Analytical Processing System involves the non-categorical attribute information also whereas standard Online Analytical Processing System deals with only categorical attributes. Providing spatial information to the data warehouse (DW); two major challenges faced are;1.Defining and Aggregation of Spatial/Continues values and 2.Representation, indexing, updating and efficient query processing. In this paper, we present GCUBE(Geographical Cube) storage and indexing procedure to aggregate the spatial information/Continuous values. We employed the proposed approach storing and indexing using synthetic and real data sets and evaluated its build, update and Query time. It is observed that the proposed procedure offers significant performance advantage.
Structural indexing is an approach to accelerating query evaluation, whereby data objects are partitioned and indexed reflecting the precise expressive power of a given query language. Each partition block of the index holds exactly those objects that are indistinguishable with respect to queries expressible in the language. Structural indexes have proven successful for XML, RDF, and relational data management. In this paper we study structural indexing for conjunctive path queries (CPQ). CPQ forms the core of contemporary graph query languages such as SPARQL, Cypher, PGQL, and G-CORE. CPQ plays the same fundamental role with respect to contemporary graph query languages as the classic conjunctive queries play for SQL. We develop the first practical structural indexes for this important query language. In particular, we propose a structural index based on k-path-bisimulation, tightly coupled to the expressive power of CPQ, and develop algorithms for efficient query processing with our index. Furthermore, we study workload-aware structural indexes to reduce both the construction and space costs according to a given workload. We demonstrate through extensive experiments using real and synthetic graphs that our methods accelerate query processing by up to multiple orders of magnitude over the state-of-the-art methods, without increasing index size.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
