Anonymizing continuous queries with delay-tolerant mix-zones over road networks

This paper presents a delay-tolerant mix-zone framework for protecting the location privacy of mobile users against continuous query correlation attacks. First, we describe and analyze the continuous query correlation attacks (CQ-attacks) that perform query correlation based inference to break the anonymity of road network-aware mix-zones. We formally study the privacy strengths of the mix-zone anonymization under the CQ-attack model and argue that spatial cloaking or temporal cloaking over road network mix-zones is ineffective and susceptible to attacks that carry out inference by combining query correlation with timing correlation (CQ-timing attack) and transition correlation (CQ-transition attack) information. Next, we introduce three types of delay-tolerant road network mix-zones (i.e., temporal, spatial and spatio-temporal) that are free from CQ-timing and CQ-transition attacks and in contrast to conventional mix-zones, perform a combination of both location mixing and identity mixing of spatially and temporally perturbed user locations to achieve stronger anonymity under the CQ-attack model. We show that by combining temporal and spatial delay-tolerant mix-zones, we can obtain the strongest anonymity for continuous queries while making acceptable tradeoff between anonymous query processing cost and temporal delay incurred in anonymous query processing. We evaluate the proposed techniques through extensive experiments conducted on realistic traces produced by GTMobiSim on different scales of geographic maps. Our experiments show that the proposed techniques offer high level of anonymity and attack resilience to continuous queries.     

On three classes of division queries involving ordinal preferences

In this paper, we are interested in taking preferences into account for a family of queries inspired by the relational division. A division query aims at retrieving the elements associated with a specified set of values and usually the results remain not discriminated. So, we suggest the introduction of preferences inside such queries with the following specificities: (i) the user gives his/her preferences in an ordinal way and (ii) the preferences apply to the divisor which is defined as a hierarchy of sets. Different uses of the hierarchy are investigated, which leads to queries conveying different semantics and the property of the result in terms of a quotient is studied. Special attention is paid to the implementation of such extended division queries using a regular database management system along which some experiments to support the feasibility of the approach. Moreover, the issue of empty or overabundant answers is dealt with.     

Scalable processing of continuous K-nearest neighbor queries with uncertain velocity

Continuous K-nearest neighbor (CKNN) query is an important type of spatio-temporal queries. Given a time interval [t_s, t_e] and a moving query object q, a CKNN query is to find the K-nearest neighbors (KNNs) of q at each time instant within [t_s, t_e]. In this paper, we focus on the issue of scalable processing of CKNN queries over moving objects with uncertain velocity. Due to the large amount of CKNN queries that need to be evaluated concurrently, efficiently processing such queries inevitably becomes more complicated. We propose an index structure, namely the CI-tree, to predetermine and organize the candidates for each query issued by the user from anywhere and anytime. When the CKNN queries are evaluated, their corresponding candidates can be rapidly retrieved by traversing the CI-tree so that the processing time is greatly reduced. A comprehensive set of experiments is performed to demonstrate the effectiveness and the efficiency of the CI-tree.     

DHTJoin: processing continuous join queries using DHT networks

Continuous query processing in data stream management systems (DSMS) has received considerable attention recently. Many applications share the same need for processing data streams in a continuous fashion. For most distributed streaming applications, the centralized processing of continuous queries over distributed data is simply not viable. This paper addresses the problem of computing approximate answers to continuous join queries over distributed data streams. We present a new method, called DHTJoin, which combines hash-based placement of tuples in a Distributed Hash Table (DHT) and dissemination of queries by exploiting the embedded trees in the underlying DHT, thereby incurring little overhead. DHTJoin also deals with join attribute value skew which may hurt load balancing and result completeness. We provide a performance evaluation of DHTJoin which shows that it can achieve significant performance gains in terms of network traffic.     

Probabilistic filters: A stream protocol for continuous probabilistic queries

Pervasive applications, such as natural habitat monitoring and location-based services, have attracted plenty of research interest. These applications, which deploy a lot of sensor devices to collect data from external environments, often have limited network bandwidth and battery resources. The sensors also cannot record accurate values. The uncertainty of data captured by a sensor should thus be considered for query evaluation. To this end, probabilistic queries, which consider data impreciseness and provide statistical guarantees in answers, have been recently studied.     

The Train Benchmark: cross-technology performance evaluation of continuous model queries

In model-driven development of safety-critical systems (like automotive, avionics or railways), well-formedness of models is repeatedly validated in order to detect design flaws as early as possible. In many industrial tools, validation rules are still often implemented by a large amount of imperative model traversal code which makes those rule implementations complicated and hard to maintain. Additionally, as models are rapidly increasing in size and complexity, efficient execution of validation rules is challenging for the currently available tools. Checking well-formedness constraints can be captured by declarative queries over graph models, while model update operations can be specified as model transformations. This paper presents a benchmark for systematically assessing the scalability of validating and revalidating well-formedness constraints over large graph models. The benchmark defines well-formedness validation scenarios in the railway domain: a metamodel, an instance model generator and a set of well-formedness constraints captured by queries, fault injection and repair operations (imitating the work of systems engineers by model transformations). The benchmark focuses on the performance of query evaluation, i.e. its execution time and memory consumption, with a particular emphasis on reevaluation. We demonstrate that the benchmark can be adopted to various technologies and query engines, including modeling tools; relational, graph and semantic databases. The Train Benchmark is available as an open-source project with continuous builds from https://github.com/FTSRG/trainbenchmark.     

