Search

We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query $q$, we consider the following two problems: given as input an incomplete database $D$, (a) return the number of completions of $D$ that satisfy $q$; or (b) return the number of valuations of the nulls of $D$ yielding a completion that satisfies $q$. We obtain dichotomies between \#P-hardness and polynomial-time computability for these problems when $q$ is a self-join-free conjunctive query, and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in $D$ (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: for instance, while the latter is always in \#P, we prove that the former is not in \#P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes., Comment: 51 pages, including 43 pages of main text. Extended version of arXiv:1912.11064. Up to the stylesheet, page/environment numbering, minor formatting, and publisher-induced changes, this is the exact content of the paper in ACM Transactions on Computational Logic

Database tuples can be seen as players in the game of jointly realizing the answer to a query. Some tuples may contribute more than others to the outcome, which can be a binary value in the case of a Boolean query, a number for a numerical aggregate query, and so on. To quantify the contributions of tuples, we use the Shapley value that was introduced in cooperative game theory and has found applications in a plethora of domains. Specifically, the Shapley value of an individual tuple quantifies its contribution to the query. We investigate the applicability of the Shapley value in this setting, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.

Mobile cloud computing has become an important technology for mobile services. It overcomes physical limitations of mobile devices towards flexible and scalable mobile services. When using mobile clouds, people usually upload and store their data in cloud servers, and access the data through mobile devices from anywhere. As the privacy of the sensitive data is the major concern of users, the data is often encrypted before storing in cloud servers. However, the flexibility using the data is thereby affected, such as a Boolean search over the encrypted data, or ranking search results. To address these problems, in this paper we first propose a novel multi-user Boolean keyword search scheme (MBKSS) to achieve a rapid Boolean query outcome, while eliminating query interactions between users and the data owner. To rank search results and protect the privacy of relevance scores between files and keywords, we design a new homomorphic cryptosystem with partial decryption, which could be used as a basis for constructing a fast ranking search protocol (FRSP). A comprehensive security analysis shows that the proposed MBKSS and FRSP can achieve secure Boolean search and ranking. The experimental results demonstrate that the proposed MBKSS and FRSP are efficient and suitable for mobile devices.

Systematic reviews are comprehensive literature reviews that target a highly focused research question. In the medical domain, complex Boolean queries are used to identify studies. To ensure comprehensiveness, all studies retrieved are screened for inclusion or exclusion in the review. Developing Boolean queries for this task requires the expertise of trained information specialists. However, even for these expert searchers, query formulation can be difficult and lengthy: especially when dealing with areas of medicine that they may not be knowledgeable about. To this end, two computational adaptations of methods information specialists use to formulate Boolean queries have been proposed in prior work. These adaptations can be used to assist information specialists by providing a good starting point for query development. However, a number of limitations with these computational methods have been raised, and a comparison between them has not been made. In this study, we address the limitations of previous work and evaluate the two. We found that, between the two computational adaptions, the objective method is more effective than the conceptual method for query formulation alone, however, the conceptual method provides a better starting point for manual query refinement. This work helps to inform those building search tools that assist with systematic review construction.

In traditional public key searchable encryption (PKSE), a data owner (writer) utilizes data user’s (reader) public key to build ciphertexts. Thus, to share D data items (W keywords per item) with R readers, a writer suffers from $$O(R \cdot D \cdot W)$$ computational overhead. Researchers then offer numerous schemes supporting multiple readers with optimal overhead, i.e., $$O(D \cdot W)$$ . However, these schemes support either a single-keyword search or multi-keyword search in single-writer multi-reader (SWMR) setting where a writer could share data with the known set of readers. On the other hand, the existing multi-writer multi-reader (MWMR) PKSE offers Boolean search but suffers from $$O(R \cdot D \cdot W)$$ computational overhead for each writer. We observe applications desiring PKSE where writers could share data with the unknown set of readers and readers could perform search across data for Boolean query. Since the existing literature lacks such schemes, we propose a multi-writer multi-reader Boolean keyword searchable encryption (MWMR-BKSE) where the separate sets of registered readers and writers are prepared. Once registered, the writer could compute ciphertexts without knowing the potential readers and the readers could search across data at any time. The computational overhead on each writer is optimal $$O(D \cdot W)$$ . Additionally, a deregistered client would not be able to further write or read data. With MWMR-BKSE, we offer a Boolean keyword search utilizing key policy attribute-based encryption. The security of ciphertext against chosen keyword attack is proved using full security model. With the detailed theoretical analysis and extensive simulations on real-world datasets, we demonstrate the effectiveness of MWMR-BKSE.

We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In Koutris and Wijsen (ACM Trans. Database Syst. 42(2), 9:1–9:45, 2017), the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this article, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.

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.

Resilience problem is defined on a database d, given a boolean query q where q ( d ) is initially t r u e , and an integer k, it is to find the tuple set d ′ of smallest size such that the query result q ( d ∖ d ′ ) becomes f a l s e . As a potential explanation of a specified query, resilience plays a fundamental and important role in query explanation, database debugging and error tracing. Complexity results of resilience decision on relational algebraic queries have been studied previously. In this paper, we investigate the resilience decision problem on aggregation queries. New results on the hardness are provided. We show that, this problem is polynomially intractable on nested COUNT and SUM query both under data complexity and parametric complexity, and even it is NP - hard to approximate it within a constant ratio under the active domain constraint.

