{'fraction_non_alphanumeric': 0.03482880755608028, 'fraction_numerical': 0.013085399449035813, 'mean_word_length': 4.597466960352423, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Continuous k-Nearest Neighbor Queries in Wireless Environments

Objectives: Network Coding-based Spatial Air Index (NCSAI) has been proposed for improving query performance of continuous k-nearest neighbor queries in road networks. Methods: Due to unreliable nature of wireless links, network coding has been playing an important role in wireless environments and improves scalability and throughput. In this work, NCSAI has been adapted using XOR-based network coding because it is simple and efficient coding strategy. Findings: Experiments have been conducted for evaluating query performance, the experimental result show that performance of NCSAI better than state-of-the-art Network Partition Index (NPI). Improvements: We can improve the performance of NCSAI by adapting an efficient network coding strategies.


Introduction
Spatial query processing in wireless mobile environments has been a challenging issue due to mobility, limited bandwidth, low energy and capacity. Wireless broadcast strategies are classified into push-based, pull-based and hybrid scheduling [1][2][3] . However, these strategies have been suffered from own limitations and sequential data access. Various scheduling strategies have been adapted for spatial queries in Euclidian space 4,5 . However, in realtime applications, query processing in road networks is essential. Recently, air index adapted for shortest path queries in road networks based on live traffic, but it doesn't address the other queries like range queries and k-nearest neighbor queries and continues k-nearest neighbor queries 6 . Based on air index, NPI adapted for various spatial queries in road networks, but it doesn't address reliability and well scheduling strategy when increase large number of data objects in a broadcast system 7 . Motivated by this observation, NCSAI proposed for spatial queries in road networks. The overall idea of this work is explained as follows. The original road networks may contain various data objects such as restaurants, shopping-malls, hospitals, gas-stations and schools, and these are classified into general and specific based on client's requirement, and then compute cut-off point 8 . Using grid partition strategy, original road network partitioned into small grid cells, and pre-computed general information such as diameter of each cell and minimum/maximum network distance between every pair of cells that will be carried by NCSAI. On server site, we incorporate XOR-based network coding into broadcast scheduling program, and broadcast general and specific data objects of NCSAI with network connectivity information of each cell using Hybrid Broadcast (HB) scheduling. On client site, once a client receives a query request from a mobile user, then it search query result in its cache, if found then it return query result. If not found, then the client tune into channel, retrieves required information and perform decoding. Finally, process the query using Dijkstra's shortest path algorithm. If required data doesn't broadcast while tuning, then the client send request query to server via pull-based scheduling. While broadcasting, if any free time-slots exist then server broadcast the client requested data objects (i.e., specific data objects) along with general data objects of NCSAI by considering longest waiting time and priority order, and updates optimal cut-off point.
The contribution of this paper is summarized as follows: • Propose NCSAI for spatial queries in road networks.
• Propose continuous k-nearest neighbor query searching algorithm at client site. • Experiments have been conducted using real road networks data and compared performance of NCSAI with state-of-the-art NPI.

Data Dissemination on Wireless channel using NCSAI
The original road networks may contain large number of data objects and these are classified into general and specific, and compute cut-off point. Using grid partition strategy, original road networks is partitioning into small grid cells and pre-computes the diameter of each cell and minimum/maximum network distance between every pair of cells, and then form NPI called NCSAI 7 . Now XOR-based network coding is incorporate into hybrid broadcast scheduling program, and then broadcast NCSAI with data segment on wireless channel. XOR-based network coding is simple and efficient strategy compared to other network coding strategies and improves scalability, throughput and robustness of the network 9-14 .

Processing of Continuous k-nearest neighbor query using NCSAI
Continuous k-nearest neighbor query has been used in many real-time applications 15 . For example, a mobile user continuously sending a query request to nearest mobile users while moving on the road networks called as Ck-NNquery. In Ck-NNquery, once a mobile user receives a query from a client then initially it finds a query located grid cell and query path (v 1 , v 2,… v L ). Based on the query path, the client will find data objects in each segment in the road network. Each segment in the network called as valid interval. All valid intervals contain start/ end points, and these are called as split points. Assume that, mobile user is located in same safe region and request Ck-NNquery is not efficient, because Ck-NNquery result is same. That means if the mobile user doesn't leave from the safe region then Ck-NNcandidates and partial road network is same. Hence, in this work we assume that, the mobile user will tune into channel and retrieves new candidates cells only, when a mobile user moves away from the safe region with maximum distance. i.e., The mobile users will tune into channel only if the condition i.e., ||q, q 1 || ≤ (UB(d max )-d k )/2 is not satisfied. In this simulation, assume that the clients' locations are located at network nodes' and easily extend to support cases where clients' locations are locating along the network edges as shown in Figure 1, and used Dijkstra's shortest path algorithm because it is simple and efficient for small sub-graphs. % receive_query() -a client waits for receiving a query from mobile user, t-time, C q -valid grid cells from a query point q, R q -valid range query result from a query point q,α q,i -minimum or maximum network distance from a query point q, start -starting point, L -ending point, v start -starting vertex, n and i-integer, G 1 -valid query path, G 11 -query path from starting point to ending point, P -path % % perform encoding and decoding at server and client sites respectively using XOR-network coding %

Performance Evaluations
Experiments have been conducted for evaluating query performance using ns-2 simulator with window 7 platform, 2.33G Intel Core 2 CPU and 3.2 GB RAM.

Experimental setup
In this simulation, real road networks data set namely OLdenburg (OL) and CALifornia (CAL) have been considered. The OL contains 6,105 nodes and 7,035 edges, and CAL contains 21,048 nodes and 21,693 edges 16 respectively. The evolution is run on simulator which contains server, broadcast channel and clients. For simulating results, 100 clients and 500 random queries are used. In this work, we considered: 1. size of data object is fixed at 128 bytes; 2. a set of data objects are randomly generated and uniformly distributed; 3. query issuing points are always at the network nodes; 4. network bandwidth is dynamic; and 5. tuning time and access latency are measured in terms of number of bytes of data transfer in a wireless channel.

Cycle Length
In this simulation, cycle length plays an important because it is directly impacts on the access latency. The original road network is partitioning into 2 i 2 i uniform grid cells, where i vary from 0 to 4, (i.e., the number of grids ranges from 1, to 4, to 16, to 64, and to 256). The number of grid cells in a network is set to 4 i and then mapped into Hilbert curve order. The server disseminates data using (1, m) strategy by setting optimal m value 1 . In this work, the performance of NCSAI compared with state-of-the-art NPI based on grid sizes such as 4 2 , 4 3 , and 4 4 respectively, and these are denoted as NCSAI/NPI-16, NCSAI/NPI-64 and NCSAI/NPI-256. The parameter settings and broadcast cycle length as shown in Table 1 and 2 respectively.

Ck-NNquery
In Ck-NN query, Query Path Length Ratio (QPLR) is defined as the ratio of the query path length to the diameter of the road network. The query path is generated by the shortest path between two randomly selected nodes in the network. In this experiment, object density is fixed at 0.1 and QPLR ranges from 0.01 to 0.2. The performance for the OL and CAL data sets for answering Ck-NN query queries with k = 10 as shown in Figure 2. As for tuning time, performance of NCSAI-64 varies as QPLR changes because it reduces search space. But, the tuning time of NCSAI-64 has better than state-of-the-art NPI-64. However, NCSAI-64 has been suffered from longer access latency because Ck-NN algorithm under NCSAI index allows the clients to tune into the channel, update the partial road network and Ck-NN candidates only when they arrive at the first point of a new SVS. We also evaluate the performance of NCSAI-64 with state-of-the-art NPI-64 for supporting Ck-NN queries with different k values. In this experiment, we fixed QPLR at 0.1, k is varying from 1 to 15, and object density is fixed at 0.1 for both OL and CAL shown in Figure 3. As for tuning time, NCSAI-64 has more energy efficient compared to state-of-the-art NPI-64 for different k because the pre-computation of NCSAI helps to clients prune the needless regions and avoid to clients keeping tuning into the channel rapidly as the clients move to a new position. However, access latency of NCSAI-64 has better than state-of-the-art NPI-64 with different k.

Conclusions
In this work, we proposed NCSAI for continuous k-nearest neighbor queries in road networks. The experimental results show that the performance of NCSAI better than state-of-the-art NPI because NCSAI has been utilized the usages of network coding for improving query performance in wireless environment. In future, we can extent NCSAI by adapting advanced spatial queries in road networks.