Search

A natural language interface (NLI) to databases is an interface that translates a natural language question to a structured query that is executable by database management systems (DBMS). However, an NLI that is trained in the general domain is hard to apply in the spatial domain due to the idiosyncrasy and expressiveness of the spatial semantics. Moreover, there are a wide range of database servers available, and a unilingual NLI model limits its practical usage. In this article, we propose to not only address the spatial domain generalization challenge, but also support multilingual back-end, i.e., supporting different query languages, such as SQL and Prolog. For the challenge of spatial semantics, we propose a spatial comprehension model that is able to recognize the meaning of spatial entities based on the semantics of context and effectively resolve the ambiguity given the spatial semantics. The spatial semantics learned from the spatial comprehension model is then injected to the natural language question to ease the burden of capturing the spatial-specific semantics. We also propose to add a prefix symbol to support the multilingual back-end (e.g., query languages). With our spatial comprehension model and symbol injections, our NLI for the spatial domain, named SpatialNLI, is able to capture the semantic structure of the question and translate it to the corresponding syntax of an executable query accurately. We also experimentally ascertain that SpatialNLI outperforms state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In a cloud environment, resources should be acquired quickly and automatically released at runtime. Traditional trajectory data partitions, indexing and query processing techniques are extended, so that they can take advantage of the cloud of large clusters of highly parallel processing capabilities. There are ways with trajectory data in the cloud database query processing. The advanced sensing techniques available today caused the existence of many types of trajectory datasets whose study can form a strong basis for decision making regarding a data context. Trajectory data generally includes trajectory classification, trajectory clustering, and trajectory associations and so on. All these tools need trajectory similarity measures to get comparisons in trajectory data. Some of the popular existing methods of trajectory similarity include Euclidean distance, semantic distance and there near variants. Each variant of these techniques exhibits notable differences in measurement of similarity and computational difficulty. This paper targeted to deal with this situation with the goal of lower computational efforts in trajectory similarity computations. A two‐phase trajectory similarity measure is defined. The first phase does point level analysis of trajectory points representing all trajectories and the following phase use the analysis to find the similarities. Using a hybrid similarity framework, new means for trajectory clustering and trajectory query processing are developed. From trajectory analysis followed by trajectory clustering, evaluation of cluster quality and processing of trajectory query are undertaken in this paper in different ways from the existing methods. All the proposed developments are tested with trajectory datasets with multiple attributes and the results are more favour to proposed framework than the existing ones. [ABSTRACT FROM AUTHOR]

Apache Sedona (formerly GeoSpark) is a new in-memory cluster computing system for processing large-scale spatial data, which extends the core of Apache Spark to support spatial datatypes, partitioning techniques, spatial indexes, and spatial operations (e.g. spatial range, nearest neighbor, and spatial join queries). Distance-based Join Queries (DJQs), like nearest neighbor join (kNNJQ) or closest pairs queries (kCPQ), are not supported by it. Therefore, in this paper, we investigate how to design and implement efficient DJQ distributed algorithms in Apache Sedona, using the most appropriate spatial partitioning and other optimization techniques. The results of an extensive set of experiments with real-world datasets are presented, demonstrating that the proposed kNNJQ and kCPQ distributed algorithms are efficient, scalable, and robust in Apache Sedona. Finally, Sedona is also compared to other similar cluster computing systems, showing the best performance for kCPQ and competitive results for kNNJQ. [ABSTRACT FROM AUTHOR]

We study the expressive power of the Lara language – a recently proposed unified model for expressing relational and linear algebra operations – both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. Since Lara is parameterized by a set of user-defined functions which allow to transform values in tables, known as extension functions , the exact expressive power of the language depends on how these functions are defined. We start by showing Lara to be expressive complete with respect to a syntactic fragment of relational algebra with aggregation (under the mild assumption that extension functions in Lara can cope with traditional relational algebra operations such as selection and renaming). We then look further into the expressiveness of Lara based on different classes of extension functions, and distinguish two main cases depending on the level of genericity that queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning pipelines. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions some versions of the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain. [ABSTRACT FROM AUTHOR]

This observational study examined the strategies that music students used to locate scores and media items in an academic library's online public access catalog (OPAC). During a usability test, investigators tracked students' search strategies and behaviors, and measured their success in identifying appropriate items. Students experienced briefer, less complicated, and more successful queries for media items than for music scores (the latter of which they struggled to find and properly identify). Class standing, library catalog experience, and prior library instruction had no significant effect on positive outcomes. Searches for music scores were highly sensitive to variations in query wording, and students frequently struggled to revise their searches. [ABSTRACT FROM AUTHOR]

The "Internet of Water" project will deploy 2,500 sensors along the Flemish river system, in Belgium. These sensors will be part of a monitoring system. This will produce an enormous amount of data, on which prediction and analysis tasks can be performed. To represent, store, and query river data, relational databases are normally used. However, this choice introduces an "impedance mismatch" between the conceptual representation (typically a graph) and the storage model (relational tables). To solve this problem, this article proposes to use graph databases. The Flemish river system is presented as a use case and the Neo4j graph database and its high‐level query language, Cypher, are used for storing and querying the data, respectively. A relational alternative is implemented over the PostgreSQL database. A collection of representative queries of interest for hydrologists is defined over both database implementations. [ABSTRACT FROM AUTHOR]

The number of databases as well as their size and complexity is increasing. This creates a barrier to use especially for non-experts, who have to come to grips with the nature of the data, the way it has been represented in the database, and the specific query languages or user interfaces by which data are accessed. These difficulties worsen in research settings, where it is common to work with many different databases. One approach to improving this situation is to allow users to pose their queries in natural language. In this work we describe a machine learning framework, Polyglotter, that in a general way supports the mapping of natural language searches to database queries. Importantly, it does not require the creation of manually annotated data for training and therefore can be applied easily to multiple domains. The framework is polyglot in the sense that it supports multiple different database engines that are accessed with a variety of query languages, including SQL and Cypher. Furthermore Polyglotter supports multi-class queries. Good performance is achieved on both toy and real databases, as well as a human-annotated WikiSQL query set. Thus Polyglotter may help database maintainers make their resources more accessible. [ABSTRACT FROM AUTHOR]

