The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer s...The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.展开更多
Visual queries assist non-expert users to extract information from spatial databases in an intuitive and natural approach,making Geographic information systems comprehensive and efficient for a wide range of applicati...Visual queries assist non-expert users to extract information from spatial databases in an intuitive and natural approach,making Geographic information systems comprehensive and efficient for a wide range of applications.A common visual means of querying takes the form of drawings or graphs,under which many spatial ambiguity and translation errors rise.In this study,common query attributes extracted from user graphs such as spatial topology,size,cardinality,and proximity are regarded under a conceptual moderation scheme.Thus,the system/user may concentrate on various conceptual combinations of information.Furthermore,time is incorporated to support spatiotemporal queries for changing scenes and moving objects.Arbitrary,relative,and absolute scaling is possible according to the data-set and application at hand.The theoretic approach is implemented under a prototype user interface system,called ShapeController.Under this prototype,a user may extract scene-based relations in an automatically inferred fashion,or include single object-oriented relations when all possible relations seem redundant.Finally,a natural language description of the query is extracted upon which the user may select the desired query relations.Experimentation on a spatial database demonstrates the concepts of predefined draw objects,scaling relaxation,conceptual abstraction,and scene,object-and textual-oriented transitions that promote query expressiveness and restrain ambiguities.展开更多
Static optimization of logical queries is, in substance, to move selections down as far as possible in evaluating logical queries. This paper extends Ullman's RGG (Rule/Goal Graph) and introduces P- graph, with wh...Static optimization of logical queries is, in substance, to move selections down as far as possible in evaluating logical queries. This paper extends Ullman's RGG (Rule/Goal Graph) and introduces P- graph, with which a wide range of recursive logical queries can be statically optimized top-down and evaluated bottom-up, some of which are usually optimized by dynamic approaches. The paper also shows that for some logical queries the complexity of pushing selections down and computing bottom-up is related to the complexity of base relation in the queries.展开更多
Graphs are widely used for modeling complicated data such as social networks,chemical compounds,protein interactions and semantic web.To effiectively understand and utilize any collection of graphs,a graph database th...Graphs are widely used for modeling complicated data such as social networks,chemical compounds,protein interactions and semantic web.To effiectively understand and utilize any collection of graphs,a graph database that efficiently supports elementary querying mechanisms is crucially required.For example,Subgraph and Supergraph queries are important types of graph queries which have many applications in practice.A primary challenge in computing the answers of graph queries is that pair-wise comparisons of graphs are usually hard problems.Relational database management systems（RDBMSs） have repeatedly been shown to be able to efficiently host different types of data such as complex objects and XML data.RDBMSs derive much of their performance from sophisticated optimizer components which make use of physical properties that are specific to the relational model such as sortedness,proper join ordering and powerful indexing mechanisms.In this article,we study the problem of indexing and querying graph databases using the relational infrastructure.We present a purely relational framework for processing graph queries.This framework relies on building a layer of graph features knowledge which capture metadata and summary features of the underlying graph database.We describe different querying mechanisms which make use of the layer of graph features knowledge to achieve scalable performance for processing graph queries.Finally,we conduct an extensive set of experiments on real and synthetic datasets to demonstrate the efficiency and the scalability of our techniques.展开更多
It is increasingly common to find graphs in which edges are of different types, indicating a variety of relation- ships. For such graphs we propose a class of reachability queries and a class of graph patterns, in whi...It is increasingly common to find graphs in which edges are of different types, indicating a variety of relation- ships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, ex- pressing the connectivity of a data graph via edges of var- ious types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible informa- tion than their traditional counterparts. Better still, their in- creased expressive power does not come with extra complex- ity. Indeed, （1） we investigate their containment and mini- mization problems, and show that these fundamental prob- lems are in quadratic time for reachability queries and are in cubic time for pattern queries. （2） We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. （3） We provide two cubic-time algorithms for evaluating graph pattern queries, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. （4） The effectiveness and efficiency of these al- gorithms are experimentally verified using real-life data and synthetic data.展开更多
In this paper, an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed. High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluatio...In this paper, an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed. High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation. In such a way the subsumption checks and the identification of cyclic data can be done very efficielltly First, based on the subsumption checks, the search space can be reduced drastically by avoiding any redundant expansion operation. In fact, in the case of non-cyclic data, the proposed algorithm requires only linear time for evaluating a linear recursive query. On the other hand, in the case of cyclic data, by using the technique for isolating strongly connected components a lot of answers can be generated directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations. Since the cost of generating an answer is much less than that of evaluating an answer by algebraic operations, the time consumption for cyclic data can be reduced by an order of magnitude or more.展开更多
The existing search engines are lack of the consideration of personalization and display the same search results for different users despite their differences in interesting and purpose. By analyzing user＇s dynamic s...The existing search engines are lack of the consideration of personalization and display the same search results for different users despite their differences in interesting and purpose. By analyzing user＇s dynamic search behavior, the paper introduces a new method of using a keyword query graph to express user＇s dynamic search behavior, and uses Bayesian network to construct the prior probability of keyword selection and the migration probability between keywords for each user. To reflect the dynamic changes of the user＇s preference, the paper introduces non-lineal gradual forgetting collaborative filtering strategy into the personalized search recommendation model. By calculating the similarity between each two users, the model can do the recommendation based on neighbors and be used to construct the personalized search engine.展开更多
This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recurstion (ILR) and presents an optima...This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recurstion (ILR) and presents an optimal algorithm for each. First, for the CSLRs, the magic-set method is refined in such a way that queries can be evaluated efficiently. Then, for the NILRS and ILRs, the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied.展开更多
文摘The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.
基金supported by the basic research grant of the Special Account for Research of the Technical University of Crete for the project“Spatiotemporal queries by sketch in moving object geographic databases”(No.80080).
文摘Visual queries assist non-expert users to extract information from spatial databases in an intuitive and natural approach,making Geographic information systems comprehensive and efficient for a wide range of applications.A common visual means of querying takes the form of drawings or graphs,under which many spatial ambiguity and translation errors rise.In this study,common query attributes extracted from user graphs such as spatial topology,size,cardinality,and proximity are regarded under a conceptual moderation scheme.Thus,the system/user may concentrate on various conceptual combinations of information.Furthermore,time is incorporated to support spatiotemporal queries for changing scenes and moving objects.Arbitrary,relative,and absolute scaling is possible according to the data-set and application at hand.The theoretic approach is implemented under a prototype user interface system,called ShapeController.Under this prototype,a user may extract scene-based relations in an automatically inferred fashion,or include single object-oriented relations when all possible relations seem redundant.Finally,a natural language description of the query is extracted upon which the user may select the desired query relations.Experimentation on a spatial database demonstrates the concepts of predefined draw objects,scaling relaxation,conceptual abstraction,and scene,object-and textual-oriented transitions that promote query expressiveness and restrain ambiguities.
文摘Static optimization of logical queries is, in substance, to move selections down as far as possible in evaluating logical queries. This paper extends Ullman's RGG (Rule/Goal Graph) and introduces P- graph, with which a wide range of recursive logical queries can be statically optimized top-down and evaluated bottom-up, some of which are usually optimized by dynamic approaches. The paper also shows that for some logical queries the complexity of pushing selections down and computing bottom-up is related to the complexity of base relation in the queries.
文摘Graphs are widely used for modeling complicated data such as social networks,chemical compounds,protein interactions and semantic web.To effiectively understand and utilize any collection of graphs,a graph database that efficiently supports elementary querying mechanisms is crucially required.For example,Subgraph and Supergraph queries are important types of graph queries which have many applications in practice.A primary challenge in computing the answers of graph queries is that pair-wise comparisons of graphs are usually hard problems.Relational database management systems（RDBMSs） have repeatedly been shown to be able to efficiently host different types of data such as complex objects and XML data.RDBMSs derive much of their performance from sophisticated optimizer components which make use of physical properties that are specific to the relational model such as sortedness,proper join ordering and powerful indexing mechanisms.In this article,we study the problem of indexing and querying graph databases using the relational infrastructure.We present a purely relational framework for processing graph queries.This framework relies on building a layer of graph features knowledge which capture metadata and summary features of the underlying graph database.We describe different querying mechanisms which make use of the layer of graph features knowledge to achieve scalable performance for processing graph queries.Finally,we conduct an extensive set of experiments on real and synthetic datasets to demonstrate the efficiency and the scalability of our techniques.
文摘It is increasingly common to find graphs in which edges are of different types, indicating a variety of relation- ships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, ex- pressing the connectivity of a data graph via edges of var- ious types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible informa- tion than their traditional counterparts. Better still, their in- creased expressive power does not come with extra complex- ity. Indeed, （1） we investigate their containment and mini- mization problems, and show that these fundamental prob- lems are in quadratic time for reachability queries and are in cubic time for pattern queries. （2） We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. （3） We provide two cubic-time algorithms for evaluating graph pattern queries, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. （4） The effectiveness and efficiency of these al- gorithms are experimentally verified using real-life data and synthetic data.
文摘In this paper, an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed. High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation. In such a way the subsumption checks and the identification of cyclic data can be done very efficielltly First, based on the subsumption checks, the search space can be reduced drastically by avoiding any redundant expansion operation. In fact, in the case of non-cyclic data, the proposed algorithm requires only linear time for evaluating a linear recursive query. On the other hand, in the case of cyclic data, by using the technique for isolating strongly connected components a lot of answers can be generated directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations. Since the cost of generating an answer is much less than that of evaluating an answer by algebraic operations, the time consumption for cyclic data can be reduced by an order of magnitude or more.
基金supported by the National Natural Science Foundation of China (60432010)the National Basic Research Program of China (2007CB307103)+1 种基金the Fundamental Research Funds for the Central Universities (2009RC0507)Important Science & Technology Specific Project of Guizhou Province (【2007】6017)
文摘The existing search engines are lack of the consideration of personalization and display the same search results for different users despite their differences in interesting and purpose. By analyzing user＇s dynamic search behavior, the paper introduces a new method of using a keyword query graph to express user＇s dynamic search behavior, and uses Bayesian network to construct the prior probability of keyword selection and the migration probability between keywords for each user. To reflect the dynamic changes of the user＇s preference, the paper introduces non-lineal gradual forgetting collaborative filtering strategy into the personalized search recommendation model. By calculating the similarity between each two users, the model can do the recommendation based on neighbors and be used to construct the personalized search engine.
文摘This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recurstion (ILR) and presents an optimal algorithm for each. First, for the CSLRs, the magic-set method is refined in such a way that queries can be evaluated efficiently. Then, for the NILRS and ILRs, the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied.
