Effective protocols for kNN search on broadcast multi-dimensional index trees

In a wireless mobile environment, data broadcasting provides an efficient way to disseminate data. Via data broadcasting, a server can provide location-based services to a large client population in a wireless environment. Among different location-based services, the k nearest neighbors (kNN) search is important and is used to find the k closest objects to a given point. However, the kNN search in a broadcast environment is particularly challenging due to the sequential access to the data on a broadcast channel. We propose efficient protocols for the kNN search on a broadcast R-tree, which is a popular multi-dimensional index tree, in a wireless broadcast environment in terms of latency and tuning time as well as memory usage. We investigate how a server schedules the broadcast and provide the corresponding kNN search algorithms at the mobile clients. One of our kNN search protocols further allows a kNN search to start at an arbitrary time instance and it can skip the waiting time for the beginning of a broadcast cycle, thereby reducing the latency. The experimental results validate that our mechanisms achieve the objectives.     

Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services

Traditional nearest-neighbor (NN) search is based on two basic indexing approaches: object-based indexing and solution-based indexing. The former is constructed based on the locations of data objects: using some distance heuristics on object locations. The latter is built on a precomputed solution space. Thus, NN queries can be reduced to and processed as simple point queries in this solution space. Both approaches exhibit some disadvantages, especially when employed for wireless data broadcast in mobile computing environments. In this paper, we introduce a new index method, called the grid-partition index, to support NN search in both on-demand access and periodic broadcast modes of mobile computing. The grid-partition index is constructed based on the Voronoi diagram, i.e., the solution space of NN queries. However, it has two distinctive characteristics. First, it divides the solution space into grid cells such that a query point can be efficiently mapped into a grid cell around which the nearest object is located. This significantly reduces the search space. Second, the grid-partition index stores the objects that are potential NNs of any query falling within the cell. The storage of objects, instead of the Voronoi cells, makes the grid-partition index a hybrid of the solution-based and object-based approaches. As a result, it achieves a much more compact representation than the pure solution-based approach and avoids backtracked traversals required in the typical object-based approach, thus realizing the advantages of both approaches. We develop an incremental construction algorithm to address the issue of object update. In addition, we present a cost model to approximate the search cost of different grid partitioning schemes. The performances of the grid-partition index and existing indexes are evaluated using both synthetic and real data. The results show that, overall, the grid-partition index significantly outperforms object-based indexes and solution-based indexes. Furthermore, we extend the grid-partition index to support continuous-nearest-neighbor search. Both algorithms and experimental results are presented. Edited by R. Guting     

Searching continuous nearest neighbors in road networks on the air

Recently, people have begun to deal with location-based queries (LBQs) under broadcast environments. To the best of our knowledge, most of the existing broadcast-based LBQ methods are aimed at Euclidean spaces and cannot be readily extended to road networks. This paper takes the first step toward processing Continuous Nearest Neighbor queries in road Networks under wireless Broadcast environments (CN³B). Our method leverages the key properties of Network Voronoi Diagram (NVD). We first present an efficient method to partition the NVD structure of the underlying road networks into a set of grid cells and number the grid cells obtained, based on which we further propose an NVD-based Distributed air Index (NVD-DI) to support CN³B query processing. Finally, we propose an efficient algorithm on the client side to process CN³B queries. Extensive simulation experiments have been conducted to demonstrate the efficiency of our approach. The results show that our proposed method is about 4 and 7.6 times more efficient than a less-sophisticated D-tree air index based method, in access latency and tuning time, respectively.     

A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting

The main requirements for spatial query processing via mobile terminals include rapid and accurate searching and low energy consumption. Most location-based services (LBSs) are provided using an on-demand method, which is suitable for light-loaded systems where contention for wireless channels and server processing is not severe. However, as the number of users of LBSs increases, performance deteriorates rapidly since the servers’ capability to process queries is limited. Furthermore, the response time of a query may significantly increase with the concentration of users’ queries in a server at the same time. That is because the server has to check the locations of users and potential objects for the final result and then individually send answers to clients via a point-to-point channel. At this time, an inefficient structure of spatial index and searching algorithm may incur an extremely large access latency. To address this problem, we propose the Hierarchical Grid Index (HGI), which provides a light-weight sequential location-based index structure for efficient LBSs. We minimize the index size through the use of hierarchical location-based identifications. And we support efficient query processing in broadcasting environments through sequential data transfer and search based on the object locations. We also propose Top-Down Search and Reduction-Counter Search algorithms for efficient searching and query processing. HGI has a simple structure through elimination of replication pointers and is therefore suitable for broadcasting environments with one-dimensional characteristics, thus enabling rapid and accurate spatial search by reducing redundant data. Our performance evaluation shows that our proposed index and algorithms are accurate and fast and support efficient spatial query processing.     

An indexing scheme for energy-efficient processing of content-based retrieval queries on a wireless data stream

Wireless data broadcasting is a popular data delivery approach in mobile computing environments, where the broadcasting servers usually adopt indexing schemes for mobile clients to energy-efficiently access data on a wireless broadcast stream. However, conventional indexing schemes use primary key attribute values to construct tree structures. Therefore, these schemes do not support content-based retrieval queries such as partial-match queries and range-queries. This paper proposes an indexing method that supports content-based retrieval queries on a wireless data stream. The method uses a tree-structured index, called B2V-Tree, which is composed of bit-vectors that are generated from data records through multi-attribute hashing. Through analysis and experiments, the effectiveness of the proposed method is shown.     

一种障碍空间数据库中的连续反k近邻查询方法

随着智能移动设备和无线定位技术的飞速发展,使用基于位置服务应用的用户越来越多.特别地,不同于传统的针对固定位置的快照查询,移动的用户往往基于移动轨迹发出连续的查询.在真实和虚拟的空间环境中,障碍物的影响都是广泛存在的,障碍空间内的查询处理技术得到了越来越多的关注,其中,障碍空间内的连续反k近邻查询处理有着重要的应用.对障碍空间中的连续反k近邻查询问题进行了定义和系统的研究,通过定义控制点和分割点,提出了针对该问题的处理框架.进一步地,提出了一系列的过滤和求精算法,包括剪枝数据集、获取障碍物、剪枝和计算控制点和更新结果集等处理策略.基于多种数据集对所提出的算法进行了实验评估.与针对每个数据点进行k 近邻计算的基本方法相比,这些方法可以大幅度提高查询处理的CPU 和I/O 效率.     

Distributed Searching of Multi-dimensional Data: A Performance Evaluation Study

In this paper we present a data structure for searching in multi-dimensional point sets in distributed environments and discuss its experimental evaluation also through a comparison with previous proposals. The data structure is based on an extension ofk-d trees. The technological reference context is a distributed environment where multicast (i.e., restricted broadcast) is allowed, but it is also shown how to avoid using it. The data structure supports exact, partial, and range search queries with a complexity that is optimal in a distributed sense. The set of multidimensional points is managed in a scalable way, i.e., it can be dynamically enlarged with insertion of new points. We also propose new performance measures for the comparative evaluation of the efficiency with which a data structure is distributed over a communication network.     

Location privacy: going beyond K-anonymity,cloaking and anonymizers

With many location-based services, it is implicitly assumed that the location server receives actual users locations to respond to their spatial queries. Consequently, information customized to their locations, such as nearest points of interest can be provided. However, there is a major privacy concern over sharing such sensitive information with potentially malicious servers, jeopardizing users’ private information. The anonymity- and cloaking-based approaches proposed to address this problem cannot provide stringent privacy guarantees without incurring costly computation and communication overhead. Furthermore, they require a trusted intermediate anonymizer to protect user locations during query processing. This paper proposes a fundamental approach based on private information retrieval to process range and K-nearest neighbor queries, the prevalent queries used in many location-based services, with stronger privacy guarantees compared to those of the cloaking and anonymity approaches. We performed extensive experiments on both real-world and synthetic datasets to confirm the effectiveness of our approaches.     