Secure semantic searching can search arbitrary query words semantically related to keywords over the encrypted data. However, most of the current schemes perform the matching after query semantic expansion on the plaintext. The existing works rarely support cross‐lingual searching that breaks the language barrier to allow a query issued in a lingual to retrieve the documents written in other languages. Meanwhile, most of the previous schemes are difficult to be applied to real‐time applications because of their poor efficiency. This letter designs an efficient cross‐lingual secure semantic searching scheme that performs semantic analysis, semantic matching, and relevance ranking on the ciphertext. The proposed scheme encrypts the language‐aligned word vectors of the keywords, and further calculates the semantic similarity between the encrypted vectors to perform clustering for the encrypted keywords. Therefore, the scheme uses the encrypted language‐aligned word vectors of query words to perform cross‐lingual semantic matching only with the cluster centre keywords to get encrypted keywords semantically related to the query, instead of scanning all the keywords, thus significantly improving the search efficiency. The scheme also realises the ciphertext relevance ranking algorithm to rank the documents. Experimental results show the practicability of the proposed scheme. [ABSTRACT FROM AUTHOR]

Summary Cutevariant is a graphical user interface (GUI)-based desktop application designed to filter variations from annotated VCF file. The application imports data into a local SQLite database where complex filter queries can be built either from GUI controllers or using a domain-specific language called Variant Query Language. Cutevariant provides more features than existing applications and is fully customizable thanks to a complete plugins architecture. Availability and implementation Cutevariant is distributed as a multiplatform client-side software under an open source license and is available at https://github.com/labsquare/cutevariant. [ABSTRACT FROM AUTHOR]

The persistent growth of big data applications has being raising new challenges in managing large volumes of datasets with high scalability, confidentiality protection, and flexible types of search queries. In this paper, we propose a secure design to disassemble the private dataset with the aim to store them across geographically distributed servers while supporting secure multi-client Boolean queries. In this design, the data owner encrypts the private database with the searchable index attributes. The encrypted dataset will be disassembled and distributed evenly across multiple servers by leveraging the property of a distributed index framework. By constructing an encryption structure, generating search tokens, and enabling parallel query, we show how the proposed design performs the secure while efficient Boolean search. These queries are not only limited to those initiated by the data owner but also can be extended to support multiple authorized clients, where each client is allowed to access a necessary part of the private database. In this stage, we advocate a non-interactive authorization scheme where data owner is not required to stay online to process the query request. Moreover, the query operation can be executed in parallel, which significantly improves the search efficiency. We formally characterize the leakage profile, which allow us to follow the existing security analysis method to demonstrate that our system can guarantee data confidentiality and query privacy. To validate our protocol, we implement a system prototype and evaluate the efficiency of our construction. Through experimental results, we demonstrate the effectiveness of our protocol in terms of data outsourcing time and Boolean query time. [ABSTRACT FROM AUTHOR]

In recent past, there has been a steep increase in the use of online platforms for the search of desired products. Real estate industry is no exception and has started initiating rent/sale of houses through online platforms. In this paper, we propose a deep neural network framework to facilitate automatic search of homes based on their floor plans. The salient features of this framework are that the query can be either an image (existing floor plan) or a sketch through a sketch pad interface. Our proposed framework automatically determines the type of query (image or sketch) and retrieves similar floor plan images from the database. The critical contributions of our proposed approach are: (1) a novel unified floor plan retrieval framework using multimodal query, i.e., an intuitive and convenient sketch query mode as well as a query by example mode ; (2) a conjunction of autoencoder, Cyclic GAN and CNN for the task of domain mapping and floor plan image retrieval. We have reported results of extensive experimentation and comparison with baseline results to establish the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

Highlights • An improvement-based method is proposed to identify the feedback types. • A novel negative feedback model which captures negative information is proposed. • Integrating positive and negative feedback model is explored to improve retrieval. • A content-based representativeness criterion is proposed and evaluated. • Performance of the proposed models is evaluated on several TREC datasets. Abstract Pseudo-relevance feedback (PRF) has evident potential for enriching the representation of short queries. Traditional PRF methods treat top-ranked documents as feedback, since they are assumed to be relevant to the query. However, some of these feedback documents may actually distract from the query topic for a range of reasons and accordingly downgrade PRF system performance. Such documents constitute negative examples (negative feedback) but could also be valuable in retrieval. In this paper, a novel framework of query language model construction is proposed in order to improve retrieval performance by integrating both positive and negative feedback. First, an improvement-based method is proposed to automatically identify the types of feedback documents (i.e. positive or negative) according to whether the document enhances the retrieval's effectiveness. Subsequently, based on the learned positive and negative examples, the positive feedback models and the negative feedback models are estimated using an Expectation-Maximization algorithm with the assumptions: the positive term distribution is affected by the context term distribution and the negative term distribution is affected by both the positive term distribution and the context term distribution (such that the positive feedback model upgrades the rankings of relevant documents and the negative feedback model prunes the irrelevant documents from a query). Finally, a content-based representativeness criterion is proposed in order to obtain the representative negative feedback documents. Experiments conducted on the TREC collections demonstrate that our proposed approach results in better retrieval accuracy and robustness than baseline methods. [ABSTRACT FROM AUTHOR]

