Search

Structural XQuery and XPath queries are often modeled by twig pattern queries (TPQs) specifying predicates on XML nodes and structural relationships to be satisfied between them. This paper considers a TPQ model extended by a specification of output and non-output query nodes since it complies with the XQuery and XPath semantics. There are two types of TPQ processing approaches: binary joins and holistic joins. The binary joins utilize a query plan of interconnected binary operators, whereas the holistic joins are based on one complex operator to process the whole query. In the recent years, the holistic joins have been considered as the state-of-the-art TPQ processing method. However, a thorough analytical and experimental comparison of binary and holistic joins has been missing despite an enormous research effort in this area. In this paper, we try to fill this gap. We introduce several improvements of the binary join operators which enable us to build a so-called fully-pipelined (FP) query plan for any TPQ with the specification of output and non-output query nodes. We analytically show that, for a class of queries, the proposed approach has the same time and space complexity as holistic joins, and we experimentally demonstrate that the proposed approach outperforms holistic joins in many cases.

Keyword search in XML and relational databases (RDB) has gained popularity as it provides a user-friendly way to explore structured data. Existing works on XML and RDB keyword search only rely on the structures of XML/RDB data and/or schemas, and this causes serious problems of returning incomplete answers, meaningless answers and overwhelming answers. In this paper, we identify the problems of existing keyword search methods and point out that the main reason of these problems is due to the unawareness of the Object-Relationship-Attribute (ORA) semantics in XML/RDB. We exploit the ORA semantics in XML and RDB, and capture these semantics by constructing the Object tree for XML, and the Object-Relationship-Mixed (ORM) data graph for RDB, respectively. Based on the Object tree and the ORM data graph, we propose an ORA-Semantics based keyword search in XML and RDB. Our semantic approach can avoid the problems of existing methods and improves the completeness and correctness of keyword search. In addition, we extend the keyword query language to include keywords that match the metadata, i.e., the names of tags in XML and the names of relations and attributes in RDB. These keywords reduce the ambiguities of queries and enable us to infer user' search intention more precisely. Finally, we incorporate aggregate functions and GROUPBY into keyword queries to retrieve statistical information from XML and RDB.

Scientific literatures contain some academic knowledge which is interesting or valuable but previously unknown. For instance, an algorithm A proposed in one article might have association with algorithm B in another article, while algorithm B is designed based on the definition of C in a third article. Thus we can deduce the relationship A-C based on A-B and B-C. There are also other kinds of academic knowledge such as association between two research communities, historical evolvement of a research topics, etc. But with the exponential growth of research articles that usually published in Portable Document Format (PDF), to discover and acquire potential knowledge poses many practical challenges. Existing algorithmic methods can hardly extend to handle diverse journals and layouts, nor scale up to process massive documents. As crowdsourcing has become a powerful paradigm for problem-solving especially for tasks that are difficult for computer to resolve solely, we state the problem of academic knowledge discovery and acquisition using an hybrid framework, integrating the accuracy of human workers and the speed of automatic algorithms. We briefly introduce a Platform for Academic kNowledge Discovery and Acquisition (PANDA), our current system implementation, as well as some preliminary achievements and promising future directions.

In the world of academia, research documents enable the sharing and dissemination of scientific discoveries. During these “big data” times, academic search engines are widely used to find the relevant research documents. Considering the domain of computer science, a researcher often inputs a query with a specific goal to find an algorithm or a theorem. However, to this date, the return result of most search engines is just as a list of related papers. Users have to browse the results, download the interesting papers and look for the desired information, which is obviously laborious and inefficient. In this paper, we present a novel academic search system, called PandaSearch, that returns the results with a fine-grained interface, where the results are well organized by different categories, such as definitions, theorems, lemmas, algorithms and figures. The key technical challenges in our system include the automatic identification and extraction of different parts in a research document, the discovery of the main topic phrases for a definition or a theorem, and the recommendation of related definitions or figures to elegantly satisfy the search intention of users. Based on this, we have built a user friendly search interface for users to conveniently explore the documents, and find the relevant information.

