Search

Given a graph G, a budget k and a misinformation seed set S, Influence Minimization (IMIN) via node blocking aims to find a set of k nodes to be blocked such that the expected spread of S is minimized. This problem finds important applications in suppressing the spread of misinformation and has been extensively studied in the literature. However, existing solutions for IMIN still incur significant computation overhead, especially when k becomes large. In addition, there is still no approximation solution with non-trivial theoretical guarantee for IMIN via node blocking prior to our work. In this paper, we conduct the first attempt to propose algorithms that yield data-dependent approximation guarantees. Based on the Sandwich framework, we first develop submodular and monotonic lower and upper bounds for our non-submodular objective function and prove the computation of proposed bounds is \#P-hard. In addition, two advanced sampling methods are proposed to estimate the value of bounding functions. Moreover, we develop two novel martingale-based concentration bounds to reduce the sample complexity and design two non-trivial algorithms that provide (1-1/e-\epsilon)-approximate solutions to our bounding functions. Comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques. Compared with the state-of-the-art methods, our solutions can achieve up to two orders of magnitude speedup and provide theoretical guarantees for the quality of returned results.

Ultrasmall Au nanoclusters have been proven to effectively enhance the catalytic performance of NiFe layered double hydroxides (NiFe-LDHs) toward oxygen evolution reaction (OER), yet the surface ligand effect of the Au nanoclusters still remains elusive. Herein, a systematic study is reported to examine the OER performance of NiFe-LDHs supported atom-precise all alkynyl-protected [Au28(tBuC≡C)17]− nanoclusters (Au28-Alkynyl in short) and thiolate-protected Au28(TBBT)20 (TBBT = 4-tert-butylbenzenethiol) counterparts (Au28-Thiolate in short). The Au28-Alkynyl cluster has characteristic absorbance feature, and its composition is verified by mass spectrometry. It possesses a drastically different structure from the reported mixed ligand protected Au28 nanoclusters. Interestingly, the NiFe-LDHs loaded with Au28-Alkynyl exhibited a superior OER performance than the sample loaded with Au28-Thiolate under the same conditions, evidenced by a smaller overpotential of 205 mV at the current density of 10 mA·cm−2 and a lower Tafel slope value of 41.0 mV·dec−1 in 1 mol·L−1 KOH. Such excellent performance is attributed to the interfaces created between the NiFe-LDHs and the Au nanoclusters, as density functional theory calculations reveal that more significant charge transfer occurs in Au28-Alkynyl/NiFe-LDHs catalyst, and more importantly, the energy barrier of the potential-determining step in the OER process for Au28-Alkynyl/NiFe-LDHs is much lower than that of Au28-Thiolate/NiFe-LDHs hence favors the electrocatalytic reaction.

Xiao-kun Liu,1,* Dan-ling Huang,1,2,* Li-ping Meng,1 Wei Cheng,1 Yi-yi Li,1 Lu-lu Qin,3 Ao Yang,4 Fan Zeng,5 Qin Zou,1 Qi-fu Li6 1Clinical Psychology Department, The First Affiliated Hospital of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 2Neurology Department, Graduate School of Tianjin Medical University, Tianjin City, People’s Republic of China; 3Department of Social Medicine and Health Management, School of Medicine, Hunan Normal University, Changsha City, Hunan Province, People’s Republic of China; 4Health Management Department, School of Management of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 5Graduate School of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 6Neurology Department, The First Affiliated Hospital of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China*These authors contributed equally to this workCorrespondence: Xiao-kun Liu; Qi-fu Li, Email lacyfairy@qq.com; lee-chief@163.comAim: This study was designed to develop an effective measurement tool for occupational stress among medical staff and to identify the underlying risk factors among clinical nurses in China under depression during and after COVID-19.Methods: In the first stage, an occupational stress scale was developed for medical staff based on qualitative and quantitative methods. The dimensions of the scale were based on childhood stress and seven other parameters of working stress. In the second stage, a provincial survey was conducted among clinical nurses in Hainan. The structure of Medical Staff Occupational Stress Scale was tested in secondary and tertiary hospitals. The socio-demographic information, occupational stress (measured using the developed scale), and current depression symptoms (assessed with the nine‐item Patient Health Questionnaire) were evaluated. The risk factors for occupational

Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design efficient query processing and index construction algorithms with good performance guarantees. Moreover, due to the dynamic properties of real-world networks, we also devise index maintenance algorithms that can maintain the index efficiently. To evaluate the performance of proposed methods, we conduct extensive experimental studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to two orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the experimental results also show that the index can also be efficiently constructed and maintained for dynamic graphs.

The Feedback vertex set with the minimum size is one of Karp's 21 NP-complete problems targeted at breaking all the cycles in a graph. This problem is applicable to a broad variety of domains, including E-commerce networks, database systems, and program analysis. In reality, users are frequently most concerned with the hop-constrained cycles (i.e., cycles with a limited number of hops). For instance, in the E-commerce networks, the fraud detection team would discard cycles with a high number of hops since they are less relevant and grow exponentially in size. Thus, it is quite reasonable to investigate the feedback vertex set problem in the context of hop-constrained cycles, namely hop-constrained cycle cover problem. It is concerned with determining a set of vertices that covers all hop-constrained cycles in a given directed graph. A common method to solve this is to use a bottom-up algorithm, where it iteratively selects cover vertices into the result set. Based on this paradigm, the existing works mainly focus on the vertices orders and several heuristic strategies. In this paper, a totally opposite cover process topdown is proposed and bounds are presented on it. Surprisingly, both theoretical time complexity and practical performance are improved.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study the maximal balanced clique enumeration problem (MBCE) which computes all the maximal balanced cliques in a given signed network and the maximum balanced clique search problem (MBCS) which computes the balanced clique with maximum size. We show that MBCE problem and MBCS problem are both NP-Hard. For the MBCE problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the MBCS problem, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments on large real datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms for MBCE problem and MBCS problem.