Group skyline query is a powerful tool for optimal group analysis. Most of the existing group skyline queries select optimal groups by comparing the dominance relationship between aggregate-based points; such feature creates difficulties for users to specify an appropriate aggregate function. Besides, many significant groups that have great attractions to users in practice may be overlooked. To address these issues, the group skyline (GSky) query is formulated on the basis of a general definition of group dominance operator. While the existing GSky query algorithms are effective, there is still room for improvement in terms of progressiveness and efficiency. In this paper, we propose some new lemmas which facilitate direct generation of the GSky query results. Consecutively, we design a layered unit-based (LU) algorithm that applies a layered optimum strategy. Additionally, for the GSky query over the data that are dynamically produced and cannot be indexed, we propose a novel index-independent algorithm, called sorted-based progressive (SP) algorithm. The experimental results demonstrate the effectiveness, efficiency, and progressiveness of the proposed algorithms. By comparing with the state-of-the-art algorithm for the GSky query, our LU algorithm is more scalable and two orders of magnitude faster. [ABSTRACT FROM AUTHOR]

Abstract The Weak Dominance Drawing problem can be defined as follows: given a directed acyclic graph G , find two topological sorts, t X and t Y , minimizing the size of the intersection between them. The intersection of two topological sorts is defined as the set of ordered pair of vertices (u , v) such that t X (u) < t X (v) and t Y (u) < t Y (v). In this work we consider a variation of this problem, that we call One-Sided Weak Dominance Drawing , in which one of the topological sorts is given as input and we must find another topological sort minimizing the intersection set with the given one. This problem has been considered in the literature and its applications include index generation of competitive algorithms for reachability queries on very large graphs. In this paper we formalize the problem, describe one of its applications, show how the problem is currently tackled in the literature, prove that its decision version is NP-complete and determine a primal bound for it as a function of the dimension of G. [ABSTRACT FROM AUTHOR]

Abstract To address the problem of query-focused multi-document summarisation, we present a novel unsupervised pattern-enhanced approach for representing coherent topics across documents, as well as the query relevance, in order to generate topically coherent summaries that meet the information needs of users. The proposed model employs not only a pattern-enhanced topic model to generate discriminative and semantic rich representations for topics and documents, but also a pattern-based relevance model for the query relevance of sentences. With these dual pattern-based representations for sentences, we are able to integrate various indicative metrics, such as rational coverage of document topics and sentence relevance, into a unified model. When evaluated on the datasets of the document understanding conferences of 2006 and 2007, the proposed approach shows a performance improvement as compared to a number of state-of-the-art methods and unsupervised baseline systems. [ABSTRACT FROM AUTHOR]

Background: Studies have suggested that aphasia rates are different in men and women following stroke. One hypothesis says that men have more lateralized language function than women. Given unilateral stroke, this would lead to a prediction of men having higher aphasia rates than women. Another line of observations suggest that women are more severely affected by stroke, which could lead to a higher aphasia rate among women. An additional potential confounding variable could be age, given that women are typically older at the time of stroke. Methods & procedures: This study consists of two parts. First, a meta-analysis of the available reports of aphasia rates in the two sexes was conducted. A comprehensive literature search yielded 25 studies with sufficient information about both aphasia and gender. These studies included a total of 48,362 stroke patients for which aphasia rates were calculated. Second, data were extracted from an American health database (with 1,967,038 stroke patients), in order to include age and stroke severity into a regression analysis of sex differences in aphasia rates. Outcomes & results: Both analyses revealed significantly larger aphasia rates in women than in men (1.1–1.14 ratio). This speaks against the idea that men should be more lateralized in their language function. When age and stroke severity were included as covariates, sex failed to explain any aphasia rate sex difference above and beyond that which is explained by age differences at time of stroke. [ABSTRACT FROM AUTHOR]

Social networks have become a source of data which are of interest in all areas, and their querying and analysis is a hot topic in computer science. Our research group has developed a fuzzy extension of the Semantic Web query language SPARQL, called FSA-SPARQL ( Fuzzy Sets and Aggregators based SPARQL ). This extension provides mechanisms to express fuzzy queries against RDF data. FSA-SPARQL works with social networks. With this aim, FSA-SPARQL enables the transformation and fuzzification of social network API data. Fuzzification of social networks data is automatic and user-defined enabling a wide range of mechanisms for ranking and categorization, including sentiment analysis and topic detection. As a case study, FSA-SPARQL has been used to query three well-known social networks: Twitter, Foursquare and TMDb . [ABSTRACT FROM AUTHOR]

Search users rely on result captions including titles, snippets, and URLs to decide whether they should read and click a particular result or not. Snippet usually serves as a query-dependent summary of its corresponding landing page and is therefore treated as one of the most important factors in search interaction process. Although there exist many efforts in improving snippet generation algorithms and incorporating more powerful interaction functions into snippets, little attention is paid to the effect of text highlighting in user behaviors. The highlighting of query terms in search snippets has been regarded as a matter of course and whether there exists a better way in snippet text highlighting remains uninvestigated. In this paper, we try to find out whether the default strategy of highlighting query terms employed by most commercial search engines is the best for search users. Through carefully designed experiments, we show that the retrieval efficiency can be affected by different term-highlighting strategies without changes in snippet contents. We also propose an automatic method which adopts CRF to learn to highlight terms based on word embedding, Wikipedia, and snippet content information. Experimental results show that the proposed method could predict highlighted terms selected by crowd workers with moderate performance. [ABSTRACT FROM AUTHOR]

The article analizes characteristics, definition, constitution, and technologies adopted for designing and implementing ontologies within the Semantic Web framework. Therefore, it describes relationships between Web ontologies and Linked Open Data (LOD), Resource Description Framework (RDF) model, Web Ontology Language (WQL), Simple Protocol and RDF Query Language (SPARQL) and Uniform Resources Identifiers (URIs). The study deals with naming, lexicalizing, localization and serializing. It identifies the most used methodologies for developing Web ontologies. The work describes the method proposed by Stuart (2016). According to this author, this article considers decisions about ontologies methods design representing Argentine scientific and academic research. It underlines the importance of methodological stage in the creation process of applied ontologies to optimizing their capacity of automatic inference. [ABSTRACT FROM AUTHOR]