This thesis explores and investigates query automation methods and tools to support more effective study retrieval for the creation of medical systematic reviews. A systematic review is a synthesis of very high-quality medical studies with a stringent protocol to guide creation with minimal bias and error. Modern medicine practice and healthcare policies rely heavily on systematic reviews in order to make decisions on the best available evidence.Systematic review creation is often highly time-intensive and costly. Thus there has been much attention to attempt to automate phases in the creation of a systematic review. In this context, the definition of automation is the encoding of manual tasks into computational procedures. Existing automation research has primarily focused on the phase concerned with the critical appraisal of studies. Prior research has attempted to automate this appraisal phase by, for example, simulating human appraisal, (re-)ranking the retrieved studies, and classifying relevant studies, among others. A major drawback of these approaches is that they all rely on the initial search's retrieval effectiveness, which is contingent on the query's quality. We follow a fresh, new direction of research by investigating methods for query automation.In investigating automatic methods for building effective queries for systematic review creation, this thesis develops three main areas of enquiry: (i) query formulation: the development of Boolean queries suitable for systematic review literature search, (ii) query refinement: the iterative process of improving the search effectiveness of a Boolean query suitable for systematic review literature search, and (iii) query exploitation: the application of methods to Boolean queries in order to improve systematic review literature search effectiveness. For each of these query automation areas, this thesis devises computational methods as well as practical tools.This thesis makes contributions across three main areas of enquiry. They comprise of: (i) computational adaptations of human query formulation methodologies to support the automatic development of complex Boolean queries for systematic review literature search, and practical tools built upon them, (ii) a framework for the generation and identification of more effective query variations to support the automatic refinement of high-quality Boolean queries used in systematic review literature search, as well as tools built upon them, and (iii) methods to exploit intrinsic characteristics of Boolean queries in order to improve the retrieval effectiveness of systematic review literature search. We found that for each of these inquiry areas, query automation was able to improve search effectiveness, reducing the amount of time necessary to create systematic reviews.

When conducting a search for research papers, the search should return comprehensive results related to the user’s query. In general, a user inputs a Boolean query that reflects the information need, and the search engine ranks the research papers based on the query. However, it is difficult to anticipate all possible terms that authors of relevant papers might have used. Moreover, general query-based ranking methods emphasize how to rank the relevant documents at the top of the results, but require some means of guaranteeing the comprehensiveness of the results. Therefore, two ranking methods that consider the comprehensiveness of relevant papers are proposed. The first uses a topic-based Boolean query search. This search converts every word in the abstract set and query into a topic via topic analysis by Latent Dirichlet Allocation (LDA) and conducts a search at the topic level. The topic assigned to synonyms of a search term is expected to be the same as that assigned to the search term. Each paper is ranked based on the number of times it is matched with each topic-based Boolean query search executed for various LDA parameter settings. The second is a hybrid method that emphasizes better results from our topic-based ranking result and a general query-based ranking result. This method is based on the observation that the paper sets retrieved by our method and by a general ranking method will be different. Through experiments using the NTCIR-1 and -2 datasets, the effectiveness of our topic-based and hybrid methods are demonstrated.

This paper addresses the problem of sharing person-specific genomic sequences without violating the privacy of their data subjects to support large-scale biomedical research projects. The proposed method builds on the framework proposed by Kantarcioglu et al. [1] but extends the results in a number of ways. One improvement is that our scheme is deterministic, with zero probability of a wrong answer (as opposed to a low probability). We also provide a new operating point in the space-time tradeoff, by offering a scheme that is twice as fast as theirs but uses twice the storage space. This point is motivated by the fact that storage is cheaper than computation in current cloud computing pricing plans. Moreover, our encoding of the data makes it possible for us to handle a richer set of queries than exact matching between the query and each sequence of the database, including: (i) counting the number of matches between the query symbols and a sequence; (ii) logical OR matches where a query symbol is allowed to match a subset of the alphabet thereby making it possible to handle (as a special case) a “not equal to” requirement for a query symbol (e.g., “not a G”); (iii) support for the extended alphabet of nucleotide base codes that encompasses ambiguities in DNA sequences (this happens on the DNA sequence side instead of the query side); (iv) queries that specify the number of occurrences of each kind of symbol in the specified sequence positions (e.g., two ‘A’ and four ‘C’ and one ‘G’ and three ‘T’, occurring in any order in the query-specified sequence positions); (v) a threshold query whose answer is ‘yes’ if the number of matches exceeds a query-specified threshold (e.g., “7 or more matches out of the 15 query-specified positions”). (vi) For all query types, we can hide the answers from the decrypting server, so that only the client learns the answer. (vii) In all cases, the client deterministically learns only the query's answer, except for query type (v) where we quantify the (very small) statistical leakage to the client of the actual count.

For any query language $\mathcal {F}$ , we consider three natural families of boolean queries. Nonemptiness queries are expressed as e ≠ ∅ with e an $\mathcal {F}$ expression. Emptiness queries are expressed as e = ∅. Containment queries are expressed as e1 ⊆ e2. We refer to syntactic constructions of boolean queries as modalities. In first order logic, the emptiness, nonemptiness and containment modalities have exactly the same expressive power. For other classes of queries, e.g., expressed in weaker query languages, the modalities may differ in expressiveness. We propose a framework for studying the expressive power of boolean query modalities. Along one dimension, one may work within a fixed query language and compare the three modalities. Here, we identify crucial query features that enable us to go from one modality to another. Furthermore, we identify semantical properties that reflect the lack of these query features to establish separations. Along a second dimension, one may fix a modality and compare different query languages. This second dimension is the one that has already received quite some attention in the literature, whereas in this paper we emphasize the first dimension. Combining both dimensions, it is interesting to compare the expressive power of a weak query language using a strong modality, against that of a seemingly stronger query language but perhaps using a weaker modality. We present some initial results within this theme. The two main query languages to which we apply our framework are the algebra of binary relations, and the language of conjunctive queries.