Subgraph matching is a fundamental problem in various fields that use graph structured data. Subgraph matching algorithms enumerate all isomorphic embeddings of a query graph q in a data graph G. An important branch of matching algorithms exploit the backtracking search approach which recursively extends intermediate results following a matching order of query vertices. It has been shown that the matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In recent years, many advanced techniques for query vertex ordering (i.e., matching order generation) have been proposed to reduce the unpromising intermediate results according to the preset heuristic rules. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms. Instead of using the fixed heuristics to generate the matching order, our model could capture and make full use of the graph information, and thus determine the query vertex order with the adaptive learning-based rule that could significantly reduces the number of redundant enumerations. With the help of the reinforcement learning framework, our model is able to consider the long-term benefits rather than only consider the local information at current ordering step.Extensive experiments on six real-life data graphs demonstrate that our proposed matching order generation technique could reduce up to two orders of magnitude of query processing time compared to the state-of-the-art algorithms., Comment: Accepted by ICDE 2022

In this paper, we improve the cube attack by exploiting low-degree factors of the superpoly w.r.t. certain "special" index set of cube (ISoC). This can be viewed as a special case of the correlation cube attack proposed at Eurocrypt 2018, but under our framework more beneficial equations on the key variables can be obtained in the key-recovery phase. To mount our attack, one has two challenging problems: effectively recover algebraic normal form of the superpoly and extract out its low-degree factors; and efficiently search a large quantity of good ISoCs. We bring in new techniques to solve both of them. First, we propose the variable substitution technique for middle rounds of a cipher, in which polynomials on the key variables in the algebraic expressions of internal states are substituted by new variables. This will improve computational complexity of the superpoly recovery and promise more compact superpolys that can be easily decomposed with respect to the new variables. Second, we propose the vector numeric mapping technique, which seeks out a tradeoff between efficiency of the numeric mapping technique and accuracy of the monomial prediction technique in degree evaluation of superpolys. Combining with this technique, a fast pruning method is given and modeled by MILP to filter good ISoCs of which the algebraic degree satisfies some fixed threshold. Thanks to automated MILP solvers, it becomes practical to comprehensively search for good cubes across the entire search space. To illustrate the power of our techniques, we apply all of them to Trivium stream cipher. The previous best practical key recovery attack was on 820-round Trivium with complexity $2^{53.17}$. We put forward 820-, 825- and 830-round practical key-recovery attacks, in which there are 2^{80}\times 87.8%, 2^{80}\times 83% and 2^{80}\times 65.7% keys that could be practically recovered, respectively.

Bipartite graphs are naturally used to model relationships between two different types of entities. On bipartite graphs, maximum biclique search is a fundamental problem that aims to find the complete bipartite subgraph (biclique) with the maximum number of edges and is widely adopted for many applications such as anomaly detection in E-commerce and social network analysis. However, maximum biclique search only identifies the biclique whose size is globally maximum, whereas fast microscopic (personalized) analysis is needed in many real-world scenarios. For instance, when a suspected user is identified in an E-commerce network (e.g., a user-product network), it is important to quickly find the anomalous group containing the user and send the group of users for further human expert investigation. To fill this research gap, for the first time, we study the efficient personalized maximum biclique search problem, which aims to find the maximum biclique containing a specific query vertex in real-time. Apart from online computation algorithms, we explore index-based approaches and propose the PMBC-Index. With the PMBC-Index, the query algorithm is up to five orders of magnitude faster than the baseline algorithms. Furthermore, effective pruning strategies and parallelization techniques are devised to support efficient index construction. Extensive experiments on 10 real-world graphs validate both the effectiveness and the efficiency of our proposed techniques.

Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness. In this paper, we propose a novel approximate subgraph counting algorithm, NeurSC, that can exploit and combine information from both the query graphs and the data graphs effectively and efficiently. It consists of two components: (1) an extraction module that adaptively generates simple yet representative substructures from data graph for each query graph and (2) an estimator WEst that first computes the representations from individual and joint distributions of query and data graphs and then estimates subgraph counts with the learned representations. Furthermore, we design a novel Wasserstein discriminator in WEst to minimize the Wasserstein distance between query and data graphs by updating the parameters in network with the vertex correspondence relationship between query and data graphs. By doing this, WEst can better capture the correlation between query and data graphs which is essential to the quality of the estimation. We conduct experimental studies on seven large real-life labeled graphs to demonstrate the superior performance of NeurSC in terms of estimation accuracy and robustness.

Xiao-kun Liu,1 Shan-lin Chen,1 Dan-ling Huang,1 Zi-shang Jiang,1 Yu-ting Jiang,1 Li-juan Liang,1 Lu-lu Qin2 1The First Affiliated Hospital of Hainan Medical University, Haikou, People’s Republic of China; 2Department of Social Medicine and Health Management, School of Medicine, Hunan Normal University, Changsha, People’s Republic of ChinaCorrespondence: Xiao-kun LiuThe First Affiliated Hospital of Hainan Medical University, 3 Xueyuan Road, Haikou, 571199, Hainan, People’s Republic of ChinaEmail lacyfairy@qq.comPurpose: Road safety research is important due to the large number of road traffic fatalities globally. This study investigated the influences of age, driving experience and other covariates on aggressive driving behavior.Methods: A cross-sectional survey was conducted in Yixing City, Wuxi City, Jiangsu Province, China. Regression analysis was applied to explore the influences of age and driving experience and their interactions with other covariates on aggressive driving behavior. Two analyses methodologies were used to assess the simple effect of the interactions. Firstly, the Jamovi automatic analysis classification program was used to calculate the simple slope test. Second, the SPSS macro program was also used to calculate the simple slope test also.Results: A total of 570 drivers (247 males, 282 females) participated in the survey. A negative correlation was found between age and aggressive driving behaviors, and a positive correlation was found between neuroticism and aggressive driving behaviors in the multiple regression analysis. Significant associations were also found between age, driving experience, and depression, as well as age, driving experience, and neuroticism. Simple slope tests showed that depressive symptoms could increase aggressive behaviors in the elderly and experienced drivers. When experiencing neuroticism, individuals with higher driving experience were more aggressive in driving than shorter experienced drivers.Conclusion: A

Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments., Comment: 14 pages, ICDE 2021