Tuple-independent and disjoint-independent probabilistic databases (TI- and DI-PDBs) represent uncertain data in a factorized form as a product of independent random variables that represent either tuples (TI-PDBs) or sets of tuples (DI-PDBs). When the user submits a query, the database derives the marginal probabilities of each output-tuple, exploiting the underlying assumptions of statistical independence. While query processing in TI- and DI-PDBs has been studied extensively, limited research has been dedicated to the problems of updating or deriving the parameters from observations of query results. Addressing this problem is the main focus of this article. We first introduce Beta Probabilistic Databases (B-PDBs), a generalization of TI-PDBs designed to support both (i) belief updating and (ii) parameter learning in a principled and scalable way. The key idea of B-PDBs is to treat each parameter as a latent, Beta-distributed random variable. We show how this simple expedient enables both belief updating and parameter learning in a principled way, without imposing any burden on regular query processing. Building on B-PDBs, we then introduce Dirichlet Probabilistic Databases (D-PDBs), a generalization of DI-PDBs with similar properties. We provide the following key contributions for both B- and D-PDBs: (i) We study the complexity of performing Bayesian belief updates and devise efficient algorithms for certain tractable classes of queries; (ii) we propose a soft-EM algorithm for computing maximum-likelihood estimates of the parameters; (iii) we present an algorithm for efficiently computing conditional probabilities, allowing us to efficiently implement B- and D-PDBs via a standard relational engine; and (iv) we support our conclusions with extensive experimental results. [ABSTRACT FROM AUTHOR]

Abstract In this paper, the problem of tree size reduction with guarantee of preserving distinguishability is studied. Given a query q and a tree T , evaluating q on T will output q (T) which is a set of nodes of T. Given two nodes a and b in T , they are said to be distinguished by some query q in T , iff exactly one of them belongs to q (T). Then, given a tree T , a query class L , and two disjoint node sets A and B of T , a subtree T ′ of T satisfies the condition of preserving distinguishability of T , iff (1) T ′ contains all nodes in A ∪ B , (2) for any node pair (a , b) ∈ A × B , if a and b can be distinguished by some query in L in T , they can also be distinguished by some query (not necessarily the same one) in L in T ′ , and (3) for any node pair (a , b) ∈ A × B and a query q ∈ L , if a and b can be distinguished by q in T ′ , they can also be distinguished by q in T. The tree size reduction problem considered by this paper is to determine whether there is a small enough subtree T ′ of T , such that for query class L and node sets A and B , T ′ preserves the distinguishability of T. In this paper, as an initial attempt of investigating this problem, fixing L to be a specific part of tree pattern queries which is an important practical query language on trees, the tree size reduction problem is shown to be NP- complete. [ABSTRACT FROM AUTHOR]

Abstract To date, widely implemented and full-featured query languages for building models in their native exchange formats do not exist. While interesting proposals exist for querying Industry Foundation Classes (IFC) models, their functionality is often incomplete and their semantics not precisely defined. With the introduction of the ifcOWL ontology as an equivalent to the IFC schema in the Web Ontology Language (OWL), an option to represent such models in RDF (Resource Description Framework, a general information modeling method) is provided, and such models can be queried using SPARQL (SPARQL Protocol and RDF Query Language). The size of data sets in complex building projects, however, renders the use of clear-text encoded RDF infeasible in many cases. A SPARQL implementation, compatible with ifcOWL , is proposed, directly atop a standardized binary serialization format for IFC building models. This novel format is the binary equivalent of traditional IFC serialization formats but with more compact storage and less overhead than the graph serialization in RDF. The format is based on ISO 10303-26 and relies on an open standard for organizing large amounts of data: Hierarchical Data Format version 5 (HDF5). Due to hierarchical partitioning and fixed-length records, only small subsets of the data are read to answer queries, improving efficiency. A prototypical implementation of the query engine is provided in the Python programming language. In several realistic use cases, the proposed system performs equivalent to or better than the state of the art in SPARQL querying on building models. For large datasets, the proposed storage format results in files that are 2–3 times smaller than the current, most concise, RDF databases while offering a platform-neutral, containerized exchange file. Highlights • A SPARQL query engine is presented that operates directly on IFC building models. • The models are in a binary format suitable for efficiently retrieving subsets. • In several cases, the system performs equivalent or better to the state of the art. [ABSTRACT FROM AUTHOR]

In the setting of dynamic complexity, the goal of a dynamic program is to maintain the result of a fixed query for an input database that is subject to changes, possibly using additional auxiliary relations. In other words, a dynamic program updates a materialized view whenever a base relation is changed. The update of query result and auxiliary relations is specified using first-order logic or, equivalently, relational algebra. The original framework by Patnaik and Immerman only considers changes to the database that insert or delete single tuples. This article extends the setting to definable changes, also specified by first-order queries on the database, and generalizes previous maintenance results to these more expressive change operations. More specifically, it is shown that the undirected reachability query is first-order maintainable under single-tuple changes and first-order defined insertions, likewise the directed reachability query for directed acyclic graphs is first-order maintainable under insertions defined by quantifier-free first-order queries. These results rely on bounded bridge properties, which basically say that, after an insertion of a defined set of edges, for each connected pair of nodes there is some path with a bounded number of new edges. While this bound can be huge, in general, it is shown to be small for insertion queries defined by unions of conjunctive queries. To illustrate that the results for this restricted setting could be practically relevant, they are complemented by an experimental study that compares the performance of dynamic programs with complex changes, dynamic programs with single changes, and with recomputation from scratch. The positive results are complemented by several inexpressibility results. For example, it is shown that—unlike for single-tuple insertions—dynamic programs that maintain the reachability query under definable, quantifier-free changes strictly need update formulas with quantifiers. Finally, further positive results unrelated to reachability are presented: it is shown that for changes definable by parameter-free first-order formulas, all LOGSPACE-definable (and even AC1-definable) queries can be maintained by first-order dynamic programs. [ABSTRACT FROM AUTHOR]