对位置信息服务的连续查询攻击算法

为了解决连续查询攻击算法给位置信息服务(LBS)带来的安全隐患,基于已有的k-匿名化Cloaking算法提出了一种新的连续查询攻击算法--CQACA。该算法首先利用熵和查询匿名度量定义了查询识别率的目标函数,并结合元胞蚁群给出了目标函数的求解算法。最后,利用移动对象数据生成器进行实验,深入研究了影响CQACA的关键因素,同时对比分析了该算法与Cloaking算法的性能差异:CQACA与实际数据的误差为13.27%,而Cloaking算法则为17.35%。结果表明CQACA具有一定的有效性。     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

Telecommunications service requirements: Principles for managing complexity

Telecommunications services are complex and rapidly becoming more so. If we wish to apply formal methods of requirements engineering in the telecommunications domain, then the primary obstacle we face is the sheer complexity of the behaviour to be described. This paper focuses on one kind of telecommunications system, thelong-distance telephone network (LDTN), and presents several ways of managing complexity in LDTN requirements. The alleviation of complexity comes from careful application of some general principles of requirements engineering. At the same time that these principles help us manage complexity, the productive focus on complexity enhances the motivation for these principles.     

Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t _s , t _e ] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t _s , t _e ]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t _s , t _e ]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.     

SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams

This paper presents the scalable on-line execution (SOLE) algorithm for continuous and on-line evaluation of concurrent continuous spatio-temporal queries over data streams. Incoming spatio-temporal data streams are processed in-memory against a set of outstanding continuous queries. The SOLE algorithm utilizes the scarce memory resource efficiently by keeping track of only the significant objects. In-memory stored objects are expired (i.e., dropped) from memory once they become insignificant. SOLE is a scalable algorithm where all the continuous outstanding queries share the same buffer pool. In addition, SOLE is presented as a spatio-temporal join between two input streams, a stream of spatio-temporal objects and a stream of spatio-temporal queries. To cope with intervals of high arrival rates of objects and/or queries, SOLE utilizes a load-shedding approach where some of the stored objects are dropped from memory. SOLE is implemented as a pipelined query operator that can be combined with traditional query operators in a query execution plan to support a wide variety of continuous queries. Performance experiments based on a real implementation of SOLE inside a prototype of a data stream management system show the scalability and efficiency of SOLE in highly dynamic environments. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

连续空间查询的位置隐私保护综述

在移动互联网中,移动用户把个人位置信息发送到位置服务提供者并通过空间查询获取兴趣点数据;在连续空间查询中,用户沿着轨迹提交多个位置信息,这导致了严重的用户隐私风险。近年来,连续空间查询的位置隐私保护技术成为无线网络安全和隐私领域的研究热点。首先介绍了位置服务中的空间查询和隐私威胁;归纳了连续空间查询的隐私保护模型,并比较了对应的隐私保护方法。最后介绍了发展趋势并指明了未来的研究方向。     

Dispatching stream operators in parallel execution of continuous queries

Data stream is a continuous, rapid, time-varying sequence of data elements which should be processed in an online manner. These matters are under research in Data Stream Management Systems (DSMSs). Single processor DSMSs cannot satisfy data stream applications?? requirements properly. Main shortcomings are tuple latency, tuple loss, and throughput. In our previous publications, we introduced parallel execution of continuous queries to overcome these problems via performance improvement, especially in terms of tuple latency. We scheduled operators in an event-driven manner which caused system performance reduction in periods between consecutive scheduling instances. In this paper, a continuous scheduling method (dispatching) is presented to be more compatible with the continuous nature of data streams as well as queries to improve system adaptivity and performance. In a multiprocessing environment, the dispatching method forces processing nodes (logical machines) to send partially-processed tuples to next machines with minimum workload to execute the next operator on them. So, operator scheduling is done continuously and dynamically for each tuple processed by each operator. The dispatching method is described, formally presented, and its correctness is proved. Also, it is modeled in PetriNets and is evaluated via simulation. Results show that the dispatching method significantly improves system performance in terms of tuple latency, throughput, and tuple loss. Furthermore, the fluctuation of system performance parameters (against variation of system and stream characteristics) diminishes considerably and leads to high adaptivity with the underlying system.     

Human-agent service matching using natural language queries: system test and training