Triangle listing is an important topic significant in many practical applications. Efficient algorithms exist for the task of triangle listing. Recent algorithms leverage an orientation framework, which can be thought of as mapping an undirected graph to a directed acylic graph, namely oriented graph, with respect to any global vertex order. In this paper, we propose an adaptive orientation technique that satisfies the orientation technique but refines it by traversing carefully based on the out-degree of the vertices in the oriented graph during the computation of triangles. Based on this adaptive orientation technique, we design a new algorithm, namely aot, to enhance the edge-iterator listing paradigm. We also make improvements to the performance of aot by exploiting the local order within the adjacent list of the vertices. We show that aot is the first work which can achieve best performance in terms of both practical performance and theoretical time complexity. Our comprehensive experiments over $16$ real-life large graphs show a superior performance of our \aot algorithm when compared against the state-of-the-art, especially for massive graphs with billions of edges. Theoretically, we show that our proposed algorithm has a time complexity of $\Theta(\sum_{ \langle u,v \rangle \in \vec{E} } \min\{ deg^{+}(u),deg^{+}(v)\}))$, where $\vec{E}$ and $deg^{+}(x)$ denote the set of directed edges in an oriented graph and the out-degree of vertex $x$ respectively. As to our best knowledge, this is the best time complexity among in-memory triangle listing algorithms., Comment: Submitted to and accepted by DASFFA 2020

Core decomposition is a fundamental operator in network analysis. In this paper, we study the problem of computing distance-generalized core decomposition on a network. A distance-generalized core, also termed $(k, h)$-core, is a maximal subgraph in which every vertex has at least $k$ other vertices at distance no larger than $h$. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes the vertex (denoted by $v$) from the graph that has the smallest $h$-degree. The $h$-degree of a vertex $v$ denotes the number of other vertices that are reachable from $v$ within $h$ hops. Such a peeling algorithm, however, needs to frequently recompute the $h$-degrees of $v$'s neighbors after deleting $v$, which is typically very costly for a large $h$. To overcome this limitation, we propose an efficient peeling algorithm based on a novel $h$-degree updating technique. Instead of recomputing the $h$-degrees, our algorithm can dynamically maintain the $h$-degrees for all vertices via exploring a very small subgraph, after peeling a vertex. We show that such an $h$-degree updating procedure can be efficiently implemented by an elegant bitmap technique. In addition, we also propose a sampling-based algorithm and a parallelization technique to further improve the efficiency. Finally, we conduct extensive experiments on 12 real-world graphs to evaluate our algorithms. The results show that, when $h\ge 3$, our exact and sampling-based algorithms can achieve up to $10\times$ and $100\times$ speedup over the state-of-the-art algorithm, respectively.

Entity interaction prediction is essential in many important applications such as chemistry, biology, material science, and medical science. The problem becomes quite challenging when each entity is represented by a complex structure, namely structured entity, because two types of graphs are involved: local graphs for structured entities and a global graph to capture the interactions between structured entities. We observe that existing works on structured entity interaction prediction cannot properly exploit the unique graph of graphs model. In this paper, we propose a Graph of Graphs Neural Network, namely GoGNN, which extracts the features in both structured entity graphs and the entity interaction graph in a hierarchical way. We also propose the dual-attention mechanism that enables the model to preserve the neighbor importance in both levels of graphs. Extensive experiments on real-world datasets show that GoGNN outperforms the state-of-the-art methods on two representative structured entity interaction prediction tasks: chemical-chemical interaction prediction and drug-drug interaction prediction. Our code is available at Github., Comment: Accepted by IJCAI 2020

Recently, there have been some breakthroughs in graph analysis by applying the graph neural networks (GNNs) following a neighborhood aggregation scheme, which demonstrate outstanding performance in many tasks. However, we observe that the parameters of the network and the embedding of nodes are represented in real-valued matrices in existing GNN-based graph embedding approaches which may limit the efficiency and scalability of these models. It is well-known that binary vector is usually much more space and time efficient than the real-valued vector. This motivates us to develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters following the GNN-based paradigm. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches to binarize the model parameters and learn the compact embedding. Extensive experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space while matching the state-of-the-art performance.

Graph database has enjoyed a boom in the last decade, and graph queries accordingly gain a lot of attentions from both the academia and industry. We focus on analytical queries in this paper. While analyzing existing domain-specific languages (DSLs) for analytical queries regarding the perspectives of completeness, expressiveness and programmability, we find out that none of existing work has achieved a satisfactory coverage of these perspectives. Motivated by this, we propose the \flash DSL, which is named after the three primitive operators Filter, LocAl and PuSH. We prove that \flash is Turing complete (completeness), and show that it achieves both good expressiveness and programmability for analytical queries. We provide an implementation of \flash based on code generation, and compare it with native C++ codes and existing DSL using representative queries. The experiment results demonstrate \flash's expressiveness, and its capability of programming complex algorithms that achieve satisfactory runtime., Comment: 22 pages

Graph is a ubiquitous structure in many domains. The rapidly increasing data volume calls for efficient and scalable graph data processing. In recent years, designing distributed graph processing systems has been an increasingly important area to fulfil the demands of processing big graphs in a distributed environment. Though a variety of distributed graph processing systems have been developed, very little attention has been paid to achieving a good combinational system performance in terms of usage simplicity, efficiency and scalability. To contribute to the study of distributed graph processing system, this work tries to fill this gap by designing a simple, speedy and scalable system. Our observation is that enforcing the communication flexibility of a system leads to the gains of both system efficiency and scalability as well as simple usage. We realize our idea in a system Graph3S and conduct extensive experiments with diverse algorithms over big graphs from different domains to test its performance. The results show that, besides simple usage, our system has outstanding performance over various graph algorithms and can even reach up to two orders of magnitude speedup over existing in-memory systems when applying to some algorithms. Also, its scalability is competitive to disk-based systems and even better when less machines are used.