The problem of querying RDF data is a central issue for the development of the Semantic Web. The query language SPARQL has become the standard language for querying RDF since its W3C standardization in 2008. However, the 2008 version of this language missed some important functionalities: reasoning capabilities to deal with RDFS and OWL vocabularies, navigational capabilities to exploit the graph structure of RDF data, and a general form of recursion much needed to express some natural queries. To overcome these limitations, a new version of SPARQL, called SPARQL 1.1, was released in 2013, which includes entailment regimes for RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. Unfortunately, there are a number of useful navigation patterns that cannot be expressed in SPARQL 1.1, and the language lacks a general mechanism to express recursive queries. To the best of our knowledge, no efficient RDF query language that combines the above functionalities is known. It is the aim of this work to fill this gap. To this end, we focus on a core fragment of the OWL 2 QL profile of OWL 2 and show that every SPARQL query enriched with the above features can be naturally translated into a query expressed in a language that is based on an extension of Datalog, which allows for value invention and stratified negation. However, the query evaluation problem for this language is highly intractable, which is not surprising since it is expressive enough to encode some inherently hard queries. We identify a natural fragment of it, and we show it to be tractable and powerful enough to define SPARQL queries enhanced with the desired functionalities. [ABSTRACT FROM AUTHOR]

Abstract Let D = { T 1 , T 2 , … , T D } be a collection of D documents having n characters in total. Given two patterns P and Q , and an integer k > 0 , we consider the following queries. • top - k forbidden pattern query: Among all documents containing P , but not Q , report the k documents most relevant to P. • top - k two pattern query: Among all documents that contain both P and Q , report the k documents most relevant to P. For the above two queries, we provide a linear space index with O (| P | + | Q | + n k) query time, under some standard relevance functions such as PageRank and TermFrequency. The document listing version of the above two problems asks to report all t documents that either contain P , but not Q , or contain both P and Q , depending on the query type. As a corollary of the top- k result, we obtain a linear space and O (| P | + | Q | + n t) query time solution for the document listing problems. We conjecture that any significant improvement over these results is highly unlikely. We also consider the scenario when the query consists of more than two patterns. Finally, we present space-efficient indexes for these problems. [ABSTRACT FROM AUTHOR]

Model transformation is a key enabling technology of Model-Driven Engineering (MDE). Existing model transformation languages are shaped by and for MDE practitioners—a user group with needs and capabilities which are not necessarily characteristic of modelers in general. Consequently, these languages are largely ill-equipped for adoption by end-user modelers in areas such as requirements engineering, business process management, or enterprise architecture. We aim to introduce a model transformation language addressing the skills and requirements of end-user modelers. With this contribution, we hope to broaden the application scope of model transformation and MDE technology in general. We discuss the profile of end-user modelers and propose a set of design guidelines for model transformation languages addressing them. We then introduce Visual Model Transformation Language (VMTL) following these guidelines. VMTL draws on our previous work on the usability-oriented Visual Model Query Language. We implement VMTL using the Henshin model transformation engine, and empirically investigate its learnability via two user experiments and a think-aloud protocol analysis. Our experiments, although conducted on computer science students exhibiting only some of the characteristics of end-user modelers, show that VMTL compares favorably in terms of learnability with two state-of the-art model transformation languages: Epsilon and Henshin. Our think-aloud protocol analysis confirms many of the design decisions adopted for VMTL, while also indicating possible improvements. [ABSTRACT FROM AUTHOR]

We survey foundational features underlying modern graph query languages. We first discuss two popular graph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges and property graphs, where nodes and edges can further have attributes. Next we discuss the two most fundamental graph querying functionalities: graph patterns and navigational expressions. We start with graph patterns, in which a graph-structured query is matched against the data. Thereafter, we discuss navigational expressions, in which patterns can be matched recursively against the graph to navigate paths of arbitrary length; we give an overview of what kinds of expressions have been proposed and how they can be combined with graph patterns.We also discuss several semantics under which queries using the previous features can be evaluated, what effects the selection of features and semantics has on complexity, and offer examples of such features in three modern languages that are used to query graphs: SPARQL, Cypher and Gremlin. We conclude by discussing the importance of formalisation for graph query languages; a summary of what is known about SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an outline of possible future directions for the area. [ABSTRACT FROM AUTHOR]

Abstract In the past decade, there has been an increasing need for semantic-aware data search and indexing in textual (structured and NoSQL) databases, as full-text search systems became available to non-experts where users have no knowledge about the data being searched and often formulate query keywords which are different from those used by the authors in indexing relevant documents, thus producing noisy and sometimes irrelevant results. In this paper, we address the problem of semantic-aware querying and provide a general framework for modeling and processing semantic-based keyword queries in textual databases, i.e., considering the lexical and semantic similarities/disparities when matching user query and data index terms. To do so, we design and construct a semantic-aware inverted index structure called SemIndex , extending the standard inverted index by constructing a tightly coupled inverted index graph that combines two main resources: a semantic network and a standard inverted index on a collection of textual data. We then provide a general keyword query model with specially tailored query processing algorithms built on top of SemIndex , in order to produce semantic-aware results, allowing the user to choose the results' semantic coverage and expressiveness based on her needs. To investigate the practicality and effectiveness of SemIndex , we discuss its physical design within a standard commercial RDBMS allowing to create, store, and query its graph structure, thus enabling the system to easily scale up and handle large volumes of data. We have conducted a battery of experiments to test the performance of SemIndex , evaluating its construction time, storage size, query processing time, and result quality, in comparison with legacy inverted index. Results highlight both the effectiveness and scalability of our approach. [ABSTRACT FROM AUTHOR]

We study the problem of learning description logic (DL) ontologies in Angluin et al.'s framework of exact learning via queries. We admit membership queries (\is a given subsumption entailed by the target ontology?") and equivalence queries (\is a given ontology equivalent to the target ontology?"). We present three main results: (1) ontologies formulated in (two relevant versions of) the description logic DL-Lite can be learned with polynomially many queries of polynomial size; (2) this is not the case for ontologies formulated in the description logic EL, even when only acyclic ontologies are admitted; and (3) ontologies formulated in a fragment of EL related to the web ontology language OWL 2 RL can be learned in polynomial time. We also show that neither membership nor equivalence queries alone are sufficient in cases (1) and (3). [ABSTRACT FROM AUTHOR]