Query processing optimization in broadcasting XML data in mobile communications

Todays, XML as a de facto standard is used to broadcast data over mobile wireless networks. In these networks, mobile clients send their XML queries over a wireless broadcast channel and recieve their desired XML data from the channel. However, downloading the whole XML data by a mobile device is a challenge since the mobile devices used by clients are small battery powered devices with limited resources. To meet this challenge, the XML data should be indexed in such a way that the desired XML data can be found easily and only such data can be downloaded instead of the whole XML data by the mobile clients. Several indexing methods are proposed to selectively access the XML data over an XML stream. However, the existing indexing methods cause an increase in the size of XML stream by including some extra information over the XML stream. In this paper, a new XML stream structure is proposed to disseminate the XML data over a broadcast channel by grouping and summarizing the structural information of XML nodes. By summarizing such information, the size of XML stream can be reduced and therefore, the latency of retrieving the desired XML data over a wirless broadcast channel can be reduced. The proposed XML stream structure also contains indexes in order to skip from the irrelevant parts over the XML stream. It therefore can reduce the energy consumption of mobile devices in downloading the results of XML queries. In addition, our proposed XML stream structure can process different types of XML queries and experimental results showed that it improves the performace of XML query processing over the XML data stream compared to the existing research works in terms of access and tuning times.

     

P2PSpaceTwist:一种主动式用户协作的位置隐私保护方法

随着定位技术和无线移动设备的飞速发展,移动用户能够随时随地获取位置信息,也可能泄露位置信息,甚至导致个人隐私的泄露。提出了一种主动式用户协作的位置隐私保护方法—P2PSpaceTwist,该方法采用了一种带新鲜性的主动式协商机制,通过该机制用户主动与邻居协商,收集邻居信息并广播自身信息;当满足用户的匿名需求后,使用匿名区域内的随机位置代替用户的真实位置并发送给随机选定的代理,通过代理向位置服务器提供商发送增量式的近邻查询,从而获得精确的结果集。实验结果表明,P2PSpaceTwist能够较快地实现匿名查询并获得较精确的结果集,与其他位置隐私保护方法相比,P2PSpaceTwist的通信开销较低。     

Dynamic priority scheduling of periodic queries in on-demand data dissemination systems

As an important wireless data broadcast technique, on-demand broadcast has been widely used for dynamic and large-scale data dissemination. An important class of emerging data broadcast applications requires monitoring multiple data items continuously in order to support data-driven decision making. Since wireless bandwidth is a precious shared medium, an important problem to solve is how to disseminate data to periodic queries, so that all the requests can be satisfied while the bandwidth consumption is minimized. In this paper, we first propose a new real-time scheduling algorithm called EDFS, which is a variant of the classic EDF [24] algorithm. Based on EDFS, we propose a novel on-line broadcast scheduling algorithm, called EDFS-BS. To our best knowledge, EDFS-BS is the first dynamic priority based broadcast scheduling algorithm that can be utilized to satisfy the timing constraints of periodic queries. We also propose a bandwidth utilization based schedulability test for EDFS-BS, which is used to ensure timing predictability of a periodic query set. Extensive experiments have been conducted to compare EDFS-BS versus existing solutions with comparable quality. The results show that EDFS-BS outperforms them considerably in terms of wireless bandwidth consumption and query service ratio.     

Domain Monotonicity and the Performance of Local Solutions Strategies for CDPS-based Distributed Sensor Interpretation and Distributed Diagnosis