Cohesive subgraph mining in bipartite graphs becomes a popular research topic recently. An important structure k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2, 2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k >= 0. The existing bottom-up techniques need to iteratively peel the edges with the lowest butterfly support. In this peeling process, these techniques are time-consuming to enumerate all the supporting butterflies for each edge. To relax this issue, we first propose a novel online index -- the BE-Index which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process in an efficient way. Furthermore, the BiT-PC algorithm is devised which is more efficient against handling the edges with high butterfly supports. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. Also, we conduct extensive experiments on real datasets and the result demonstrates that our new techniques can speed up the state-of-the-art techniques by up to two orders of magnitude.

Bipartite graphs are widely used to model relationships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, community search on bipartite graphs remains largely unexplored. Moreover, all existing cohesive subgraph models on bipartite graphs can only be applied to measure the structure cohesiveness between two sets of vertices while overlooking the edge weight in forming the community. In this paper, we study the significant (alpha, beta)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (alpha, beta)-community R of q which adopts (alpha, beta)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within R. To support fast retrieval of R, we first retrieve the maximal connected subgraph of (alpha, beta)-core containing the query vertex (the (alpha, beta)-community), and the search space is limited to this subgraph with a much smaller size than the original graph. A novel index structure is presented which can be built in O(delta * m) time and takes O(delta * m) space where m is the number of edges in G, delta is bounded by the square root of m and is much smaller in practice. Utilizing the index, the (alpha, beta)-community can be retrieved in optimal time. To further obtain R, we develop peeling and expansion algorithms to conduct searches by shrinking from the (alpha, beta)-community and expanding from the query vertex, respectively. The experimental results on real graphs not only demonstrate the effectiveness of the significant (alpha, beta)-community model but also validate the efficiency of our query processing and indexing techniques.

Simulation and its variants (e.g., bisimulation and degree-preserving simulation) are useful in a wide spectrum of applications. However, all simulation variants are coarse "yes-or-no" indicators that simply confirm or refute whether one node simulates another, which limits the scope and power of their utility. Therefore, it is meaningful to develop a fractional $\chi$-simulation measure to quantify the degree to which one node simulates another by the simulation variant $\chi$. To this end, we first present several properties necessary for a fractional $\chi$-simulation measure. Then, we present $FSim_\chi$, a general fractional $\chi$-simulation computation framework that can be configured to quantify the extent of all $\chi$-simulations. Comprehensive experiments and real-world case studies show the measure to be effective and the computation framework to be efficient.

Xiao-kun Liu,1– 3 Shui-yuan Xiao,2,4 Dan Luo,4 Jiang-hua Zhang,5 Lu-lu Qin,6 Xun-qiang Yin4 1The First Affiliated Hospital of Hainan Medical University, Haikou, People’s Republic of China; 2Mental Health Center, Xiangya Hospital, Central South University, Changsha, Hunan 410008, People’s Republic of China; 3Key Laboratory of Brain Science Research & Transformation in Tropical Environment of Hainan Province; 4Xiangya School of Public Health, Central South University, Changsha, People’s Republic of China; 5Student Affairs Office of Central South University, Hunan, People’s Republic of China; 6Department of Social Medicine and Health Management, School of Medicine, Hunan Normal University, Changsha, People’s Republic of ChinaCorrespondence: Shui-yuan Xiao Mental Health Center, Xiangya Hospital, 87 Xiangya Road, Changsha 410087, Hunan, People’s Republic of ChinaFax +86-0731-84327332Email shuiyuanxiao1503@163.comPurpose: The aim of this study was to develop a scale to quantify the negative life events of graduate students; and to identify the associations between negative life events and emotional disorders among them.Methods: Based on a literature review, qualitative interviews and direct consultation with experts in relevant fields, the study served to identify the items that could be included in the Negative Life Events Scale for graduates (LES-GS). Psychometrics was used to analyze the items for reliability and validity. A cross-sectional survey was conducted in Changsha, China to explore the association between negative life events and emotional disorders among master’s and PhD students. LES-GS, Patient Health Questionnaire-9 (PHQ-9), and the Generalized Anxiety Disorder Scale-7 (GAD-7) were utilized in the survey.Results: The LES-GS exhibited acceptable reliability and validity. A total of 13.24% of master’s and 16.60% of PhD students experienced moderate to severe dep

Temporal graphs are ubiquitous. Mining communities that are bursting in a period of time is essential to seek emergency events in temporal graphs. Unfortunately, most previous studies for community mining in temporal networks ignore the bursting patterns of communities. In this paper, we are the first to study a problem of seeking bursting communities in a temporal graph. We propose a novel model, called (l, {\delta})-maximal dense core, to represent a bursting community in a temporal graph. Specifically, an (l, {\delta})-maximal dense core is a temporal subgraph in which each node has average degree no less than {\delta} in a time segment with length no less than l. To compute the (l, {\delta})-maximal dense core, we first develop a novel dynamic programming algorithm which can calculate the segment density efficiently. Then, we propose an improved algorithm with several novel pruning techniques to further improve the efficiency. In addition, we also develop an efficient algorithm to enumerate all (l, {\delta})-maximal dense cores that are not dominated by the others in terms of the parameters l and {\delta}. The results of extensive experiments on 9 real-life datasets demonstrate the effectiveness, efficiency and scalability of our algorithms., Comment: Submitted to ICDE at October 15, 2019

Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view to the pros and cons of each algorithm mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art works. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy-level comparison. Our implementation covers all representation algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.

