Conjunctive query evaluation by search-tree revisited

The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D$D$, a conjunctive query Q$Q$, and a tuple a$a$, tests whether Q(a)$Q\left(a\right)$ holds in D$D$ in time bounded by a polynomial in (sn)^logk(sn)^loglogn${\left(sn\right)}^{logk}{\left(sn\right)}^{loglogn}$ and n^r$n^r$, where n$n$ is the size of the domain of the database, k$k$ is the number of bound variables of the conjunctive query, s$s$ is the size of the optimal search-tree, and r$r$ is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the n^O(k)$n^{O\left(k\right)}$ bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks.     

Maintaining large update batches by restructuring and grouping

Materialized views defined over distributed data sources can be utilized by many applications to ensure better access, reliable performance, and high availability. Technology for maintaining materialized views is thus critical for providing up-to-date results since a stale view extent may not help or even mislead these applications. State-of-the-art incremental view maintenance requires O(n²)$\mathrm{O}(n^2)$ or more remote maintenance queries with n being the number of data sources in the view definition. In this work, we propose two novel maintenance strategies, namely adjacent grouping and conditional grouping, that dramatically reduce the number of maintenance queries required to maintain the materialized views. This reduction in the number of maintenance queries brings the basic trade-off between the complexity of each query and the total number of maintenance queries that can be exploited to improve maintenance performance. The proposed maintenance strategies have been implemented in a working prototype system called TxnWrap. Experimental studies illustrate that our proposed strategies are able to achieve about 400% performance improvement in terms of total processing time compared with existing batch algorithms in a majority of cases.     

A methodology for coupling fragments of XPath with structural indexes for XML documents

We introduce a new methodology for coupling language-induced partitions and index  -induced partitions on XML documents that is aimed for the benefit of efficient evaluation of XPath queries. In particular, we identify XPath fragments which are ideally coupled with the newly introduced P(k)$P(k)$-partition which has its definition grounded in the well-known A(k)$A(k)$ structural index and its associated partition. We then utilize these couplings to investigate fundamental questions about the use of structural indexes in XPath query evaluation.     

On the privacy offered by (k, δ)-anonymity