We consider tuple-independent probabilistic databases in a dynamic setting, where tuples can be inserted or deleted. In this context we are interested in efficient data structures for maintaining the query result of Boolean as well as non-Boolean queries. For Boolean queries, we show how the known lifted inference rules can be made dynamic, so that they support single-tuple updates with only a constant number of arithmetic operations. As a consequence, we obtain that the probability of every safe UCQ can be maintained with constant update time. For non-Boolean queries, our task is to enumerate all result tuples ranked by their probability. We develop lifted inference rules for non-Boolean queries, and, based on these rules, provide a dynamic data structure that allows both log-time updates and ranked enumeration with logarithmic delay. As an application, we identify a fragment of non-repeating conjunctive queries that supports log-time updates as well as log-delay ranked enumeration. This characterisation is tight under the OMv-conjecture.

We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database. For a Boolean query q, the problem CERTAINTY(q) takes a database as input, and asks whether or not each repair satisfies the query q. It is known that for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is in FO, L-complete, or coNP-complete. In particular, CERTAINTY(q) is in FO for any self-join-free Boolean path query q. In this paper, we show that if self-joins are allowed, then the complexity of CERTAINTY(q) for Boolean path queries q exhibits a tetrachotomy between FO, NL-complete, PTIME-complete, and coNP-complete. Moreover, it is decidable, in polynomial time in the size of the query q, which of the four cases applies.

With the precinct of e-mail message discharge events, for example, the Hillary Clinton’s electronic mail argument, certification besides safety of subtle e-mail info consume changed into customer’s chief concern. Mixed e-mail is unmistakably a sensible response for giving security; regardless, it will outright tie their exercise. Open encryption with catchphrase search plan is a standard headway to solidify safekeeping shield in addition inconceivable feasibility works organized that can recognize a huge development in inspecting mixed electronic message in a cloud server. Within the paper, we recommend a applied PEKS plan termed by means of open key multi-catchphrase available encryption through covered edifices (PMSEHS). That may perhaps attract e-mail recipients toward the multi-watchword also Boolean requesting from the monstrous mixed electronic post database as savvy would be reasonable, deprived of skimpy extra data to the cloud server. In same manner, we provide relative tests, whichever show that our strategy takes a sophisticated capability in multi-catchphrase break down used for mixed messages.

The resilience problem for a Boolean query in a database is the task of finding a minimum set of tuples that, when deleted from the database, turns the query evaluation false. We examine the parameterized complexity of a particular version of this problem for fixed queries. A natural parameter for this problem is the number of tuples needed to be deleted. For this, we use a formal characterization of the solution set that proves the W[1] membership for this parameter and a fixed-parameter tractable result when considering the database treewidth.

Consistent Query Answering (CQA) with respect to primary keys is the following problem. Given a database instance that is possibly inconsistent with respect to its primary key constraints, define a repair as an inclusion-maximal consistent subinstance. Given a Boolean query q, the problem CERTAINTY(q) takes a database instance as input, and asks whether q is true in every repair. For every Boolean conjunctive query q, the complement of CERTAINTY(q) can be straightforwardly implemented in Answer Set Programming (ASP) by means of a generate-and-test approach: first generate a repair, and then test whether it falsifies the query. Theoretical research has recently revealed that for every self-join-free Boolean conjunctive query q, the complexity class of CERTAINTY(q) is one of FO, L-complete, or coNP-complete. Faced with this complexity trichotomy, one can hypothesize that in practice, the full power of generate-and-test is a computational overkill when CERTAINTY(q) is in the low complexity classes FO or L. We investigate part of this hypothesis within the context of ASP, by asking the following question: whenever CERTAINTY(q) is in FO, does a dedicated first-order algorithm exhibit significant performance gains compared to a generic generate-and-test implementation? We first elaborate on the construction of such dedicated first-order algorithms in ASP, and then empirically address this question.

Systematic reviews are used widely in the biomedical and healthcare domains. Systematic reviews aim to provide a complete and exhaustive overview of the medical literature for a specific research question. Core to the construction of a systematic review is the search strategy. The main component of a search strategy is a complex Boolean query, typically developed by information specialists (e.g., librarians). The aim of the search strategy is to retrieve relevant studies that will contribute to the outcomes of the systematic review. One barrier information specialists face when developing a search strategy is the enormous amount of medical literature that exists in databases. This vast amount of literature means that search strategies often suffer from biases (e.g., lack of expertise, overconfidence, limited knowledge of the domain) and are incomplete, or retrieve far too many studies (possibly as a result of the biases, but also due to the tools used to develop search strategies). Retrieving too many studies impacts the time and financial costs of the review, and retrieving too few studies may impact the outcomes of the review. Therefore, it is vital to support expert searchers develop effective search strategies. In this paper, we present a novel end-to-end set of advanced tools for information specialists. These tools are tightly integrated into an existing Open Source search strategy refining package (searchrefiner). These tools aim to address the problems associated with search strategy development by providing a complete framework from query development, to refinement, to documentation. The implementation of these tools also offers a glimpse at the ease at which related tools may be implemented within the searchrefiner ecosystem. More information about the tools including installation, documentation, and screenshots is made available on the searchrefiner website: https://ielab.io/searchrefiner.