With the rapid development of information technologies, various big graphs are prevalent in many real applications (e.g., social media and knowledge bases). An important component of these graphs is the network community. Essentially, a community is a group of vertices which are densely connected internally. Community retrieval can be used in many real applications, such as event organization, friend recommendation, and so on. Consequently, how to efficiently find high-quality communities from big graphs is an important research topic in the era of big data. Recently a large group of research works, called community search, have been proposed. They aim to provide efficient solutions for searching high-quality communities from large networks in real-time. Nevertheless, these works focus on different types of graphs and formulate communities in different manners, and thus it is desirable to have a comprehensive review of these works. In this survey, we conduct a thorough review of existing community search works. Moreover, we analyze and compare the quality of communities under their models, and the performance of different solutions. Furthermore, we point out new research directions. This survey does not only help researchers to have a better understanding of existing community search solutions, but also provides practitioners a better judgment on choosing the proper solutions.

Set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications including data cleaning, information extraction, machine learning and so on. In this thesis, we study three important problems regarding set similarity join.Firstly, we develop algorithms for static exact set similarity join problem. The existing solutions for exact set similarity join follow a filtering-verification framework, which generates a list of candidate pairs through scanning indexes in the filtering phase, and reports those similar pairs in the verification phase. Though much research has been conducted on this problem, set relations have not been well studied on improving the algorithm efficiency through computational cost sharing. Therefore, we explore the set relations in different levels to reduce the overall computational costs. It has been shown that most of the computational time is spent on the filtering phase. Thus we explore index-level set relations to reduce the filtering cost while keeping the same filtering power. We achieve this by grouping related sets into blocks in the index and skipping useless index probes in joins. Also, we explore answer-level set relations to further improve the algorithm based on the intuition that if two sets are similar, their answers may have a large overlap. We conduct extensive performance studies using 21 real datasets with various data properties from a wide range of domains. The experimental results demonstrate that our algorithm outperforms all the existing algorithms across all datasets.Secondly, we study the dynamic set similarity join problem considering that the data are usually updated dynamically in real applications. No previous study has been found on this problem. We design efficient algorithms to incrementally update the join result when any element in the sets is updated. Computational cost is analyzed on proposed algorithms. Comprehensive experiment

Bipartite networks are of great importance in many real-world applications. In bipartite networks, butterfly (i.e., a complete 2 x 2 biclique) is the smallest non-trivial cohesive structure and plays a key role. In this paper, we study the problem of efficient counting the number of butterflies in bipartite networks. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite networks. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm BFC-VP to enumerate much fewer wedges; this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve time efficiency while theoretically retaining the time complexity of BFC-VP. Moreover, we also show that our proposed techniques can work efficiently in external and parallel contexts. Our extensive empirical studies demonstrate that the proposed techniques can speed up the state-of-the-art techniques by up to two orders of magnitude for the real datasets.

Subgraph enumeration is a fundamental graph problem with many applications. However, existing algorithms for subgraph enumeration fall short in handling large graphs due to the computational hardness. In this work, we propose a general approach that solves subgraph enumeration in the distributed contexts, including MapReduce and Spark. The approach features a decomposition-and-join manner, in which the pattern graph is decomposed into a set of structures, called join unit. We introduce the distributed graph storage mechanism to determine what structure can be the join unit. Consequently, we obtain the results by joining the matches of all join units following a specific join structure. Based on the general approach, we first propose a star-based join framework. In the framework, we adopt a basic graph storage mechanism that only supports a star (a tree with depth 2) as the join unit, and we apply the left-deep join structure to process the join. We then show that a special star called TwinTwig - an edge or two incident edges of a node - is enough to guarantee instance optimality in the star-based join framework under reasonable assumptions, which inspires the TwinTwigJoin algorithm. We devise an A*-based algorithm to compute the optimal join plan for TwinTwigJoin. TwinTwigJoin is still not scalable to large graph because of the constraints in the left-deep join structure and that each join unit must be a star. We then explore the graph-based join framework that allows us to use more than just star as the join unit. In addition, we use the bushy join structure rather than left-deep join to guarantee the optimality of the join plan. Aware that it is storage-inefficient to use any structure as the join unit, we develop the SEED algorithm that implements an effective distributed graph storage mechanism to use star and clique (complete graph) as the join units. We then devise a dynamic-programming algorithm to compute an optimal bushy join plan. SEED frees us from the co

Cohesive subgraph search has been recently studied for its large number of applications in social networks, web search, collaboration networks, and biology. Most existing approaches for cohesive subgraph search assume that the graph is kept in memory of a machine. However, many real-world graphs are big and may not reside in memory. Consequently, the I/Os between fast internal memory and slower disks can be a major performance bottleneck for these algorithms when the graph is too large to fit completely in memory. Therefore, there is an emerging call for I/O efficient algorithms for cohesive subgraph search. In this paper, we study three important problems in cohesive subgraph search with respect to the I/O efficiency: diversified top-k clique search, edge connected component decomposition and Steiner component search.Firstly, we investigate the I/O efficient algorithm for diversified top-k clique search problem. We devise an algorithm to maintain k candidates in the process of maximal clique enumeration. Our algorithm has limited memory footprint and can achieve a guaranteed approximation ratio. We also introduce a novel light-weight PNP-Index, based on which we design an optimal maximal clique maintenance algorithm. We further explore three optimization strategies to avoid enumerating all maximal cliques and thus largely reduce the computational cost. For the massive input graph, we also develop an I/O efficient algorithm to tackle the problem when the input graph cannot fit in main memory.Secondly, we study the problem of edge connected component decomposition. We introduce two elegant graph reduction operators and propose three novel I/O efficient algorithms, Bottom-Up, Top-Down, and Hybrid, that explore the k values in different orders to perform the edge connected component decomposition. Finally, we investigate the problem of computing the Steiner component with the maximum connectivity, which aims to find the maximum induced subgraph that has the maximum con