When users issue a query to a database, they have expectations about the results. If what they search for is unavailable in the database, the system will return an empty result or, worse, erroneous mismatch results.We call this problem the MisMatch Problem. In this paper, we solve the MisMatch problem in the context of XML keyword search. Our solution is based on two novel concepts that we introduce: Target Node Type and Distinguishability. Using these concepts, we develop a low-cost post-processing algorithm on the results of query evaluation to detect the MisMatch problem and generate helpful suggestions to users. Our approach has three noteworthy features: (1) for queries with the MisMatch problem, it generates the explanation, suggested queries and their sample results as the output to users, helping users judge whether the MisMatch problem is solved without reading all query results; (2) it is portable as it can work with any LCA-based matching semantics and is orthogonal to the choice of result retrieval method adopted; (3) it is lightweight in the way that it occupies a very small proportion of the whole query evaluation time. Extensive experiments on three real datasets verify the effectiveness, efficiency and scalability of our approach. A search engine called XClear has been built and is available at http://xclear.comp.nus.edu.sg.

Keyword search has been the major form of retrieval method in information retrieval system, and has become an important way for novice to explore data-centric XML and relational databases (RDB). Recent years have witnessed many approaches proposed for keyword search over XML and RDB. However, those approaches cannot intelligently exploit hidden semantics in XML or RDB, and thus encounter serious problems in processing keyword queries. In this paper, we point out mismatches between query answers returned by existing approaches and the common expectations in keyword search over XML and RDB. We analyze these mismatches and discover that the main reasons are due to the unawareness of semantics of object, relationship and attribute in databases. To capture these semantics, we construct Object Relationship (OR) data graph for XML and Object Relationship Mixed (ORM) data graph for RDB, and propose an intelligent keyword search based on OR and ORM data graph model to retrieve more informative answers. Finally, to further facilitate the usability of keyword search, we also show our ongoing work to enhance the expressive power of keyword queries. Particularly, we 1) enable users to explicitly indicate their search intentions by relation, attribute and tag names in keyword queries; 2) handle recursive relationships and identifier-dependency relationships (IDD) in databases; and 3) incorporate aggregate function into keyword queries so that users can explore databases with aggregate queries.

In this paper, we focus on efficient keyword query processing for XML data based on the SLCA and ELCA semantics. We propose a novel form of inverted lists for keywords which include IDs of nodes that directly or indirectly contain a given keyword. We propose a family of efficient algorithms that are based on the set intersection operation for both semantics. We show that the problem of SLCA/ELCA computation becomes finding a set of nodes that appear in all involved inverted lists and satisfy certain conditions. We also propose several optimization techniques to further improve the query processing performance. We have conducted extensive experiments with many alternative methods. The results demonstrate that our proposed methods outperform previous methods by up to two orders of magnitude in many cases.

The existing query languages for XML (e.g., XQuery) require professional programming skills to be formulated, however, such complex query languages burden the query processing. In addition, when issuing an XML query, users are required to be familiar with the content (including the structural and textual information) of the hierarchical XML, which is diffcult for common users. The need for designing user friendly interfaces to reduce the burden of query formulation is fundamental to the spreading of XML community. We present a twig-based XML graphical search system, called LotusX, that provides a graphical interface to simplify the query processing without the need of learning query language and data schemas and the knowledge of the content of the XML document. The basic idea is that LotusX proposes "position-aware" and "auto-completion" features to help users to create tree-modeled queries (twig pattern) by providing the possible candidates on-the-fly. In addition, complex twig queries (including order sensitive queries) are supported in LotusX. Furthermore, a new ranking strategy and a query rewriting solution are implemented to rank and rewrite the query effectively. We provide an online demo for LotusX system: http://datasearch.ruc.edu.cn:8080/LotusX.