The growth in computer networks has created the potential to harness a great deal of computing power, but new models of distributed computing are often required. Cooperative distributed problem solving (CDPS) is the subfield of multi-agent systems (MAS) that is concerned with how large-scale problems can be solved using a network of intelligent agents working together. Building CDPS systems for real-world applications is still very difficult, however, in large part because the effects that domain and strategy characteristics have on the performance of CDPS systems are not well understood. This paper reports on the first results from a new simulation-based analysis system that has been created to study the performance of CDPS-based distributed sensor interpretation (DSI) and distributed diagnosis (DD). To demonstrate the kind of results that can be obtained, we have investigated how the monotonicity of a domain affects the performance of a potentially very efficient class of strategies for CDPS-based DSI/DD. Local solutions strategies attempt to limit communications among the agents by focusing on using the agents' local solutions to produce global solutions. While these strategies have been described as being important for effective CDPS-based DSI/DD, they need not perform well if a domain is nonmonotonic. We had previously suggested that the reason they have performed well in several research systems was that many DSI/DD domains are what we termed nearly monotonic. In this paper, we will provide quantitative results that relate the performance of local solutions strategies to the monotonicity of a domain. The experiments confirm that domain monotonicity can be important to consider, but they also show that it is possible for these strategies to be effective even when domains are relatively nonmonotonic. What is required is that the agents receive a significant fraction of the data that is relevant to their subproblems. This has important implications for the design of DSI/DD systems using local solutions strategies. In addition, while the work indicates that many DSI/DD domains are likely to be nearly monotonic according to our original definitions, it also shows that these measures are not as predictive of performance as other measures we define. This means that near monotonicity alone does not explain why local solutions strategies have performed well in previous systems. Instead, a likely explanation is that these systems typically involved only a small number of agents.     

Nearest neighbor queries with peer-to-peer data sharing in mobile environments

Nearest neighbor queries, such as determining the proximity of stationary objects (e.g., restaurants and gas stations) are an important class of inquiries for supporting location-based services. We present a novel approach to support nearest neighbor queries from mobile hosts by leveraging the sharing capabilities of wireless ad-hoc networks. We illustrate how previous query results cached in the local storage of neighboring mobile users can be leveraged to either fully or partially compute and verify nearest neighbor queries at a local host. The feasibility and appeal of our technique is illustrated through extensive simulation results that indicate a considerable reduction of the query load on the remote database. Furthermore, the scalability of our approach is excellent because a higher density of mobile hosts increases its effectiveness.     

Voronoi-based range and continuous range query processing in mobile databases

With the wide availability of mobile devices (smart phones, iPhones, etc.), mobile location-based queries are increasingly in demand. One of the most frequent queries is range search which returns objects of interest within a pre-defined area. Most of the existing methods are based on the road network expansion method – expanding all nodes (intersections and objects) and computing the distance of each node to the query point. Since road networks are extremely complex, node expansion approaches are inefficient. In this paper, we propose a method, Voronoi Range Search (VRS) based on the Voronoi diagram, to process range search queries efficiently and accurately by partitioning the road networks to some special polygons. Then we further propose Voronoi Continuous Range (VCR) to satisfy the requirement for continuous range search queries (moving queries) based on VRS. Our empirical experiments show that VRS and VCR surpass all their rivals for both static and moving queries.     

Effective Data Placement for Wireless Broadcast

This paper investigates how to place data objects on air for wireless broadcast such that mobile clients can access the data in short latency. We first define and analyze the problem of wireless data placement, and also propose a measure, named Query Distance (QD), which represents the coherence degree of data set accessed by a query. We show that the problem is NP-complete, and then propose an effective data placement method that constructs the broadcast schedule by appending each query's data set in greedy way. We show through performance experiments that the proposed method reduces the access time of mobile query.     

Distributed text search using suffix arrays