Smart environments, ambient intelligence and intelligent agents leave the user lost between large amounts of services. Ad-hoc networks, mobile agents and mobile devices make the set of available services dynamic over time and space, increasing the user’s problems to find the service he needs. Earlier, we presented a ServiceMatcher that can find the agent best fitting to the user’s natural language request. This paper presents performance results of the ServiceMatcher. The test queries come from human users in a realistic scenario (see our other paper in this issue). With a short training of the agent vocabularies, over 80% correct service matches are found.     

Maintaining consistent results of continuous queries under diverse window specifications

Continuous queries applied over nonterminating data streams usually specify windows in order to obtain an evolving–yet restricted–set of tuples and thus provide timely and incremental results. Although sliding windows get frequently employed in many user requests, additional types like partitioned or landmark windows are also available in stream processing engines. In this paper, we set out to study the existence of monotonic-related semantics for a rich set of windowing constructs in order to facilitate a more efficient maintenance of their changing contents. After laying out a formal foundation for expressing windowed queries, we investigate update patterns observed in most common window variants as well as their impact on adaptations of typical operators (like windowed join, union or aggregation), thus offering more insight towards design and implementation of stream processing mechanisms. Furthermore, we identify syntactic equivalences in algebraic expressions involving windows, to the potential benefit of query optimizations. Finally, this framework is validated for several windowed operations against streaming datasets with simulations at diverse arrival rates and window specifications, providing concrete evidence of its significance.     

Adaptive two-level optimization for selection predicates of multiple continuous queries

A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Query processing for such a data stream should also be continuous and rapid, which requires strict time and space constraints. In order to guarantee these constraints, we have proposed a new scheme called an Attribute Selection Construct (ASC) for an attribute of a data stream in our previous study (Lee and Lee, Information Sciences 178:2416?C2432, 2008). As its optimization technique, this paper proposes the new strategy that determines the evaluation order of multiple ASC??s for a given query set at two different levels??macro and micro levels. Based on the two levels, it also proposes two different strategies??macro-sequence and hybrid-sequence??that find the optimized full evaluation sequence of all the ASC??s. In addition, it provides the adaptive strategy that periodically rearranges the evaluation sequence of multiple ASC??s. The performance of the proposed technique is verified by a series of experiments.     

On query processing in wireless sensor networks using classes of quality of queries

This paper introduces the concept of quality of queries (QoQs) towards a more adaptive query processing in wireless sensor networks (WSNs). This approach aims at the intelligent consumption of the limited resources (energy and memory) available in these networks while still delivering a reasonable level of data quality as expected by client applications. In a nutshell, the concept of QoQ stipulates that the results of different queries injected into the same WSN can be tailored according to different criteria, in particular the levels of query result accuracy and energy consumption. For this purpose, four classes of QoQ (CoQoQ) are specified having in mind distinct requirements in terms of these criteria. To allow the implementation of these classes in a real WSN setting, a new novelty-detection based algorithm, referred to as AdaQuali (which stands for “ADAptive QUALIty control for query processing in WSN”), is also proposed in a manner as to control the sensor node activities through the dynamic adjustment of their rates of data collection and transmission. In order to validate the novel approach, simulations with a prototype implemented in Sinalgo have been conducted over real temperature data. The results achieved evidence the suitability of the proposal and point to gains of up to 66.76%, for different CoQoQ, in terms of reduction in energy consumption.     

Alpha: an extension of relational algebra to express a class ofrecursive queries

An extension of E.F. Codd's relational algebra (1970) with an alpha (α) operator is presented that allows a large class of natural and useful recursive queries to be expressed, and yet has the property of being efficiently implementable. Formally, this class is a superset of linear recursive queries. Intuitively, this class comprises queries that examine transitive relationships between various instances of an entity. It is believed that this class covers many natural and interesting recursive queries. Examples of such queries include determining parts requirements for manufacturing a product, finding the critical path in a project management network, finding the shortest path between two cities, verifying connectivity between two points of a circuit, etc     

Approximate processing of massive continuous quantile queries over high-speed data streams

Quantile computation has many applications including data mining and financial data analysis. It has been shown that an /spl epsi/-approximate summary can be maintained so that, given a quantile query (/spl phi/,/spl epsi/), the data item at rank /spl lceil//spl phi/N/spl rceil/ may be approximately obtained within the rank error precision /spl epsi/N over all N data items in a data stream or in a sliding window. However, scalable online processing of massive continuous quantile queries with different /spl phi/ and /spl epsi/ poses a new challenge because the summary is continuously updated with new arrivals of data items. In this paper, first we aim to dramatically reduce the number of distinct query results by grouping a set of different queries into a cluster so that they can be processed virtually as a single query while the precision requirements from users can be retained. Second, we aim to minimize the total query processing costs. Efficient algorithms are developed to minimize the total number of times for reprocessing clusters and to produce the minimum number of clusters, respectively. The techniques are extended to maintain near-optimal clustering when queries are registered and removed in an arbitrary fashion against whole data streams or sliding windows. In addition to theoretical analysis, our performance study indicates that the proposed techniques are indeed scalable with respect to the number of input queries as well as the number of items and the item arrival rate in a data stream.