We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query answering for a Boolean query is the following problem: given a database instance as input, is the query true in every repair? In [Koutris and Wijsen, ICDT 2019], it was shown that for every self-join-free Boolean conjunctive query and set of key dependencies containing exactly one key dependency per relation name (also called the primary key), this problem is in FO, L-complete, or coNP-complete, and it is decidable which of the three cases applies. In this paper, we consider the more general case where a relation name can be associated with more than one key dependency. It is shown that in this more general setting, it remains decidable whether or not the above problem is in FO, for self-join-free Boolean conjunctive queries. Moreover, it is possible to effectively construct a first-order query that solves the problem whenever such a query exists.

Formulating Boolean queries for systematic review literature search is a challenging task. Commonly, queries are formulated by information specialists using the protocol specified in the review and interactions with the research team. Information specialists have in-depth experience on how to formulate queries in this domain, but may not have in-depth knowledge about the reviews’ topics. Query formulation requires a significant amount of time and effort, and is performed interactively; specialists repeatedly formulate queries, attempt to validate their results, and reformulate specific Boolean clauses. In this paper, we investigate the possibility of automatically formulating a Boolean query from the systematic review protocol. We propose a novel five-step approach to automatic query formulation, specific to Boolean queries in this domain, which approximates the process by which information specialists formulate queries. In this process, we use syntax parsing to derive the logical structure of high-level concepts in a query, automatically extract and map concepts to entities in order to perform entity expansion, and finally apply post-processing operations (such as stemming and search filters). Automatic query formulation for systematic review literature search has several benefits: (i) it can provide reviewers with an indication of the types of studies that will be retrieved, without the involvement of an information specialist, (ii) it can provide information specialists with an initial query to begin the formulation process, (iii) it can provide researchers that perform rapid reviews with a method to quickly perform searches.

Searching medical literature for synthesis in a systematic review is a complex and labour intensive task. In this context, expert searchers construct lengthy Boolean queries. The universe of possible query variations can be massive: a single query can be composed of hundreds of field-restricted search terms/phrases or ontological concepts, each grouped by a logical operator nested to depths of sometimes five or more levels deep. With the many choices about how to construct a query, it is difficult to both formulate and recognise effective queries. To address this challenge, automatic methods have recently been explored for generating and selecting effective Boolean query variations for systematic reviews. The limiting factor of these methods is that it is computationally infeasible to process all query variations for training the methods. To overcome this, we propose novel query variation sampling methods for training Learning to Rank models to rank queries. Our results show that query sampling methods do directly impact the ability of a Learning to Rank model to effectively identify good query variations. Thus, selecting appropriate query sampling methods is a key problem for the automatic reformulation of effective Boolean queries for systematic review literature search. We find that the best sampling strategies are those which balance the diversity of queries with the quantity of queries.

Objective Systematic reviews are important in health care but are expensive to produce and maintain. The authors explore the use of automated transformations of Boolean queries to improve the identification of relevant studies for updates to systematic reviews. Materials and Methods A set of query transformations, including operator substitution, query expansion, and query reduction, were used to iteratively modify the Boolean query used for the original systematic review. The most effective transformation at each stage is identified using information about the studies included and excluded from the original review. A dataset consisting of 22 systematic reviews was used for evaluation. Updated queries were evaluated using the included and excluded studies from the updated version of the review. Recall and precision were used as evaluation measures. Results The updated queries were more effective than the ones used for the original review, in terms of both precision and recall. The overall number of documents retrieved was reduced by more than half, while the number of relevant documents found increased by 10.3%. Conclusions Identification of relevant studies for updates to systematic reviews can be carried out more effectively by using information about the included and excluded studies from the original review to produce improved Boolean queries. These updated queries reduce the overall number of documents retrieved while also increasing the number of relevant documents identified, thereby representing a considerable reduction in effort required by systematic reviewers.

Searchable symmetric encryption (SSE) with increasing expressiveness was proposed to acquire optimal communication complexity, but it has poor efficiency compared to the single-word query. Many of the existing expressive SSE mechanisms use the inverted index to build the encrypted database (EDB) for the sub-linear search complexity. However, this inevitably brings about the problems of repeated storage and low efficiency of set operations. To this end, we introduced a new approach, using the boolean vectors (BV) instead of the inverted indexes to build EDB, which dramatically improves the search efficiency and reduces the storage space. While boolean operation must run on the closed space, we divided the full queried space into several disjoint closed sub-spaces and proved its correctness theoretically. Our construction supports arbitrary conjunctive, disjunctive, and boolean queries. The experiments prove that our system is more efficient in storage and search complexity than existing methods.