With the development of the Internet of Things (IoT), the industrial vehicle ad hoc networks are revolving into the Internet of Industrial Vehicles (IoIV). Due to the popularity of the geographical devices used on the Industrial vehicle, location-based information is extensively available in IoIV. This development calls for spatial keyword queries (SKQ), which takes into account both the locations and textual descriptions of objects. This paper addresses the issue of processing SKQ in IoIV environment, which focuses on two types of SKQ queries, namely Boolean kNN Queries and Top-k Queries. A general air index called Extended Spatial Keyword query index in IoIV environment (ESKIV) is proposed, which supports both network space pruning and textual pruning simultaneously. Based on ESKIV, efficient algorithms are designed to deal with these two types of SKQ respectively. The proposed ESKIV also can be used to deal with other kinds of queries, such as range SKQ. Finally, extensive simulations are conducted to demonstrate the efficiency of our ESKIV index and the corresponding query processing algorithms. [ABSTRACT FROM AUTHOR]

Process-oriented data analysis techniques allow organizations to understand how their processes operate, where modifications are needed and where enhancements are possible. A recurrent task in any process analysis technique is querying. Process data querying allows analysts to easily explore the data with the intent of getting insights about the execution of business processes. The current generation of process query languages targets data scientists. However, there is a need to a query language to support domain analysts who may be inexperienced with database technologies. This paper addresses this challenge by proposing a natural language interface that assists the end-users in querying the stored event data. The interface takes a natural language query from the user, automatically constructs a corresponding structured query to be executed over the stored event data. We use graph based storage techniques, namely labeled property graphs, which allow to explicitly model event data relationships. As an executable query language, we use the Cypher language which is widely used for querying property graphs. The approach has been implemented and evaluated using two publicly available event logs. • We proposed a natural language interface for querying process execution data from natural language. • We presents a Labeled Graph metamodel for stroing process data. • We proposed a hybrid pipline to automatically constructing Cypher queries from natural language. • Our NLI system is hybrid and combines machine learning and rule-based approaches. • We defined a set of general intent patterns that are domain-independent. • We evaluated the proposed system with more than 530 natural language queries. [ABSTRACT FROM AUTHOR]

The recently proposed Geometric Monitoring (GM) method has provided a general tool for the distributed monitoring of arbitrary non-linear queries over streaming data observed by a collection of remote sites, with numerous practical applications. Unfortunately, GM-based techniques can suffer from serious scalability issues with increasing numbers of remote sites. In this paper, we propose novel techniques that effectively tackle the aforementioned scalability problems by exploiting a carefully designed sample of the remote sites for efficient approximate query tracking. Our novel sampling-based scheme utilizes a sample of cardinality proportional to N (compared to N for the original GM and its variants), where N is the number of sites in the network, to perform the monitoring process. Our extensive experimental evaluation and comparative analysis over a variety of real-life data streams demonstrates that our sampling-based techniques can significantly reduce the communication cost during distributed monitoring with controllable, predefined accuracy guarantees. In that, we manage to scale the monitoring of any given non-linear function on much higher network scales which had not been reached by any GM related method or variant so far. [ABSTRACT FROM AUTHOR]

We present a new graph compressor that works by recursively detecting repeated substructures and representing them through grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. Specific queries such as reachability between two nodes or regular path queries can be evaluated in linear time (or quadratic times, respectively), over the grammar, thus allowing speed-ups proportional to the compression ratio. [ABSTRACT FROM AUTHOR]

