Answering reachability queries is a fundamental graph operation. Considering that the size of the input graph has a great impact on query performance, there are studies focusing on reducing the graph size, such that queries can be answered over a smaller graph. Although the input graph can be compressed significantly by existing approaches, a good compression ratio does not always mean a positive effect on query performance. In this paper, we study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to compress the input graph into a smaller one. Let a be the compression ratio of the number of nodes in the reduced graph over that of the input graph, we show that based on our approach, the lower bound probability that a query q can be answered in constant time is 1-a^2. We show the difficulties of RCN reduction and propose efficient algorithms to improve the compression ratio. Based on the result of RCN reduction, we further propose a novel labeling scheme to accelerate queries answering. We confirm the efficiency of our approach by extensive experimental results for graph reduction and reachability queries processing using 20 real datasets.

We study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to reduce the input graph$G$of$\vert V\vert$nodes into a smaller one with$\vert V^{r}\vert$nodes. Assume that the probability of a node of$G$to be a query node is$1/\vert V\vert$, we show that based on our approach, the lower bound probability that a query$q$can be answered in constant time is$1-(\frac{\vert V^{r}\vert}{\vert V\vert})^{2}$, denoting that the smaller the reduced graph, the larger the probability that$q$can be answered in constant time. We show the difficulties of RCN reduction and propose efficient algorithms to improve the reduction ratio. We confirm the benefits of our approach by rich experimental results using real datasets.

Recently, cross-modal hashing has attracted much attention due to its low storage cost and fast query speed. Mean Average Precision (MAP) is the most widely used performance measure for cross-modal hashing. However, we found that the MAP scores do not fully reflect the quality of the top-K results for cross-modal retrieval because it neglects multi-label information and overlooks the label semantic hierarchy. In view of this, we propose a new performance measure named Normalized Weighted Discounted Cumulative Gains (NWDCG) by extending Normalized Discounted Cumulative Gains (NDCG) using co-occurrence probability matrix. To verify the effectiveness of NWDCG, we conduct extensive experiments using three popular cross-modal hashing schemes over two publically available datasets.