Coordination level matching is a ranking method originally proposed to rank documents given Boolean queries that is now several decades old. Rank fusion is a relatively recent method for combining runs from multiple systems into a single ranking, and has been shown to significantly improve the ranking. This paper presents a novel extension to coordination level matching, by applying rank fusion to each sub-clause of a Boolean query. We show that, for the tasks of systematic review screening prioritisation and stopping estimation, our method significantly outperforms the state-of-the-art learning to rank and bag-of-words-based systems for this domain. Our fully automatic, unsupervised method has (i) the potential for significant real-world cost savings (ii) does not rely on any intervention from the user, and (iii) is significantly better at ranking documents given only a Boolean query in the context of systematic reviews when compared to other approaches.

Searchable symmetric encryption (SSE) allows one to outsource a collection of encrypted documents to a remote server, and later conduct keyword searches on these encrypted documents, while revealing minimal information to the server. Most existing SSE schemes are only proved adaptively secure against the untrusted server in the random oracle model. To enhance security, we consider the security in the standard model when designing an SSE scheme. We extend the OXT protocol of Cash et al. to support arbitrary boolean query in multi-client setting while achieving update of documents. Our scheme realizes access control on documents without requiring per-query interaction between the data owner and each client. In addition, we give a new effective T-set instantiation, which supports update of the index files. Besides, our scheme achieves provable security against adaptive adversarial server and malicious clients in the standard model. Finally, performance analysis shows the applicability of our scheme.

Data security and privacy concerns in cloud storage services compel data owners to encrypt their sensitive data before outsourcing. Standard encryption systems, however, hinder users from issuing search queries on encrypted data. Though various systems for search over encrypted data have been proposed in the literature, existing systems use different encrypted index structures to conduct search on different search query patterns and hence are not compatible with each other. In this paper, we propose a query over encrypted data system which supports expressive search query patterns, such as single/conjunctive keyword query, range query, boolean query and mixed boolean query, all using a single encrypted index structure. To the best of our knowledge, the proposed system enables the most expressive query pattern search among all the existing solutions. In addition, the system allows data users to simultaneously query over encrypted documents from multiple data owners using one query trapdoor and supports flexible user authorization and revocation. We show that our system is secure and resists keyword guessing attack. We also conduct extensive experiments and demonstrate that the system is more efficient than other public key searchable encryption systems.

Query expansion term selection methods are really very important for improving the accuracy and efficiency of pseudo-relevance feedback based automatic query expansion for information retrieval system by removing irrelevant and redundant terms from the top retrieved feedback documents corpus with respect to user query. Individual query expansion term selection methods have been widely investigated for improving its performance. However, it is always a challenging task to find an individual query expansion term selection method that would outperform other individual query expansion term selection methods in most cases. In this paper, first we explore the possibility of improving the overall performance using individual query expansion term selection methods. Second, we propose a model for combining multiple query expansion term selection methods by using rank combination approach, called multiple ranks combination based query expansion. Third, semantic filtering is used to filter semantically irrelevant term obtained after combining multiple query expansion term selection methods, called ranks combination and semantic filtering based query expansion. Fourth, the genetic algorithm is used to make an optimal combination of query terms and candidate term obtained after rank combination and semantic filtering approach, called semantic genetic filtering and rank combination based query expansion. Our experimental results demonstrated that our proposed approaches achieved significant improvement over each individual query expansion term selection method and related state-of-the-art approaches.

The effectiveness of query expansion methods depends essentially on identifying good candidates, or prospects, semantically related to query terms. Word embeddings have been used recently in an attempt to address this problem. Nevertheless query disambiguation is still necessary as the semantic relatedness of each word in the corpus is modeled, but choosing the right terms for expansion from the standpoint of the un-modeled query semantics remains an open issue. In this paper we propose a novel query expansion method using word embeddings that models the global query semantics from the standpoint of prospect vocabulary terms. The proposed method allows to explore query-vocabulary semantic closeness in such a way that new terms, semantically related to more relevant topics, are elicited and added in function of the query as a whole. The method includes candidates pooling strategies that address disambiguation issues without using exogenous resources. We tested our method with three topic sets over CLEF corpora and compared it across different Information Retrieval models and against another expansion technique using word embeddings as well. Our experiments indicate that our method achieves significant results that outperform the baselines, improving both recall and precision metrics without relevance feedback.

Community search problem, which is to find good communities given a set of query nodes in a graph, has attracted increasing research interest recently. Though various measurement models have been proposed to define and solve community search problem. Few of them could define a community concisely and have good quality of query results. They either involve additional constraints for modeling communities, such as size and diameter, or suffer from the free rider effect, i.e., include irrelevant subgraphs. In this paper, we propose a new k-plex based community model for community search. We show that our model not only is simple and clear, but also meets with basic requirements of defining a community search problem. We formulate the maximum k-plex community query (MCKPQ) problem, that is, given a set of query nodes Q, searching for optimal k-plex containing Q. We prove that MCKPQ is NP-hard, and it is hard to approximate in any constant factor. We first give exact solutions. Then, we propose an efficient branch-and-bound (B&B) method and design an effective upper bound function and a pruning strategy. Furthermore, we optimize the basic B&B by fast candidate generation. We also give a fast heuristic solution, which produces high-quality results in practice. The effectiveness of our model of community and the efficiency of our methods are verified by elaborate experiments.

