We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Computing weight constraint reachability in large networks.
- Authors
Qiao, Miao; Cheng, Hong; Qin, Lu; Yu, Jeffrey; Yu, Philip; Chang, Lijun
- Abstract
Reachability is a fundamental problem on large-scale networks emerging nowadays in various application domains, such as social networks, communication networks, biological networks, road networks, etc. It has been studied extensively. However, little existing work has studied reachability with realistic constraints imposed on graphs with real-valued edge or node weights. In fact, such weights are very common in many real-world networks, for example, the bandwidth of a link in communication networks, the reliability of an interaction between two proteins in PPI networks, and the handling capacity of a warehouse/storage point in a distribution network. In this paper, we formalize a new yet important reachability query in weighted undirected graphs, called weight constraint reachability ( WCR) query that asks: is there a path between nodes $$a$$ and $$b$$, on which each real-valued edge (or node) weight satisfies a range constraint. We discover an interesting property of WCR, based on which, we design a novel edge-based index structure to answer the WCR query in $$O(1)$$ time. Furthermore, we consider the case when the index cannot entirely fit in the memory, which can be very common for emerging massive networks. An I/O-efficient index is proposed, which provides constant I/O (precisely four I/Os) query time with $$O(|V|\log |V|)$$ disk-based index size. Extensive experimental studies on both real and synthetic datasets demonstrate the efficiency and scalability of our solutions in answering the WCR query.
- Subjects
DIGITAL communications; SOCIAL networks; SYSTEMS design; SOCIAL groups; DATA transmission systems
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2013, Vol 22, Issue 3, p275
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-012-0288-4