Background: Clinical decision-support systems (CDSS) are designed to solve knowledge-intensive tasks for supporting decision-making processes. Although many approaches for designing CDSS have been proposed, due to high implementation costs, as well as the lack of interoperability features, current solutions are not well-established across different institutions. Recently, the use of standardized formalisms for knowledge representation as terminologies as well as the integration of semantically enriched clinical information models, as openEHR Archetypes, and their reuse within CDSS are theoretically considered as key factors for reusable CDSS.Objective: We aim at developing and evaluating an openEHR based approach to achieve interoperability in CDSS by designing and implementing an exemplary system for automated systemic inflammatory response syndrome (SIRS) detection in pediatric intensive care.Methods: We designed an interoperable concept, which enables an easy integration of the CDSS across different institutions, by using openEHR Archetypes, terminology bindings and the Archetype Query Language (AQL). The practicability of the approach was tested by (1) implementing a prototype, which is based on an openEHR based data repository of the Hannover Medical School (HaMSTR), and (2) conducting a first pilot study.Results: We successfully designed and implemented a CDSS with interoperable knowledge bases and interfaces by reusing internationally agreed-upon Archetypes, incorporating LOINC terminology and creating AQL queries, which allowed retrieving dynamic facts in a standardized and unambiguous form. The technical capabilities of the system were evaluated by testing the prototype on 16 randomly selected patients with 129 days of stay, and comparing the results with the assessment of clinical experts (leading to a sensitivity of 1.00, a specificity of 0.94 and a Cohen's kappa of 0.92).Conclusions: We found the use of openEHR Archetypes and AQL a feasible approach to bridge the interoperability gap between local infrastructures and CDSS. The designed concept was successfully transferred into a clinically evaluated openEHR based CDSS. To the authors' knowledge, this is the first openEHR based CDSS, which is technically reliable and capable in a real context, and facilitates clinical decision-support for a complex task. Further activities will comprise enrichments of the knowledge base, the reasoning processes and cross-institutional evaluations. [ABSTRACT FROM AUTHOR]

One of the challenges of managing an RDF database is predicting performance of SPARQL queries before they are executed. Performance characteristics, such as the execution time and memory usage, can help data consumers identify unexpected long-running queries before they start and estimate the system workload for query scheduling. Extensive works address such performance prediction problem in traditional SQL queries but they are not directly applicable to SPARQL queries. In this paper, we adopt machine learning techniques to predict the performance of SPARQL queries. Our work focuses on modeling features of a SPARQL query to a vector representation. Our feature modeling method does not depend on the knowledge of underlying systems and the structure of the underlying data, but only on the nature of SPARQL queries. Then we use these features to train prediction models. We propose a two-step prediction process and consider performances in both cold and warm stages. Evaluations are performed on real world SPRAQL queries, whose execution time ranges from milliseconds to hours. The results demonstrate that the proposed approach can effectively predict SPARQL query performance and outperforms state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

The aim of this research was to select and identify user influence on Twitter data. In identification stage, the method proposed in this study was matrix Twitter approach, sentiment analysis, and characterization of the opinion leader. The importan characteristics included external communication, accessibility, and innovation. Based on these characteristics and information from Twitter data through matrix Twitter and sentiment analysis, a algorithm of skyline query was constructed for the selection stage. Algorithm of skyline query selected user influence by comparing with other users according to values of each characteristic. Thus, user influence was indicated as user that was not influenced b y other users in any combination of skyline objects. The use of MapReduce framework model in identification and selection stage, support whole operation where Twitter had big size data and rapid changes. The results in identification and selection of user influence exhibited that MapReduce framework minimized the execution time, whereas in parallel skyline query could reveal user influence on the data. [ABSTRACT FROM AUTHOR]

Let P be a set of n uncertain points in R d , where each point p i ∈ P is associated with a real value v i and exists with probability α i ∈ ( 0 , 1 ] independently of the other points. We present algorithms for building an index on P so that for a d -dimensional query rectangle ρ , the expected maximum value or the most-likely maximum value in ρ can be computed quickly. Our main contributions include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension. (ii) A conditional lower bound for most-likely range-max queries, based on the conjectured hardness of the set-intersection problem. (iii) A near-linear-size index for estimating the expected range-max value within approximation factor 1/2 in O ( polylog ( n ) ) time. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top- k values of the range-max. [ABSTRACT FROM AUTHOR]

We optimize multiway equijoins on relational tables using degree information. We give a new bound that uses degree information to more tightly bound the maximum output size of a query. On real data, our bound on the number of triangles in a social network can be up to 95 times tighter than existing worst case bounds. We show that using only a constant amount of degree information, we are able to obtain join algorithms with a running time that has a smaller exponent than existing algorithms-for any database instance. We also show that this degree information can be obtained in nearly linear time, which yields asymptotically faster algorithms in the serial setting and lower communication cost algorithms in the MapReduce setting. In the serial setting, the data complexity of join processing can be expressed as a function O(INx + OUT) in terms of input size IN and output size OUT in which x depends on the query. An upper bound for x is given by the fractional hypertreewidth. We are interested in situations in which we can get algorithms for which x is strictly smaller than the fractional hypertreewidth. We say that a join can be processed in subquadratic time if x < 2. Building on the AYZ algorithm for processing cycle joins in quadratic time, for a restricted class of joins which we call 1-series-parallel graphs, we obtain a complete decision procedure for identifying subquadratic solvability (subject to the 3-SUM problem requiring quadratic time). Our 3-SUM based quadratic lower bound is tight, making it the only known tight bound for joins that does not require any assumption about the matrix multiplication exponent ω. We also give a MapReduce algorithm that meets our improved communication bound and handles essentially optimal parallelism. [ABSTRACT FROM AUTHOR]

SPARQL is the standard query language for RDF data. The distinctive feature of SPARQL is the OPTIONAL operator, which allows for partial answers when complete answers are not available due to lack of information. However, optional matching is computationally expensive—query answering is PSPACE-complete. The well-designed fragment of SPARQL achieves much better computational properties by restricting the use of optional matching—query answering becomes coNP-complete. On the downside, well-designed SPARQL captures far from all real-life queries—in fact, only about half of the queries over DBpedia that use OPTIONAL are well-designed. In the present paper, we study queries outside of well-designed SPARQL. We introduce the class of weakly well-designed queries that subsumes well-designed queries and includes most common meaningful non-well-designed queries: our analysis shows that the new fragment captures over 99% of DBpedia queries with OPTIONAL. At the same time, query answering for weakly well-designed SPARQL remains coNP-complete, and our fragment is in a certain sense maximal for this complexity. We show that the fragment’s expressive power is strictly in-between well-designed and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence. [ABSTRACT FROM AUTHOR]

It is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, databases that include designated predicates that hold the active domain, which we call product databases, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guardedbased existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the query languages in question. [ABSTRACT FROM AUTHOR]

A large distributed data acquisition system based on PXI/PXIe technology has been implemented on EAST tokamak. Now the whole data system has more than 60 data acquisition units and more than 3000 raw channels, and the maximum data throughput is about 5GBytes/s. Most of the acquired data are continuously stored into MDSplus Wan et al. database, moreover the calculated and analyzed data are also saved into MDSplus. In case of long-term discharge mode, the raw data of one shot is more than 1TBytes, and the total data of one campaign is more than 100TBytes. MDSplus is helpful to store tokamak experiment discharge data, and the scientific data are saved into database by shot and tree, and it is easy to know the signal information of one shot or tree. However, it is difficult to get the general metadata information of all the shots and trees. Even if we can read the information by some scripts, but it is not so convenient and the data retrieval speed is slow. So we have planned to design a data statistics and retrieval system for EAST MDSplus data system, which can provide all the metadata information of all the trees such as signal name, sampling rate, data size, data available or not, and so on, basing on these metadata the system can give detailed statistics and reports automatically by some pre-defined model, which can help users to grasp the status and schema of all the data. The system has been developed based on apache/mysql/php framework and the PCIe SSD storage is adopted to promote the database access speed. The design details will be given in the paper. [ABSTRACT FROM AUTHOR]

We present a cheating-sensitive quantum protocol for Privacy-Preserving Nearest Neighbor Query based on Oblivious Quantum Key Distribution and Quantum Encryption. Compared with the classical related protocols, our proposed protocol has higher security, because the security of our protocol is based on basic physical principles of quantum mechanics, instead of difficulty assumptions. Especially, our protocol takes single photons as quantum resources and only needs to perform single-photon projective measurement. Therefore, it is feasible to implement this protocol with the present technologies. [ABSTRACT FROM AUTHOR]

We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraphs that asks an almost optimal number of queries. [ABSTRACT FROM AUTHOR]

Large-scale distributed computing environments provide a vast amount of heterogeneous computing resources from different sources for resource sharing and distributed computing. Discovering appropriate resources in such environments is a challenge which involves several different subjects. In this paper, we provide an investigation on the current state of resource discovery protocols, mechanisms, and platforms for large-scale distributed environments, focusing on the design aspects. We classify all related aspects, general steps, and requirements to construct a novel resource discovery solution in three categories consisting of structures, methods, and issues. Accordingly, we review the literature, analyzing various aspects for each category. [ABSTRACT FROM AUTHOR]

In this paper, we study a new type of indoor queries, called the indoor trip planning query (iTPQ). We have observed that the existing methods for outdoor spaces cannot be applied directly to indoor spaces, due to the difference in the underlying networks. Outdoor spaces, which are normally represented as spatial road networks, are commonly modelled as a graph. In contrast, indoor spaces have distinct features (e.g. rooms, doors, hallways) that do not exist in road networks. So far, no specific solutions have been proposed for iTPQ. Even if outdoor techniques are revised for iTPQ, they fail to process iTPQ efficiently. In this paper, we propose an indoor-specific technique, based on the indoor VIP-Tree, called the VIP-Tree neighbor expansion (VNE) method, that also includes new pruning techniques in both pre-processing and query processing phases. Our experimental results show that our proposed method VNE outperforms other indoor and outdoor algorithms by several orders of magnitude in terms of processing time with low indexing cost. [ABSTRACT FROM AUTHOR]

In recent years, many studies on computational linguistics have employed the Web as source for research. Specifically, the distribution of textual data in the Web is used to drive linguistic analyses in tasks such as information extraction, knowledge acquisition or natural language processing. For these purposes, commercial Web search engines are commonly used as the low-entry-cost way to access Web data and, more specifically, to estimate the distribution of the entity(ies) of interest from the hit count the search engines provide when querying such entities. Even though several studies have evaluated the effectiveness of Web search engines as information retrieval tools from the perspective of the end users, few authors have assessed the suitability of hit counts as research tools in computational linguistics; moreover, studies so far have focused on the most well-known search engines (typically Google, Bing and Yahoo!), and neglected potentially interesting alternatives that have recently surfaced. To fill this gap, in this work, we first compile and survey the general-purpose search engines that are currently available. Then, we evaluate the suitability of the hit counts they provide under several perspectives that are relevant for computational linguistics: flexibility of the query language, linguistic coherence, mathematical coherence and temporal consistency. The results of our survey show that, even though the choice of a particular search engine has been generally ignored by researchers relying on Web data, there are significant quality differences between the hit counts of current search engines, and that the most well-known and widely-used search engines do not provide the best results. In this respect, we also identify the search engines whose hit counts are best suited for research. [ABSTRACT FROM AUTHOR]

We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by straight-line context free tree grammars (which are also known as tree straight-line programs or TSLPs). Although SLPs may be exponentially more succinct than TSLPs, we show that many simple tree queries can still be performed efficiently on SLPs, such as computing the height of a tree, tree navigation, or evaluation of Boolean expressions. Other problems on tree traversals turn out to be intractable, e.g. pattern matching and evaluation of tree automata. These problems can be still solved in polynomial time for TSLPs. [ABSTRACT FROM AUTHOR]

An enterprise database contains a global, integrated, and consistent representation of a company’s data. Multi-level modeling facilitates the definition and maintenance of such an integrated conceptual data model in a dynamic environment of changing data requirements of diverse applications. Multi-level models transcend the traditional separation of class and object with clabjects as the central modeling primitive, which allows for a more flexible and natural representation of many real-world use cases. In deep instantiation, the number of instantiation levels of a clabject or property is indicated by a single potency. Dual deep modeling (DDM) differentiates between source potency and target potency of a property or association and supports the flexible instantiation and refinement of the property by statements connecting clabjects at different modeling levels. DDM comes with multiple generalization of clabjects, subsetting/specialization of properties, and multi-level cardinality constraints. Examples are presented using a UML-style notation for DDM together with UML class and object diagrams for the representation of two-level user views derived from the multi-level model. Syntax and semantics of DDM are formalized and implemented in F-Logic, supporting the modeler with integrity checks and rich query facilities. [ABSTRACT FROM AUTHOR]

Session search, the task of document retrieval for a series of queries in a session, has been receiving increasing attention from the information retrieval research community. Session search exhibits the properties of rich user-system interactions and temporal dependency. These properties lead to our proposal of using partially observable Markov decision process to model session search. On the basis of a design choice schema for states, actions and rewards, we evaluate different combinations of these choices over the TREC 2012 and 2013 session track datasets. According to the experimental results, practical design recommendations for using PODMP in session search are discussed. [ABSTRACT FROM AUTHOR]

A business process or workflow is an assembly of tasks that accomplishes a business goal. Business process management is the study of the design, configuration/implementation, enactment and monitoring, analysis, and re-design of workflows. The traditional methodology for the re-design and improvement of workflows relies on the well-known sequence of extract, transform and load (ETL), data/process warehousing and online analytical processing (OLAP) tools. In this paper, we study the ad hoc queryiny of process enactments for (data-centric) business processes, bypassing the traditional methodology for more flexibility in querying. We develop an algebraic query language based on "incident patterns" with four operators inspired from Business Process Model and Notation (BPMN) representation, allowing the user to formulate ad hoc queries directly over workflow logs. A formal semantics of this query language, a preliminary query evaluation algorithm, and a group of elementary properties of the operators are provided. [ABSTRACT FROM AUTHOR]