In an accurate and timely manner, capturing the risk signals for a specific emerging technology from academic publications is important to facilitate risk governance and to reduce the potential negative impact on socioeconomic systems. In the past decade, three-dimensional printing (3D printing) has become a promising emerging technology. To identify the relevant research on risk analysis for 3D printing, “term clumping” on “risk analysis” is explored using a quantitative method, and an integrated framework for risk identification is proposed with regard to 3D printing. This method involves a variation of TF*IDF and several new metrics for a Boolean query of the literature. The empirical results for the risk analysis studies of 3D printing show that, to date, very little attention has been paid to the relevant topics. However, although the risk signals of 3D printing are still weak and dispersed in many different categories, the potential threats to human health, cyber-security, and the environment are revealed in some facets. This enables initiation of strategies for anticipatory governance, involving science and technology policies and regulations.

The arrival of large voluminous continuous queries sets for a given query leads an insignificant insights. The elimination of certain data tuples occurs in order to balance the system load. The streaming query removes the improper data tuples and uses proper data tuples in the form of defined tables or sets. However, major drawback occurs due to unbounded streaming and inadequate access to end data. Due to such constraints, many stream processing methods makes the processed data unavailable for any applications or to the related queries of neighborhood branches. This paper avoids such problems during the process of data tuples at the generation of queries. The study uses a streaming model that executes effective query plans in continuous data. The streaming model aims reduce the communication cost and improves the scalability of continuous aggregation queries. It sub-divides the client query and executes it over data aggregators within the incoherent limit. A weighted dominant query algorithm is formulated to provide the top dominant value in each sub-query clusters. This reduces the cost for computation in synthetic databases. The experimental results proved that the proposed model with weighted dominant query algorithm effectively improves scalability by reducing the computational cost.

We present a framework for information retrieval that combines document models and query models using a probabilistic ranking function based on Bayesian decision theory. The framework suggests an operational retrieval model that extends recent developments in the language modeling approach to information retrieval. A language model for each document is estimated, as well as a language model for each query, and the retrieval problem is cast in terms of risk minimization. The query language model can be exploited to model user preferences, the context of a query, synonomy and word senses. While recent work has incorporated word translation models for this purpose, we introduce a new method using Markov chains defined on a set of documents to estimate the query models. The Markov chain method has connections to algorithms from link analysis and social networks. The new approach is evaluated on TREC collections and compared to the basic language modeling approach and vector space models together with query expansion using Rocchio. Significant improvements are obtained over standard query expansion methods for strong baseline TF-IDF systems, with the greatest improvements attained for short queries on Web data.

Query reverse engineering seeks to re-generate the SQL query that produced a given query output table from a given database. In this paper, we solve this problem for OLAP queries with group-by and aggregation. We develop a novel three-phase algorithm named REGAL 1 for this problem. First, based on a lattice graph structure, we identify a set of group-by candidates for the desired query. Second, we apply a set of aggregation constraints that are derived from the properties of aggregate operators at both the table-level and the group-level to discover candidate combinations of group-by columns and aggregations that are consistent with the given query output table. Finally, we find a multi-dimensional filter, i.e., a conjunction of selection predicates over the base table attributes, that is needed to generate the exact query output table. We conduct an extensive experimental study over the TPC-H dataset to demonstrate the effectiveness and efficiency of our proposal.

A relational database is said to be uncertain if primary key constraints can possibly be violated. A repair (or possible world) of an uncertain database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with the same primary key value. For any Boolean query q , CERTAINTY( q ) is the problem that takes an uncertain database db as input and asks whether q is true in every repair of db . The complexity of this problem has been particularly studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q , whether CERTAINTY( q ) belongs to complexity classes FO , P , or coNP -complete. In this article, we combine existing techniques for studying this complexity classification task. We show that, for any self-join-free Boolean conjunctive query q , it can be decided whether or not CERTAINTY( q ) is in FO . We additionally show how to construct a single SQL query for solving CERTAINTY( q ) if it is in FO . Further, for any self-join-free Boolean conjunctive query q , CERTAINTY( q ) is either in P or coNP -complete and the complexity dichotomy is effective. This settles a research question that has been open for 10 years.

The state-of-the-art indexing mechanisms for distributed cloud data management systems can not support complex queries, such as multi-dimensional query and range query. To solve this problem, we propose a multi-dimensional indexing mechanism named PR-Chord to support complex queries. PR-Chord is composed of the global index named PR-Index and the Chord network. The multi-dimensional space formed by the range of the multi-dimensional data is divided into hyper-rectangle spaces equally. The PR-Index is a hierarchical index structure based on the improved PR quadtree to index these spaces. The complex query is transformed into the query of leaf nodes of PR-Index. We design the algorithms of query, insertion and deletion to support complex queries. Since PR-Index does not store the multi-dimensional data, its maintenance cost is zero. PR-Chord has the advantages of load balancing and simple algorithm. The experiment results demonstrate that PR-Chord has good query efficiency.

Efficient processing of skyline queries with partially ordered domains has been intensively addressed in recent years. To further reduce the query processing time to support high-responsive applications, the skyline queries that were previously processed with user preferences similar to those of the new query contribute useful candidate result points. Hence, the answered queries can be cached with both their results and the user preferences such that the query processor can rapidly retrieve the result for a new query only from the result sets of cached queries with compatible user preferences. When caching a significant number of queries accumulated over time, it is essential to adopt effective access methods to index the cached queries to retrieve a set of relevant cached queries for facilitating the cache-based skyline query computations. In this paper, we propose an extended depth-first search indexing method (e-DFS for short) for accessing user preference profiles represented by directed acyclic graphs (DAGs), and emphasize the design of the e-DFS encoding that effectively encodes a user preference profile into a low-dimensional feature point which is eventually indexed by an R-tree. We obtain one or more traversal orders for each node in a DAG by traversing it through a modified version of the depth-first search which is utilized to examine the topology structure and dominance relations to measure closeness or similarity. As a result, e-DFS which combines the criteria of similarity evaluation is able to greatly reduce the search space by filtering out most of the irrelevant cached queries such that the query processor can avoid accessing the entire data set to compute the query results. Extensive experiments are presented to demonstrate the performance and utility of our indexing method, which outperforms the baseline planning techniques by reducing 37 percent of the computational time on average.