The widespread deployment of technologies with tracking capabilities, like GPS, GSM, RFID and on-line social networks, allows mass collection of spatio-temporal data about their users. As a consequence, several methods aimed at anonymizing spatio-temporal data before their publication have been proposed in recent years. Such methods are based on a number of underlying privacy models. Among these models, (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$ claims to extend the widely used k  -anonymity concept by exploiting the spatial uncertainty δ≥0$\delta \ge 0$ in the trajectory recording process. In this paper, we prove that, for any δ>0$\delta >0$ (that is, whenever there is actual uncertainty), (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$ does not offer trajectory k-anonymity, that is, it does not hide an original trajectory in a set of k   indistinguishable anonymized trajectories. Hence, the methods based on (k,δ)-anonymity$(k,\delta )\mathrm{-}\mathrm{anonymity}$, like Never Walk Alone (NWA) and Wait For Me (W4M) can offer trajectory k  -anonymity only when δ=0$\delta =0$ (no uncertainty). Thus, the idea of exploiting the recording uncertainty δ$\delta$ to achieve trajectory k  -anonymity with information loss inversely proportional to δ$\delta$ turns out to be flawed.     

Thermodynamic modeling of dilute components in multicomponent solutions

Those performing applied calculations with thermodynamic database computing systems often find that an essential component of a particular solution phase is missing from the database. Provided that one is interested only in dilute solutions of this component, and only over a relatively narrow concentration range of the major components, the solution can often be treated with acceptable accuracy for practical purposes by assuming that the activity coefficient of the dilute component is constant, independent of composition over the composition range of interest (Henry’s Law). It is shown that, in this case, the only required model parameter, apart from the constant activity coefficient γ$\gamma$, is a constant ν$\nu$, defined as the total number of independent species, not already present in the solvent solution, into which the dilute component dissociates. That is, the equation for the chemical potential of the dilute component is independent of the model used for the solution in the database. Consequently, simple software can be written permitting one to add dilute species to existing solution databases, while performing calculations, by supplying values only of the constants γ$\gamma$ and ν$\nu$. A sample application is given of the calculation of Fe³⁺/Fe²⁺ and Cu²⁺/Cu⁺ redox ratios in a 9-component glass melt.     

Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.     

On approximating metric 1-median in sublinear time

This paper focuses on approximating the metric 1-median problem with sublinear number of queries and time complexity. We first show a simper proof of the currently best 4-approximation algorithm, and then propose a recursive algorithm. For any integer h?2$h?2$, the algorithm finds a 2h  -approximation solution with O(n^1+1/h)$O(n^{1+1/h})$ queries and time complexity.     

The complexity of weighted counting for acyclic conjunctive queries

This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P$\mathrm{\#}\mathsf{P}$-hard. We first show that weighted counting for quantifier free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate a large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions for ACQs. Thus we completely determine the tractability frontier for weighted counting for ACQ.     

Continuous distance-based skyline queries in road networks

In recent years, the research community has introduced various methods for processing skyline queries in road networks. A skyline query retrieves the skyline points that are not dominated by others in terms of static and dynamic attributes (i.e., the road distance). This paper addresses the issue of efficiently processing continuous skyline queries in road networks. Two novel and important distance-based skyline queries are presented, namely, the continuous  _dε-skyline$d_{\epsilon }\mathrm{-}\mathit{skyline}$query   (_Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$) and the continuous k nearest neighbor-skyline query (Cknn-SQ  ). A grid index is first designed to effectively manage the information of data objects and then two algorithms are proposed, the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$algorithm   and the _Cdε-SQ⁺${\mathit{Cd}}_{\epsilon }\mathrm{-}{\mathit{SQ}}^{+}$algorithm  , which are combined with the grid index to answer the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$. Similarly, the Cknn-SQ algorithm and the Cknn-SQ⁺algorithm are developed to efficiently process the Cknn-SQ. Extensive experiments using real road network datasets demonstrate the effectiveness and the efficiency of the proposed algorithms.     

Modeling Motion Relations for Moving Objects on Road Networks

In this paper, a basic set of motion relations capturing specific prototypical movements of vehicles on US road networks are introduced. Vehicle positional data collected from a geosensor network and stored in a spatio-temporal database serve as the basis for computing the relations that include isBehind, inFrontOf, driveBeside, and passBy. Relational SQL queries are used to derive the relations, returning information about pairs of moving objects and their relative positions. This information provides additional user contexts for binary vehicle patterns relative to a reference object. A framework for the kinds of moving objects that participate in these relations is supplied through an associated TransportationDevice ontology. Depending on the class of moving object, a relation such as isBehind captures scenarios that are facilitating or inhibiting with respect to the movement of traffic. For example, if a police car is known to be behind an automobile, the automobile typically slows to correspond with the legal speed limit. In this work, we show how linking the spatio-temporal database to an ontology can augment and extend the motion relation information, providing multi-granular perspectives of moving vehicles.

Tag systems and Collatz-like functions

Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both   the shift number v$v$ and the number of symbols μ$\mu$. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n+1$3n+1$-problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of μ$\mu$ and v$v$–for tag systems might be significantly decreased.     

Multiple <Emphasis Type="Italic">k</Emphasis> nearest neighbor search

The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time.     

Liouvillian solutions of linear difference–differential equations

For a field k$k$ with an automorphism σ$\sigma$ and a derivation δ$\delta$, we introduce the notion of Liouvillian solutions of linear difference–differential systems {σ(Y)=AY,δ(Y)=BY}$\{\sigma \left(Y\right)=AY,\delta \left(Y\right)=BY\}$ over k$k$ and characterize the existence of Liouvillian solutions in terms of the Galois group of the systems. In the forthcoming paper, we will propose an algorithm for deciding if linear difference–differential systems of prime order have Liouvillian solutions.     

Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing

This paper proposes a method for finding solutions of arbitrarily nonlinear systems of functional equations through stochastic global optimization. The original problem (equation solving) is transformed into a global optimization one by synthesizing objective functions whose global minima, if they exist, are also solutions to the original system. The global minimization task is carried out by the stochastic method known as fuzzy adaptive simulated annealing, triggered from different starting points, aiming at finding as many solutions as possible. To demonstrate the efficiency of the proposed method, solutions for several examples of nonlinear systems are presented and compared with results obtained by other approaches. We consider systems composed of n   equations on Euclidean spaces ?n${?}^n$ (n variables: x₁, x₂, x₃, ? , x_n).     

Sequencing by hybridization in few rounds

Sequencing by Hybridization (SBH) is a method for reconstructing an unknown DNA string based on obtaining, through hybridization experiments, whether certain short strings appear in the target string. Following Margaritis and Skiena (1995) [12], we study the SBH in rounds problem: The goal is to reconstruct an unknown string A (over a fixed alphabet) using queries of the form “does the string S appear in A?” for some query string S. The queries are performed in rounds, where the queries in each round depend on the answers to the queries in the previous rounds. We show that almost all strings of length n can be reconstructed in ${\log }^{1}n$ rounds with $O(n)$ queries per round. We also consider a variant of the problem in which for each substring query S, the answer is whether S appears once in the string A, appears at least twice in A, or does not appear in A. For this problem, we show that almost all strings can be reconstructed in 2 rounds of $O(n)$ queries. Our results improve the previous results of Margaritis and Skiena (1995) [12] and Frieze and Halldórsson (2002) [8].     

Compressed data structures: Dictionaries and data-aware measures

In this paper, we propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data  , where the task is to construct a data structure for representing a set S$S$ of n$n$ items out of a universe U={0,…,u−1}$U=\{0,\dots ,u-1\}$ and supporting various queries on S$S$. We use a well-known data-aware measure for set data called gap to bound the space of our data structures.     

Optimum sweeps of simple polygons with two guards

A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P  , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n²)$O(n^2)$ time and O(n)$O(n)$ space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)$O(n)$.