Web tracking plays a crucial role in the Web ecosystem. It relies on third-party tracking domains collecting user information for various applications such as advertisement and analytics. With the massive growth of the Internet, understanding tracking and its geographical roots is of strategic importance. The goal of this paper is to propose a thorough investigation of web tracking inside China taking advantage of a large dataset (1011records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL. Our results show that a power law applies on the traffic of both sites and trackers with a handful of trackers, 26, representing 90% of tracking activity. We then show that although most first-party sites accessed from China are owned by Chinese corporations, large proportion of trackers belong to US ones. This raises concerns about the analytics industry in China, and more generally shed new lights on the international data flows, the interdependency of the main actors, and the complexity of the threats for both people and states.

DNS is a critical component of Internet architecture. Almost all applications, in particular web based applications that constitute the large majority of current Internet traffic, leverage heavily on DNS. This makes DNS based measurements a promising tool for understanding global properties of Internet traffic, e.g., sites audience, traffic matrix. However, using passive DNS traces from local DNS servers is challenging because of DNS caching and NATs. The goal of this paper is twofold. First, we show how to correct the bias due to DNS cache and the wide use of NATs, to extract meaningful traffic information from DNS traces. The techniques are then used and validated over a large dataset (1011records) containing two days of full DNS access from a major ISP providing both mobile and landline ADSL in China. Second, we focus on the tracking activity and show that although most sites accessed from China belong to Chinese corporations, most trackers belong to US ones. Mobile and ADSL platforms are alike.

International audience

An UBIQUEST system provides a high level programming abstraction for rapid prototyping of heterogeneous and distributed applications in a dynamic environment. Such a system is perceived as a distributed database and the applications interact through declarative queries including declarative networking programs (e.g. routing) and/or specific data-oriented distributed algorithms (e.g. distributed join). Case-Based Reasoning is used for optimization of distributed queries when as there is no prior knowledge on data (sources) in networking applications, and certainly no related metadata such as data statistics.

Advances in wireless sensor networks and positioning technologies enable traffic management (e.g. routing traffic) that uses real-time data monitored by GPS-enabled cars. Location management has become an enabling technology in such application. The location modeling and trajectory prediction of moving objects are the fundamental components of location management in mobile locationaware applications. In this paper, we model the road network and moving objects in a graph of cellular automata (GCA), which makes full use of the constraints of the network and the stochastic behavior of the traffic. A simulation-based method based on graphs of cellular automata is proposed to predict future trajectories. Our technique strongly differs from the linear prediction method, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changes. The experiments, carried on two different datasets, show that the simulation-based prediction method provides higher accuracy than the linear prediction method.

This paper addresses fundamental issues related to the modeling of geometric data embedded in high-dimensional spaces. This covers several application fields, including moving objects where trajectories are described in a three- or four-dimensional space, and digital elevation models (DEMs). We show that moving objects and DEMs are specific instances of a broader class of complex spatial data that require the interpolation of values from collections of samples. We propose to model such data conceptually using infinite relations (e.g. the trajectory of a moving point yields an infinite ternary relation) which can be manipulated through standard relational query languages (e.g. SQL), with no mention of the interpolated definition. This approach is simple and establishes a clear separation between logical and physical levels. It permits the expression of queries on spatio-temporal databases in a purely declarative way. Next, we investigate algorithms for evaluating queries on interpolated data. In the general cases, the cost of manipulating $d$-dimensional data is exponential in $d$. We describe how to use rewriting and optimization techniques in order to evaluate queries with a small set of algorithms running in dimension 2, thus making the complexity independent from the global dimension.

We consider the problem of answering queries using only materialized views. We first show that if the views subsume the query from the point of view of the information content, then the query can be answered using only the views, but the resulting query might be extremely inefficient. We then focus on aggregate views and queries over a single relation, which are fundamental in many applications such as data warehousing. We show that in this case, it is possible to guarantee that as soon as the views subsume the query, it can be completely rewritten in terms of the views in a simple query language. Our main contribution is the conception of various rewriting algorithms which run in polynomial time, and the proof of their completeness which relies on combinatorial arguments. Finally, we discuss the choice of materializing or not ratio views such as average and percentage, important for the design of materialized views. We show that it has an impact on the information content, which can be used to protect data, as well as on the maintenance of views.

The paper presents a logical data model for statistical data with an explicit modeling of metadata, which allows to perform automatic aggregation. The data are stored in standard relations from the relational model, while the metadata, defining the semantics of the relations, are represented by numerical dependencies which specify the way the summary values are defined in terms of micro-data, as well as the interrelationships among summary values. The present model supports standard relational languages such as SQL. Relations with numerical dependencies are then seen as statistical views over initial relations of micro-data. Queries can be asked either against the views or directly against the initial relations, and in this later case answered, when possible, using the views. The numerical dependencies of the views are run together with the query to compute the answer to the query. This is handled in a completely automatic manner with no need for the user to deal with the intricacy of metadata. The mechanism has been tested by an implementation in Prolog of meaningful examples of queries and dependencies. It is shown in particular that various classical problems in the realm of statistical and multidimensional databases can be easily modeled and solved in the present framework. Finally, the proposed formalism is shown to be useful for statistical database schema design.

We introduce a first-order language with real polynomial arithmetic and aggregation operators (count, iterated sum and multiply), which is well suited for the definition of aggregate queries involving complex statistical functions. It offers a good trade-off between expressive power and complexity, with a tractable data complexity. Interestingly, some fundamental properties of first-order with real arithmetic are preserved in the presence of aggregates. In particular, there is an effective quantifier elimination for formulae with aggregation. We consider the problem of querying data that has already been aggregated in aggregate views, and focus on queries with an aggregation over a conjunctive query. Our main conceptual contribution is the introduction of a new equivalence relation among conjunctive queries, the isomorphism modulo a product. We prove that the equivalence of aggregate queries such as for instance averages reduces to it. Deciding if two queries are isomorphic modulo a p...

This paper presents DEDALE, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. DEDALE relies on a logical model based on linear constraints, which generalizes the constraint database model of [KKR90]. While in the classical constraint model, spatial data is always decomposed into its convex components, in DEDALE holes are allowed to fit the need of practical applications. The logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. DEDALE relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. This new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. Their formal foundation constitutes a basis for practical query optimization. We describe several evaluation rules tailored for geometric data and give the specification of an optimizer module for spatial queries. Except for the latter module, the system has been fully implemented upon the O2 DBMS, thus proving the effectiveness of a constraint-based approach for the design of spatial database systems.

) St ephane Grumbach I.N.R.I.A. Rocquencourt BP 105 78153 Le Chesnay, France [email protected] Jianwen Su Computer Science Department University of California Santa Barbara, California 93106, USA [email protected] Abstract We develop a framework for (real) constraint databases based on finite precision arithmetic which fulfills the main requirements of practical constraint databases. First, it allows the manipulation of approximate values, standard in scientific applications. More importantly, it permits the extension of the relational calculus with aggregate functions, while preserving the fundamental property of closed form evaluation with PTIME data complexity. This is an important step since the initial model of [KKR90] cannot be extended to aggregate functions. Moreover, finite precision computation plays a central role in efficient query processing. We introduce the finite precision semantics of queries and prove expressive power results concerning it. We then prese...