Keyword search over databases, popularized by keyword search in WWW, allows ordinary users to access database information without the knowledge of structured query languages and database schemas. Most of the previous studies in this area use IR-style ranking, which fail to consider the importance of the query answers. In this paper, we propose CI-Rank , a new approach to keyword search in databases, which considers the importance of individual nodes in a query answer and the cohesiveness of the result structure in a balanced way. CI-Rank is built upon a carefully designed model called Random Walk with Message Passing that helps capture the relationships between different nodes in the query answer. This model lends itself well to adaptation to user preferences. We develop a branch and bound algorithm to support the efficient generation of top-k query answers. Indexing methods are also introduced to further speed up the run-time processing of queries. Extensive experiments conducted on two real data sets with a real user query log confirm the effectiveness and efficiency of CI-Rank .

The progress in mobile devices and wireless networks technologies has considerably contributed to integrate pervasive computing expertise in many domains with the aim of improving the quality of services and users' mobility. However, in many situations, users may face difficult situations, needing faster decisions, where classical systems impose the submission of classic queries in which crisp conditions must be carefully fixed. This inconvenience limits the potential of pervasive applications accessed by users having few times to make the right decisions. To introduce the contributions of this paper, we choose the medical domain as example. We considered a pervasive healthcare application under which physicians haven't enough time to fix carefully their queries in some emergency cases. Therefore, they are allowed to flexibly express their preferences using conjunctive fuzzy queries and to quickly receive best answers anywhere and anytime while treating patients in the shortest time and consequently free resources for eventually other urgent requests. In this work, we consider, in general, the problem of efficiently finding the top-K answers for a conjunctive fuzzy query from the top-N conjunctive query rewritings of the query. In particular, we propose an efficient algorithm called the Top-N rewritings algorithm for finding the top-N query rewritings of a medical conjunctive fuzzy query using a set of conjunctive crisp views. At the best of our knowledge, this algorithm is the first to generate, without computing all possible rewritings, the N best ones ordered according to their satisfaction degrees and that are likely to return the best K-answers for the user fuzzy query. The relevance of a query rewriting is estimated using a second algorithm called the Query-satisfaction computing algorithm proposed to estimate, through the histograms maintained to approximate the distribution of set of values returned by the rewriting and to which fuzzy predicates are related, the pertinence of a conjunctive fuzzy query rewriting rather than accessing the database relations.

Data integration systems on the Deep Web offer a transparent means to query multiple data sources at once. Result merging– the generation of an overall ranked list of results from different sources in response to a query– is a key component of a data integration system. In this work we present a result merging model, called Active Relevance Weight Estimation model. Different from the existing techniques for result merging, we estimate the relevance of a data source in answering a query at query time. The relevances for a set of data sources are expressed with a (normalized) weighting scheme: the larger the weight for a data source the more relevant the source is in answering a query. We estimate the weights of a data source in each subset of the data sources involved in a training query. Because an online query may not exactly match any training query, we devise methods to obtain a subset of training queries that are related to the online query. We estimate the relevance weights of the online query from the weights of this subset of training queries. Our experiments show that our method outperforms the leading merging algorithms with comparable response time.

We prove exponential lower bounds on the running time of the state-of-the-art exact model counting algorithms—algorithms for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas. These algorithms can be seen, either directly or indirectly, as building Decision-Decomposable Negation Normal Form (decision-DNNF) representations of the input Boolean formulas. Decision-DNNFs are a special case of d -DNNFs where d stands for deterministic . We show that any knowledge compilation representations from a class (called DLDDs in this article) that contain decision-DNNFs can be converted into equivalent Free Binary Decision Diagrams (FBDDs) , also known as Read-Once Branching Programs , with only a quasi-polynomial increase in representation size. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs, which imply exponential lower bounds for model-counting algorithms. We also separate the power of decision-DNNFs from d -DNNFs and a generalization of decision-DNNFs known as AND-FBDDs. We then prove new lower bounds for FBDDs that yield exponential lower bounds on the running time of these exact model counters when applied to the problem of query evaluation in tuple-independent probabilistic databases—computing the probability of an answer to a query given independent probabilities of the individual tuples in a database instance. This approach to the query evaluation problem, in which one first obtains the lineage for the query and database instance as a Boolean formula and then performs weighted model counting on the lineage, is known as grounded inference . A second approach, known as lifted inference or extensional query evaluation , exploits the high-level structure of the query as a first-order formula. Although it has been widely believed that lifted inference is strictly more powerful than grounded inference on the lineage alone, no formal separation has previously been shown for query evaluation. In this article, we show such a formal separation for the first time. In particular, we exhibit a family of database queries for which polynomial-time extensional query evaluation techniques were previously known but for which query evaluation via grounded inference using the state-of-the-art exact model counters requires exponential time.

Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications, the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of stationary objects closer to each other the heterogeneous neighboring objects ( HNOs ). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present useful and important location-based aggregate queries on the HNOs , which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. The location-based aggregate queries consist of four queries: the shortest average-distance ( SAvgD ) query, the shortest minimal-distance ( SMinD ) query, the shortest maximal-distance ( SMaxD ) query, and the shortest sum-distance ( SSumD ) query. To process the location-based aggregate queries, we devise two heuristics, the HNOs-qualifying heuristic and the HNOs-pruning heuristic , to efficiently determine the HNOs sets. According to different query types, we further propose four heuristics, the SAvgD-pruning heuristic , the SMinD-pruning heuristic , the SMaxD-pruning heuristic , and the SSumD-pruning heuristic , to effectively reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed approaches.