Text search is a classical problem in Computer Science, with many data-intensive applications. For this problem, suffix arrays are among the most widely known and used data structures, enabling fast searches for phrases, terms, substrings and regular expressions in large texts. Potential application domains for these operations include large-scale search services, such as Web search engines, where it is necessary to efficiently process intensive-traffic streams of on-line queries. This paper proposes strategies to enable such services by means of suffix arrays. We introduce techniques for deploying suffix arrays on clusters of distributed-memory processors and then study the processing of multiple queries on the distributed data structure. Even though the cost of individual search operations in sequential (non-distributed) suffix arrays is low in practice, the problem of processing multiple queries on distributed-memory systems, so that hardware resources are used efficiently, is relevant to services aimed at achieving high query throughput at low operational costs. Our theoretical and experimental performance studies show that our proposals are suitable solutions for building efficient and scalable on-line search services based on suffix arrays.     

Mobiiscape: Middleware support for scalable mobility pattern monitoring of moving objects in a large-scale city

With the explosive proliferation of mobile devices such as smartphones, tablets, and sensor nodes, location-based services are getting even more attention than before, considered as one of the killer applications in the upcoming mobile computing era. Developing location-based services necessarily requires an effective and scalable location data processing technology. In this paper, we present Mobiiscape, a novel location monitoring system that collectively monitors mobility patterns of a large number of moving objects in a large-scale city to support city-wide mobility-aware applications. Mobiiscape provides an SQL-like query language named Moving Object Monitoring Query Language (MQL) that allows applications to intuitively specify Mobility Pattern Monitoring Queries (MPQs). Further, Mobiiscape provides a set of scalable location monitoring techniques to efficiently process a large number of MPQs over a large number of location streams. The scalable processing techniques include a (1) Place Border Index, a spatial index for quickly searching for relevant queries upon receiving location streams, (2) Place-Based Window, a spatial-purpose window for efficiently detecting primitive mobility patterns, (3) Shared NFA, a shared query processing technique for efficiently matching complex mobility patterns, and (4) Attribute Pre-matching Bitmap, an in-memory data structure for efficiently filtering out moving objects based on their attributes. We have implemented a Mobiiscape prototype system. Then, we show the usefulness of the system by implementing promising location-based applications based on it such as a ubiquitous taxicab service and a location-based advertising. Also, we demonstrate the performance benefit of the system through extensive evaluation and comparison.     

A Hybrid Index Technique for Power Efficient Data Broadcast

The intention of power conservative indexing techniques for wireless data broadcast is to reduce mobile client tune-in time while maintaining an acceptable data access time. In this paper, we investigate indexing techniques based on index trees and signatures for data disseminated on a broadcast channel. Moreover, a hybrid indexing method combining strengths of the signature and the index tree techniques is proposed. Different from previous studies, our research takes into consideration of two important data organization factors, namely, clustering and scheduling. Cost models for the three indexing methods are derived for various data organization accommodating these two factors. Based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conservative indexing of various data organization on wireless broadcast channels.     

Efficient query execution on broadcasted index tree structures

The continuous broadcast of data together with an index structure is an effective way of disseminating data in a wireless mobile environment. The index allows a mobile client to tune in only when relevant data is available on the channel and leads to reduced power consumption for the clients. This paper investigates the execution of queries on broadcasted index trees when query execution corresponds to a partial traversal of the tree. Queries exhibiting this behavior include range queries and nearest neighbor queries. We present two broadcast schedules for index trees and two query algorithms executed by mobile clients. Our solutions simultaneously minimize tuning time and latency and adapt to the client’s available memory. Experimental results using real and synthetic data compare results for a broadcast with node repetition to one without node repetition and they show how a priority-based data management can help reduce tuning time and latency.     

Supporting quantified queries in distributed databases

We show that some relational queries, which we call quantified queries are not well supported in distributed environments. We give a formal definition of quantified queries, propose a language in which to express said queries and provide a procedure to compute answers in this new language in the context of distributed databases. The proposed language is made up of high-level, declarative operators (called generalised quantifiers), and therefore it can be used in combination with several distributed frameworks. Our approach is designed to be as general as possible; it assumes horizontally partitioned relations, but nothing else, so no data placement or replication is used. We present an implementation and algorithms for the new language, propose some basic optimisations and give experimental results which show that the new approach is indeed quite efficient and scales well.