Inspired by the great success of information retrieval (IR) style keyword search on the web, keyword search on XML has emerged recently. The difference between text database and XML database results in three new challenges: (1) Identify the user search intention, i.e. identify the XML node types that user wants to search for and search via. (2) Resolve keyword ambiguity problems: a keyword can appear as both a tag name and a text value of some node; a keyword can appear as the text values of different XML node types and carry different meanings. (3) As the search results are sub-trees of the XML document, new scoring function is needed to estimate its relevance to a given query. However, existing methods cannot resolve these challenges, thus return low result quality in term of query relevance. In this paper, we propose an IR-style approach which basically utilizes the statistics of underlying XML data to address these challenges. We first propose specific guidelines that a search engine should meet in both search intention identification and relevance oriented ranking for search results. Then based on these guidelines, we design novel formulae to identify the search for nodes and search via nodes of a query, and present a novel XML TF*IDF ranking strategy to rank the individual matches of all possible search intentions. Lastly, the proposed techniques are implemented in an XML keyword search engine called XReal, and extensive experiments show the effectiveness of our approach.

It is important to process the updates when nodes are inserted into or deleted from the XML tree. All the existing labeling schemes have high update cost, thus in this paper we propose a novel Compact Dynamic Binary String (CDBS) encoding to efficiently process the updates. CDBS has two important properties which form the foundations of this paper: (1) CDBS supports that codes can be inserted between any two consecutive CDBS codes with the orders kept and without re-encoding the existing codes; (2) CDBS is orthogonal to specific labeling schemes, thus it can be applied broadly to different labeling schemes or other applications to efficiently process the updates. We report our experimental results to show that our CDBS is superior to previous approaches to process updates in terms of the number of nodes to re-label and the time for updating.

With the rapid growth of on-line information available, text classification is becoming more and more important. kNN is a widely used text classification method of high performance. However, this method is inefficient because it requires a large amount of computation for evaluating the similarity between a test document and each training document. In this paper, we propose a fast kNN text classification approach based on pruning the training corpus. By using this approach, the size of training corpus can be condensed sharply so that time-consuming on kNN searching can be cut off significantly, and consequently classification efficiency can be improved substantially while classification performance is preserved comparable to that of without pruning. Effective, algorithm for text corpus pruning is designed. Experiments over the Reuters corpus are carried out, which validate the practicability of the proposed approach. Our approach is especially suitable for on-line text classification applications.

The increase in the use of XML (eXtensible Markup Language) makes the semistructured data more and more important on the Web. To exploit the full power of XML documents, a query language for semistructured data will be a promising and interesting application. However, the XQuery standard released by W3C is too difficult for common users to use. Some XML graphical query languages for semistructured data have been proposed but they are either too complex or too limited in use. We introduce a graphical query language for semistructured data, which we call GLASS. GLASS is developed on the base of ORA-SS data model, a semantically richer data model for semistructured data In GLASS, we combine the advantages of graphs and texts, which make the graphical language much clear and easy to use. The paper presents the notations and basic capabilities of GLASS via a series of examples with increasingly complexity. We also discuss some complex query examples such as order, group entity, negation and IF-THEN statement.

With the recent popularity of the Web, an enormous amount of information is now available online. Most Web documents available over the Web are in HTML format and are hierarchically structured in nature. How to query such Web documents based on their internal hierarchical structure becomes more and more important. We present a rule-based language called WebQL to support effective and flexible Web queries. Unlike other Web query languages, WebQL is a high level declarative query language with a logical semantics. It allows us to query Web documents based on their internal hierarchical structures. It supports not only negation and recursion, but also query result restructuring in a natural way. We also describe the implementation of the system that supports the WebQL query language.

Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. This article takes us another step towards solving this problem. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic structural and behavioral inheritance with overriding, conflict resolution and blocking. This article introduces the syntax of a language with these features. The language is restricted in the sense that we have omitted other object-oriented and deductive features that are now well understood, in order to make our contribution clearer. It then defines a class of databases, called well-defined databases , that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this article establishes a firm logical foundation for deductive object-oriented databases.