Answering conjunctive queries is a fundamental problem in database theory, and it is equivalent to solving constraint satisfaction problems in artificial intelligence and to other fundamental problems arising in computer science, which can be recast in terms of looking for homomorphisms between relational structures. The problem is NP-hard, so that several research efforts have been made in the literature for identifying tractable classes, known as islands of tractability, as well as for devising clever heuristics for solving efficiently real-world instances. Many heuristic approaches are based on enforcing on the given instance a property called local consistency (also, relational arc-consistency), where each tuple in every query atom matches at least one tuple in every other query atom. Interestingly, for many well-known classes of instances, such as for the acyclic ones, enforcing local consistency is even sufficient to solve the given instance correctly. However, the precise power of such a procedure ...

Continuous top-k query over sliding window is a fundamental problem in database, which retrieves k objects with the highest scores when the window slides. Existing studies mainly adopt exact algorithms to tackle this type of queries, whose key idea is to maintain a subset of objects in the window, and try to retrieve answers from it. However, all the existing algorithms are sensitive to query parameters and data distribution. In addition, they suffer from expensive overhead for incremental maintenance, and thus cannot satisfy real-time requirement. In this paper, we define a novel query named (e, δ)-approximate continuous top-k query, which returns approximate answers for top-k query. In order to efficiently support this query, we propose an efficient framework, named PABF (Probabilistic Approximate Based Framework), to support approximate top-k query over sliding window. We firstly maintain a self-adaptive pruning value, which could filter out newly arrived objects who have a probability less than 1 − δ of being a query result. For those objects that are not filtered, we combine them together, if the score difference among them is less than a threshold. To efficiently maintain these combined results, the framework PABF also proposes a multi-phase merging algorithm. Theoretical analysis indicates that even in the worst case, we require only logarithmic complexity for maintaining each candidate.

Boolean query is an important method to achieve accurate data retrieval. The deeply study of Boolean query’s implementation strategy is conducive to flexible application of Boolean query, optimization of query expression and improvement of execution efficiency. Starting with the implementation strategy of Boolean query in Lucene framework, this paper studies the representation, execution sequence diagram, logical operation rules and sub-query merging algorithm. According to the implementation strategy, the simplification rules of complex Boolean query with depth of 2 are proposed, and their correctness is proved theoretically. Finally, the validity of these laws is verified by experimental simulation.

Searchable symmetric encryption (SSE) is a practical technique that allows a client to outsource her encrypted files while maintaining an efficient and secure keyword search ability to authorized clients. To support multi-keyword or Boolean search capability, most of the existing SSE designs inevitably reveal the intermediate single keyword search result to the remote server. Such unintended leakage could be abused to infer the valuable information of the encrypted dataset. In order to hide this kind of intermediate search result (even in some private manners), two promising directions could be adopted, one is a hardware-assisted technology, e.g., Intel SGX, and the other is a software-based approach, e.g., indistinguishability obfuscation (iO). Here, we focus on the iO approach and devise a highly-scalable SSE design for supporting Boolean queries without revealing its single keyword search results. To show the advantages of our proposed design, we conduct a theoretical comparison between some related SSE protocols and ours in terms of storage and computation costs.

With the increase in sensory capability of mobile devices, the data that can be generated and used in a lifelogging context gets increasingly diverse. Such data is special in the context of multimedia, not only because of its close personal relationship with its originator, but also because of its diverse multimodality and its composition from structured, semi-structured, and unstructured data. This diversity poses retrieval challenges that are unique to lifelog data but which also have implications for retrieval activity in other multimedia domains. In this paper, we present the extensions made to the vitrivr open-source multimedia retrieval stack, in order to address some of these unique lifelogging challenges. For the participation to the 2019 Lifelog Search Challenge (LSC), we have extended vitrivr with the capability to process Boolean query expressions alongside content-based query descriptions in order to leverage the structural diversity inherent to lifelog data.

Selectivity estimation of a boolean query based on frequent itemsets can be solved by describing the problem by a linear program. However, the number of variables in the equations is exponential, rendering the approach tractable only for small-dimensional cases. One natural approach would be to project the data to the variables occurring in the query. This can, however, change the outcome of the linear program. We introduce the concept of safe sets: projecting the data to a safe set does not change the outcome of the linear program. We characterise safe sets using graph theoretic concepts and give an algorithm for finding minimal safe sets containing given attributes. We describe a heuristic algorithm for finding almost-safe sets given a size restriction, and show empirically that these sets outperform the trivial projection. We also show a connection between safe sets and Markov Random Fields and use it to further reduce the number of variables in the linear program, given some regularity assumptions on the frequent itemsets.