Cohesive subgraph detection is an important graph problem that is widely applied in many application domains, such as social community detection, network visualization, and network topology analysis. Most of existing cohesive subgraph metrics can guarantee good structural properties but may cause the free-rider effect. Here, by free-rider effect, we mean that some irrelevant subgraphs are combined as one subgraph if they only share a small number of vertices and edges. In this paper, we study k-vertex connected component (k-VCC) which can effectively eliminate the free-rider effect but less studied in the literature. A k-VCC is a connected subgraph in which the removal of any k-1 vertices will not disconnect the subgraph. In addition to eliminating the free-rider effect, k-VCC also has other advantages such as bounded diameter, high cohesiveness, bounded graph overlapping, and bounded subgraph number. We propose a polynomial time algorithm to enumerate all k-VCCs of a graph by recursively partitioning the graph into overlapped subgraphs. We find that the key to improving the algorithm is reducing the number of local connectivity testings. Therefore, we propose two effective optimization strategies, namely neighbor sweep and group sweep, to largely reduce the number of local connectivity testings. We conduct extensive performance studies using seven large real datasets to demonstrate the effectiveness of this model as well as the efficiency of our proposed algorithms., Comment: 16 pages

Graph edit distance (GED) is an important similarity measure adopted in a similarity-based analysis between two graphs, and computing GED is a primitive operator in graph database analysis. Partially due to the NP-hardness, the existing techniques for computing GED are only able to process very small graphs with less than 30 vertices. Motivated by this, in this paper we systematically study the problems of both GED computation, and GED verification (i.e., verify whether the GED between two graphs is no larger than a user-given threshold). Firstly, we develop a unified framework that can be instantiated into either a best-first search approach AStar+ or a depth-first search approach DFS+. Secondly, we design anchor-aware lower bound estimation techniques to compute tighter lower bounds for intermediate search states, which significantly reduce the search spaces of both AStar+ and DFS+. We also propose efficient techniques to compute the lower bounds. Thirdly, based on our unified framework, we contrast AStar+ with DFS+ regarding their time and space complexities, and recommend that AStar+ is better than DFS+ by having a much smaller search space. Extensive empirical studies validate that AStar+ performs better than DFS+, and show that our AStar+-BMa approach outperforms the state-of-the-art technique by more than four orders of magnitude.

Data imputation aims at filling in missing attribute values in databases. Existing imputation approaches to nonquantitive string data can be roughly put into two categories: (1) inferring-based approaches [2], and (2) retrieving-based approaches [1]. Specifically, the inferring-based approaches find substitutes or estimations for the missing ones from the complete part of the data set. However, they typically fall short in filling in unique missing attribute values which do not exist in the complete part of the data set [1]. The retrieving-based approaches resort to external resources for help by formulating proper web search queries to retrieve web pages containing the missing values from the Web, and then extracting the missing values from the retrieved web pages [1]. This webbased retrieving approach reaches a high imputation precision and recall, but on the other hand, issues a large number of web search queries, which brings a large overhead [1]. © 2016 IEEE.