We consider infinite databases which admit a finite representation in terms of dense-order constraints.

We study classes of infinite but finitely representable databases based on constraints, motivated by new database applications such as geographical databases. The mathematical framework is based on classical decidable first-order theories. We investigate the theory of finitely representable models and prove that it differs strongly from both classical model theory and finite model theory. In particular, we show that most of the well known theorems of either one fail (compactness, completeness, locality, 0/1 laws, etc.). An immediate consequence is the lack of tools to consider the definability of queries in the relational calculus over finitely representable databases. We illustrate this very challenging problem through some classical examples.

The authors propose a lossless algorithm based on regularities, such as the presence of palindromes, in the DNA. The results obtained, although not satisfactory, are far beyond classical algorithms.>

The impact of adding certain families of generalized quantifiers to first-order logic (FO) on the asymptotic behavior of sentences is studied. All the results are stated and proved for languages disallowing free variables in the scope of generalized quantifiers. For a class K of finite structures closed under isomorphism, the quantifier Q/sub K/ is said to be strongly monotonic, sm, if membership in the class is preserved under a loose form of extensions. The first theorem (O/1 law for FO with any set of sm quantifiers) subsumes a previous criterion for proving that almost no graphs satisfy a given property. A O/1 law for FO with Hartig quantifiers (equicardinality quantifiers) and a limit law for a fragment of FO with Rescher quantifiers (expressing inequalities of cardinalities) are also established. It is also proved that the O/1 law fails for the extension of FO with Hartig quantifiers if the above syntactic restriction is relaxed, giving the best upper bound for the existence of a O/1 law for FO with Hartig quantifiers.>

Bags, i.e. sets with duplicates, are often used to implement relations in database systems. In this paper we study the expressive power of algebras for manipulating bags. The algebra we present is a simple extension of the nested relation algebra. Our aim is to investigate how the use of bags in the language extends its expressive power, and increases its complexity. We consider two main issues, namely (i) the relationship between the depth of bag nesting and the expressive power, and (ii) the relationship between the algebraic operations, and their complexity and expressive power. We show that the bag algebra is more expressive than the nested relation algebra (at all levels of nesting), and that the difference may be subtle. We establish a hierarchy based on the structure of algebra expressions. This hierarchy is shown to be highly related to the properties of the powerset operator.

The expressiveness and complexity of several calculus-based query languages for complex objects is considered. Unlike previous investigations, we are concerned with the complexity of queries on databases of complex objects, rather than flat databases. This raises new issues specific to complex objects. For instance, it is shown that the way the database makes use of its higher-order types has direct impact on query complexity. The use of fixpoint operators is shown to yield languages well-behaved with respect to complexity and expressiveness. In particular, an extension of the fixpoint queries to complex objects is shown to express precisely the PTIME queries, under the assumption that the database makes "full" use of all its types. Similar results involve range-restricted queries. 1 Introduction Complex objects are increasingly part of advanced database systems. They provide the structural core of object-oriented databases. Several query languages for complex objects have been propo...

A logic based language for manipulating complex objects constructed using set and tuple constructors is introduced. A key feature of the COL language is the use of base and derived data functions. Under some stratification restrictions, the semantics of programs is given by a minimal and justified model that can be computed using a finite sequence of fixpoints. The language is extended using external functions and predicates. An implementation of COL in a functional language is briefly discussed.