In this paper, we investigate the problem of (k,r)-core which intends to find cohesive subgraphs on social networks considering both user engagement and similarity perspectives. In particular, we adopt the popular concept of k-core to guarantee the engagement of the users (vertices) in a group (subgraph) where each vertex in a (k,r)-core connects to at least k other vertices. Meanwhile, we also consider the pairwise similarity between users based on their profiles. For a given similarity metric and a similarity threshold r, the similarity between any two vertices in a (k,r)-core is ensured not less than r. Efficient algorithms are proposed to enumerate all maximal (k,r)-cores and find the maximum (k,r)-core, where both problems are shown to be NP-hard. Effective pruning techniques significantly reduce the search space of two algorithms and a novel (k,k')-core based (k,r)-core size upper bound enhances performance of the maximum (k,r)-core computation. We also devise effective search orders to accommodate the different nature of two mining algorithms. Comprehensive experiments on real-life data demonstrate that the maximal/maximum (k,r)-cores enable us to find interesting cohesive subgraphs, and performance of two mining algorithms is significantly improved by proposed techniques.

Graphs have been widely used in many applications such as social networks, collaboration networks, and biological networks. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied, k-core is one that can be computed in linear time for a static graph. Since graphs are evolving in real applications, in this paper, we study core maintenance which is to reduce the computational cost to compute k-cores for a graph when graphs are updated from time to time dynamically. We identify drawbacks of the existing efficient algorithm, which needs a large search space to find the vertices that need to be updated, and has high overhead to maintain the index built, when a graph is updated. We propose a new order-based approach to maintain an order, called k-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-the-art algorithm up to 3 orders of magnitude for the 11 large real graphs tested. We report our findings in this paper.

Purpose: To investigate the relationship between retinal microvascular reactivity, circulatory markers for CVD risk and systemic antioxidative defence capacity in healthy middle-aged individuals with low to moderate risk of CVD. Methods: Retinal vascular reactivity to flickering light was assessed in 102 healthy participants (46-60 years) by means of dynamic retinal vessel analysis (DVA). Other vascular assessments included carotid intima-media thickness (C-IMT) and blood pressure (BP) measurements. Total cholesterol (CHOL), high-density lipoprotein cholesterol (HDL-C), low-density lipoprotein cholesterol (LDL-C), triglycerides (TG) and blood glutathione levels in its reduced (GSH) and oxidized (GSSG) forms were also determined for each participant, along with Framingham risk scores (FRS). Results: Retinal arterial baseline diameter fluctuation (BDF) was independently, significantly and negatively influenced by LDL-C levels (β = -0.53, p = 0.027). Moreover, the arterial dilation slope (SlopeAD) was independently, significantly and positively associated with redox index (GSH: GSSG ratio, β = 0.28, p = 0.016), while the arterial constriction slope (SlopeAC) was significantly and negatively influenced by blood GSH levels (β = -0.20, p = 0.042), and positively associated with FRS (β = 0.25, p = 0.009). Venous BDF and dilation amplitude (DA) were also negatively influenced by plasma LDL-C levels (β = -0.83, p = 0.013; and β = -0.22, p = 0.028, respectively). Conclusions: In otherwise healthy individuals with low to moderate cardiovascular risk, retinal microvascular dilation and constriction responses to stress levels are influenced by systemic antioxidant capacity, and circulating markers for cardiovascular risk.

Core decomposition is a fundamental graph problem with a large number of applications. Most existing approaches for core decomposition assume that the graph is kept in memory of a machine. Nevertheless, many real-world graphs are big and may not reside in memory. In the literature, there is only one work for I/O efficient core decomposition that avoids loading the whole graph in memory. However, this approach is not scalable to handle big graphs because it cannot bound the memory size and may load most parts of the graph in memory. In addition, this approach can hardly handle graph updates. In this paper, we study I/O efficient core decomposition following a semi-external model, which only allows node information to be loaded in memory. This model works well in many web-scale graphs. We propose a semi-external algorithm and two optimized algorithms for I/O efficient core decomposition using very simple structures and data access model. To handle dynamic graph updates, we show that our algorithm can be naturally extended to handle edge deletion. We also propose an I/O efficient core maintenance algorithm to handle edge insertion, and an improved algorithm to further reduce I/O and CPU cost by investigating some new graph properties. We conduct extensive experiments on 12 real large graphs. Our optimal algorithm significantly outperform the existing I/O efficient algorithm in terms of both processing time and memory consumption. In many memory-resident graphs, our algorithms for both core decomposition and maintenance can even outperform the in-memory algorithm due to the simple structures and data access model used. Our algorithms are very scalable to handle web-scale graphs. As an example, we are the first to handle a web graph with 978.5 million nodes and 42.6 billion edges using less than 4.2 GB memory.

Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimizatio

Naturally-occurring, endogenous electric fields (EFs) have been detected at skin wounds, damaged tissue sites and vasculature. Applied EFs guide migration of many types of cells, including endothelial cells to migrate directionally. Homing of endothelial progenitor cells (EPCs) to an injury site is important for repair of vasculature and also for angiogenesis. However, it has not been reported whether EPCs respond to applied EFs. Aiming to explore the possibility to use electric stimulation to regulate the progenitor cells and angiogenesis, we tested the effects of direct-current (DC) EFs on EPCs. We first used immunofluorescence to confirm the expression of endothelial progenitor markers in three lines of EPCs. We then cultured the progenitor cells in EFs. Using time-lapse video microscopy, we demonstrated that an applied DC EF directs migration of the EPCs toward the cathode. The progenitor cells also align and elongate in an EF. Inhibition of vascular endothelial growth factor (VEGF) receptor signaling completely abolished the EF-induced directional migration of the progenitor cells. We conclude that EFs are an effective signal that guides EPC migration through VEGF receptor signaling in vitro. Applied EFs may be used to control behaviors of EPCs in tissue engineering, in homing of EPCs to wounds and to an injury site in the vasculature.

Given a directed graph G, a reachability query (u, v) asks whether there exists a path from a node u to a node v in G. The existing studies support reachability queries using indexing techniques, where both the graph and the index are required to reside in main memory. However, they cannot handle reachability queries on massive graphs, when the graph and the index cannot be entirely held in memory because of the high I/O cost. In this paper, we focus on how to minimize the I/O cost when answering reachability queries on massive graphs that cannot reside entirely in memory. First, we propose a new Yes-Label scheme, as a complement of the No-Label used in GRAIL [23], to reduce the number of intermediate results generated. Second, we show how to minimize the number of I/Os using a heap-on-disk data structure when traversing a graph. We also propose new methods to partition the heap-on-disk, in order to ensure that only sequential I/Os are performed. Third, we analyze our approaches and show how to extend our approaches to answer multiple reachability queries effectively. Finally, we conducted extensive performance studies on both large synthetic and large real graphs, and confirm the efficiency of our approaches. © 2012 ACM.

To investigate the relationship between vascular function parameters measured at the retinal and systemic level and known markers for cardiovascular risk in patients with impaired glucose tolerance (IGT). Sixty age- and gender- matched White-European adults (30 IGT and 30 normal glucose tolerance -NGT) were recruited for the study. Fasting plasma glucose, lipids and 24-hour blood pressure (BP) was measured in all subjects. Systemic vascular and endothelial function was assessed using carotid-artery intimal media thickness (cIMT) and flow mediated dilation (FMD). Retinal vascular reactivity was assessed by the Dynamic Retinal Vessel Analyser (DVA). Additionally, blood glutathione (GSH, GSSG and tGSH) and plasma von-Willebrand (vWF) factor levels were also measured. Individuals with IGT demonstrated higher BP values (p<0.001), fasting TG and TG:HDL ratios (p<0.001) than NGT subjects. Furthermore, Total:HDL-C ratios and Framingham scores were raised (p=0.010 and p<0.001 respectively). Blood glutathione levels (GSH, GSSG and tGSH) were lower (p<0.001, p=0.039 and p<0.001 respectively) while plasma vWF was increased (p=0.014) in IGT subjects compared to controls. IGT individuals also demonstrated higher IMT in right and left carotid arteries (p=0.017 and p=0.005, respectively) alongside larger brachial artery diameter (p=0.015), lower FMD% (p=0.026) and GTN induced dilation (GID) (p=0.012) than healthy controls. At the retinal arterial level, the IGT subjects showed higher baseline fluctuations (BDF) (p=0.026), longer reaction time (RT) (p=0.032) and reduced baseline-corrected flicker response (bFR) (p=0.045). In IGT subjects retinal BDF correlated with and Total:HDL (p= 0.003) and HDL-C (p= 0.004). Arterial RT also correlated with FMD (p=0.017) in IGT but not NGT subjects. In IGT individuals there is a relationship between macro- and microvascular function, as well as a direct correlation between the observed retinal microcirculatory changes and established plasma marke

Top-k query processing finds a list of k results that have largest scores w.r.t the user given query, with the assumption that all the k results are independent to each other. In practice, some of the top-k results returned can be very similar to each other. As a result some of the top-k results returned are redundant. In the literature, diversified top-k search has been studied to return k results that take both score and diversity into consideration. Most existing solutions on diversified top-k search assume that scores of all the search results are given, and some works solve the diversity problem on a specific problem and can hardly be extended to general cases. In this paper, we study the diversified top-k search problem. We define a general diversified top-k search problem that only considers the similarity of the search results themselves. We propose a framework, such that most existing solutions for top-k query processing can be extended easily to handle diversified top-k search, by simply applying three new functions, a sufficient stop condition sufficient(), a necessary stop condition necessary(), and an algorithm for diversified top-k search on the current set of generated results, div-search-current(). We propose three new algorithms, namely, div-astar, div-dp, and div-cut to solve the div-search-current() problem. div-astar is an A* based algorithm, div-dp is an algorithm that decomposes the results into components which are searched using div-astar independently and combined using dynamic programming. div-cut further decomposes the current set of generated results using cut points and combines the results using sophisticated operations. We conducted extensive performance studies using two real datasets, enwiki and reuters. Our div-cut algorithm finds the optimal solution for diversified top-k search problem in seconds even for k as large as 2,000., Comment: VLDB2012

Purpose. To assess the relationship between macular pigment optical density (MPOD) and blood markers for antioxidant defense in otherwise healthy volunteers. Methods. Forty-seven healthy volunteers were subjected to blood analysis to detect the level of circulating glutathione in its reduced (GSH) and oxidized (GSSG) forms. The level of MPOD was measured using heterochromatic flicker photometry. Systemic blood pressure (BP) parameters, heart rate (HR), body mass index (BMI), and plasma levels of total, HDL, and LDL cholesterol and triglycerides (TGs) were also determined. Results. A simple correlation model revealed that the level of MPOD correlated significantly and positively with both GSH (P < 0.001) and t-GSH (P < 0.001) levels but not with those of GSSG (P > 0.05). Age, sex, systemic BP parameters, HR, BMI, and plasma levels of cholesterol and TGs did not have any influence on either MPOD or glutathione levels (all P > 0.05). In addition, a forward stepwise multiple regression analysis showed MPOD to have a significantly and independent correlation with GSH levels (ß = 0.63; P < 0.001). Conclusions. In otherwise healthy older individuals, there is a positive correlation between local and systemic antioxidant defense mechanisms.

In this thesis, for the schema-based approaches, we propose an efficient algorithm to general all relational algebra expressions in order to find all the connected trees in an RDB. We also study an efficient algorithm to evaluate all the expressions using semijoins in RDBMS . We show that our method can also be extended to answer continuous keyword queries in a relational data stream. We further propose novel algorithms that find sets of tuples that are reachable from a root tuple within a radius, and algorithms that find multi-center subgraphs within a radius. Our algorithms use SQL queries only in order to make fully use of RDBMS. We show that the current commercial RDBMSs are powerful enough to support such keyword queries in RDBs efficiently without any additional new indexing to be built and maintained. The main idea behind our approach is tuple reduction. For the graph-based approaches, we propose an efficient algorithm to find all/top- K multi-center subgraphs in polynomial delay. We also introduce a new kind of keyword query, namely, structural statistics by keywords, to summarize keyword search results into several dimensions. We conducted extensive performance studies using two large real datasets IMDB and DBLP to show the efficiency and effectiveness of all our approaches., Keyword search in relational databases (RDBs) has been extensively studied recently. A keyword search (or a keyword query) in RDBs is specified by a set of keywords to explore the interconnected tuple structures in an RDB that cannot be easily identified using SQL on RDBMSs. In brief, it finds how the tuples containing the given keywords are connected via sequences of connections (foreign key references) among tuples in an RDB. Such interconnected tuple structures can be found as connected trees up to a certain size, sets of tuples that are reachable from a root tuple within a radius, or even multi-center subgraphs within a radius. In the literature, there are two main approaches, namely schema-based approaches and graph-based approaches. The schema-based approaches are to generate a set of relational algebra expressions and evaluate every such expression using SQL on an RDBMS directly or in a middleware on top of an RDBMS indirectly. Due to a large number of relational algebra expressions needed to process, most of the existing works take a middleware approach without fully utilizing RDBMSs. The graph-based approaches are to materialize an RDB as a graph and find the interconnected tuple structures using graph-based algorithms in memory., Qin, Lu., Adviser: Jeffrey Xu Yu., Source: Dissertation Abstracts International, Volume: 73-02, Section: B, page: ., Thesis (Ph.D.)--Chinese University of Hong Kong, 2010., Includes bibliographical references (leaves 133-138)., Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web., Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web., also in Chinese., isbn: 9781124998718, Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

The probabilistic top-k queries based on the interplay of score and probability, under the possible worlds semantic, become an important research issue that considers both score and uncertainty on the same basis. In the literature, many different probabilistic top-k queries are proposed. Almost all of them need to compute the probability of a tuple t_i to be ranked at the j-th position across the entire set of possible worlds. The cost of such computing is the dominant cost and is known as O(kn^2), where n is the size of dataset. In this paper, we propose a new novel algorithm that computes such probability in O(kn).

This chapter presents these microscope systems, along with brief descriptions of the science experiments driving the development of each system. Beginning with a discussion of the philosophy that has driven the Nanoscale Science Research Group (NSRG) and the methods used, the chapter describes the lessons learned during system development, including both useful directions and blind alleys. The first lesson is to begin software development at least as soon as hardware development. The second lesson is to partner with experts in required technologies. The NSRG attempts to use the best available computer technology to develop effective systems for use by the physical science team, which then become cost-effective and can be deployed on widely available hardware as technology marches on. The chapter also describes techniques to enable telemicroscopy in the context of remote experiments and outreach. © 2005

Cyclic voltammetry of a series of air-stable dicopper(I.I) azacryptates indicates that some, including those with heterocyclic-N-donor spacers, are thermodynamically unstable towards oxidation by O2; in this case outer-sphere oxidation by Fc+ or Ag+ is readily achieved.