The optimal sequenced route query

Real-world road-planning applications often result in the formulation of new variations of the nearest neighbor (NN) problem requiring new solutions. In this paper, we study an unexplored form of NN queries named optimal sequenced route (OSR) query in both vector and metric spaces. OSR strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a particular order imposed on the types of the locations. We first transform the OSR problem into a shortest path problem on a large planar graph. We show that a classic shortest path algorithm such as Dijkstra’s is impractical for most real-world scenarios. Therefore, we propose LORD, a light threshold-based iterative algorithm, which utilizes various thresholds to prune the locations that cannot belong to the optimal route. Then we propose R-LORD, an extension of LORD which uses R-tree to examine the threshold values more efficiently. Finally, for applications that cannot tolerate the Euclidean distance as estimation and require exact distance measures in metric spaces (e.g., road networks) we propose PNE that progressively issues NN queries on different point types to construct the optimal route for the OSR query. Our extensive experiments on both real-world and synthetic datasets verify that our algorithms significantly outperform a disk-based variation of the Dijkstra approach in terms of processing time (up to two orders of magnitude) and required workspace (up to 90% reduction on average).     

k-Multi-preference query over road networks

Nowadays, the road network has gained more and more attention in the research area of databases. Existing works mainly focus on standalone queries, such as k-nearest neighbor queries over a single type of objects (e.g., facility like restaurant or hotel). In this paper, we propose a k-multi-preference (kMP) query over road networks, involving complex query predicates and multiple facilities. In particular, given a query graph, a kMP query retrieves of the top-k groups of vertices (of k facility types) satisfying the label constraints and their aggregate distances are the smallest. A naïve solution to this problem is to enumerate all combinations of vertices with k possible facility types and then select the one with the minimum sum distance. This method, however, incurs rather high computation cost due to exponential possible combinations. In addition, the existing solutions to other standalone queries are for a single type of facilities and cannot be directly used to answer kMP queries. Therefore, in this paper, we propose an efficient approach to process a kMP query, which utilizes an index with bounded space and reduces the computation cost of the shortest path queries. We also design effective pruning techniques to filter out false alarms. Through our extensive experiments, we demonstrate the efficiency and effectiveness of our proposed solutions.     

The effect of the asymmetry of road transportation networks on the traveling salesman problem

The routing of vehicles on road transportation networks is an area of great importance to transportation planners within scientific literature. This field includes well known and studied problems like traveling salesman problems or TSP or the more realistic asymmetric variant or ATSP, whose applications extend to other areas of transport and operations research. This work studies the effect that the asymmetry of road transportation networks, geographical location and territory have over TSP and ATSP methods. We conduct comprehensive experiments in order to assess the effects that these factors have on some of the best known algorithms for the TSP/ATSP. We demonstrate that all these factors have a significant influence in solution time and quality. Furthermore, we show that the solutions obtained with Euclidean matrices and those obtained with real distance matrices differ significantly.     

Efficient successor retrieval operations for aggregate query processing on clustered road networks

Get-Successors (GS) which retrieves all successors of a junction is a kernel operation used to facilitate aggregate computations in road network queries. Efficient implementation of the GS operation is crucial since the disk access cost of this operation constitutes a considerable portion of the total query processing cost. Firstly, we propose a new successor retrieval operation Get-Unevaluated-Successors (GUS), which retrieves only the unevaluated successors of a given junction. The GUS operation is an efficient implementation of the GS operation, where the candidate successors to be retrieved are pruned according to the properties and state of the algorithm. Secondly, we propose a hypergraph-based model for clustering successively retrieved junctions by the GUS operations to the same pages. The proposed model utilizes query logs to correctly capture the disk access cost of GUS operations. The proposed GUS operation and associated clustering model are evaluated for two different instances of GUS operations which typically arise in Dijkstra’s single source shortest path algorithm and incremental network expansion framework. Our simulation results show that the proposed successor retrieval operation together with the proposed clustering hypergraph model is quite effective in reducing the number of disk accesses in query processing.     

Dynamic path privacy protection framework for continuous query service over road networks

Many applications of location based services (LBSs), it is useful or even necessary to ensure that LBSs services determine their location. For continuous queries where users report their locations periodically, attackers can infer more about users’ privacy by analyzing the correlations of their query samples. The causes of path privacy problems, which emerge because the communication by different users in road network using location based services so, attacker can track continuous query information. LBSs, albeit useful and convenient, pose a serious threat to users’ path privacy as they are enticed to reveal their locations to LBS providers via their queries for location-based information. Traditional path privacy solutions designed in Euclidean space can be hardly applied to road network environment because of their ignorance of network topological properties. In this paper, we proposed a novel dynamic path privacy protection scheme for continuous query service in road networks. Our scheme also conceals DPP (Dynamic Path Privacy) users’ identities from adversaries; this is provided in initiator untraceability property of the scheme. We choose the different attack as our defending target because it is a particularly challenging attack that can be successfully launched without compromising any user or having access to any cryptographic keys. The security analysis shows that the model can effectively protect the user identity anonymous, location information and service content in LBSs. All simulation results confirm that our Dynamic Path Privacy scheme is not only more accurate than the related schemes, but also provide better locatable ratio where the highest it can be around 95 % of unknown nodes those can estimate their position. Furthermore, the scheme has good computation cost as well as communication and storage costs.Simulation results show that Dynamic Path Privacy has better performances compared to some related region based algorithms such as IAPIT scheme, half symmetric lens based localization algorithm (HSL) and sequential approximate maximum a posteriori (AMAP) estimator scheme.     

A link-based storage scheme for efficient aggregate query processing on clustered road networks

The need to have efficient storage schemes for spatial networks is apparent when the volume of query processing in some road networks (e.g., the navigation systems) is considered. Specifically, under the assumption that the road network is stored in a central server, the adjacent data elements in the network must be clustered on the disk in such a way that the number of disk page accesses is kept minimal during the processing of network queries. In this work, we introduce the link-based storage scheme for clustered road networks and compare it with the previously proposed junction-based storage scheme. In order to investigate the performance of aggregate network queries in clustered road networks, we extend our recently proposed clustering hypergraph model from junction-based storage to link-based storage. We propose techniques for additional storage savings in bidirectional networks that make the link-based storage scheme even more preferable in terms of the storage efficiency. We evaluate the performance of our link-based storage scheme against the junction-based storage scheme both theoretically and empirically. The results of the experiments conducted on a wide range of road network datasets show that the link-based storage scheme is preferable in terms of both storage and query processing efficiency.     

Practical voting rules with partial information

Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous work has typically assumed that voters send their complete set of preferences for computation, and in fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send a complete set of preferences due to communication limitations and willingness to keep as much information private as possible. The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly, we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments with simulated and real-world data show that this algorithm results in an average of 35% savings in communications, while guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in practice, close approximations are obtained.     

Drawing road networks with focus regions

Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region--such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems.     

Distributed query processing in flash-based sensor networks

Wireless sensor networks are used in a large array of applications to capture, collect, and analyze physical environmental data. Many existing sensor systems instruct sensor nodes to report their measurements to central repositories outside the network, which is expensive in energy cost. Recent technological advances in flash memory have given rise to the development of storagecentric sensor networks, where sensor nodes are equipped with high-capacity flash memory storage such that sensor data can be stored and managed inside the network to reduce expensive communication. This novel architecture calls for new data management techniques to fully exploit distributed in-network data storage. This paper describes some of our research on distributed query processing in such flash-based sensor networks. Of particular interests are the issues that arise in the design of storage management and indexing structures combining sensor system workload and read/write/erase characteristics of flash memory.     

Instance optimal query processing in spatial networks

The performance optimization of query processing in spatial networks focuses on minimizing network data accesses and the cost of network distance calculations. This paper proposes algorithms for network k-NN queries, range queries, closest-pair queries and multi-source skyline queries based on a novel processing framework, namely, incremental lower bound constraint. By giving high processing priority to the query associated data points and utilizing the incremental nature of the lower bound, the performance of our algorithms is better optimized in contrast to the corresponding algorithms based on known framework incremental Euclidean restriction and incremental network expansion. More importantly, the proposed algorithms are proven to be instance optimal among classes of algorithms. Through experiments on real road network datasets, the superiority of the proposed algorithms is demonstrated.     

Doubly periodic traveling waves in cellular neural networks with polynomial reactions

In a study (Szekely, 1965) [1] of the locomotion of salamanders, it is observed that a ‘doubly periodic traveling wave solution’ of a logical neural network can be used to explain a dynamic pattern of movements. We show here that nonlinear and nonlogical artificial neural network can also be built by means of reaction diffusion principles and existence or nonexistence of doubly periodic traveling waves can be guaranteed by adjusting parameters built into these networks. Our derivations for existence are based on implicit function theorems and the invariance properties of our model; while nonexistence is based on boundedness properties of the polynomial reaction term. We also give illustrative examples as well as comments on the differences between present results with those obtained for linear models studied earlier in Cheng and Lin (2009) [2] and [3].     

Top-k query evaluation in sensor networks under query response time constraint

Top-k query in a wireless sensor network is to find the k sensor nodes with the highest sensing values. To evaluate the top-k query in such an energy-constrained network poses great challenges, due to the unique characteristics imposed on its sensors. Existing solutions for top-k query in the literature mainly focused on energy efficiency but little attention has been paid to the query response time and its effect on the network lifetime. In this paper we address the query response time and its effect on the network lifetime through the study of the top-k query problem in sensor networks with the response time constraint. We aim at finding an energy-efficient routing tree and evaluating top-k queries on the tree such that the network lifetime is significantly prolonged, provided that the query response time constraint is met too. To do so, we first present a cost model of energy consumption for answering top-k queries and introduce the query response time definition. We then propose a novel joint query optimization framework, which consists of finding a routing tree in the network and devising a filter-based evaluation algorithm for top-k query evaluation on the tree. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithms, in terms of the total energy consumption, the maximum energy consumption among nodes, the query response time, and the network lifetime. The experimental results showed that there is a non-trivial tradeoff between the query response time and the network lifetime, and the joint query optimization framework can prolong the network lifetime significantly under a specified query response time constraint.     

Efficient skyline query processing in wireless sensor networks

How to process a skyline query efficiently has received considerable attention in recent years. A skyline query identifies a set of non-dominated data records in a multidimensional dataset. Whereas most previous studies have resolved this problem in a centralized environment, this work considers it in a distributed sensor network environment. An algorithm, known as Skyline Sensor Algorithm (SkySensor), is presented to efficiently retrieve skyline results from a sensor network. A cluster-based architecture is designed in SkySensor to collect all sensor readings. A pruning method is then proposed to progressively sift out the skyline results from the sensor network. SkySensor avoids the need of collecting data from all sensors in the network, which is an extremely expensive action, when searching for the skyline results. The performance study indicates that SkySensor is highly efficient, and significantly outperforms previous methods in processing skyline queries.     

Reducing query overhead through route learning in unstructured peer-to-peer network

In unstructured peer-to-peer networks, such as Gnutella, peers propagate query messages towards the resource holders by flooding them through the network. This is, however, a costly operation since it consumes node and link resources excessively and often unnecessarily. There is no reason, for example, for a peer to receive a query message if the peer has no matching resource or is not on the path to a peer holding a matching resource. In this paper, we present a solution to this problem, which we call Route Learning, aiming to reduce query traffic in unstructured peer-to-peer networks. In Route Learning, peers try to identify the most likely neighbors through which replies can be obtained to submitted queries. In this way, a query is forwarded only to a subset of the neighbors of a peer, or it is dropped if no neighbor, likely to reply, is found. The scheme also has mechanisms to cope with variations in user submitted queries, like changes in the keywords. The scheme can also evaluate the route for a query for which it is not trained. We show through simulation results that when compared to a pure flooding based querying approach, our scheme reduces bandwidth overhead significantly without sacrificing user satisfaction.     

Opportunistic sampling-based query processing in wireless sensor networks

High resolution sampling of physical phenomenon is a prime application of large scale wireless sensor networks (WSNs). With hundreds of nodes deployed over vast tracts of land, monitoring data can now be generated at unprecedented spatio-temporal scales. However, the limited battery life of individual nodes in the network mandates smart ways of collecting this data by maximizing localized processing of information at the node level. In this paper, we propose a WSN query processing method that enhances localized information processing by harnessing the two inherent aspects of WSN communication, i.e., multihop and multipath data transmission. In an active WSN where data collection queries are regularly processed, multihop and multipath routing leads to a situation where a significant proportion of nodes relay and overhear data generated by other nodes in the network. We propose that nodes opportunistically sample this data as they communicate. We model the data communication process in a WSN and show that opportunistic sampling during data communication leads to surprisingly accurate global knowledge at each node. We present an opportunistic query processing system that uses the accumulated global knowledge to limit the data collection requirements for future queries while ensuring temporal freshness of the results.     

Decision rules for distributed decision networks with uncertainties

The authors study distributed decision networks where uncertainties exist in the statistical environment. Specifically each decision maker (DM) has an unknown probability to be jammed or defective and an unknown probability to provide an incorrect decision when jammed or defective. Each DM in the network has the ability to process its input data consisting of external observations and decisions from preceding DMs, to produce a decision regarding an underlying binary hypothesis testing problem. The local observations are assumed conditionally independent given each hypothesis. The resulting binary hypothesis testing problem is solved using some simple concepts of Dempster-Shafer theory. The performance of the proposed decision rule is compared to that of the minimax decision rule and the decision rule that is optimum when there are no jammed or defective DMs for several distributed decision networks with different topologies. It is shown that the proposed decision rule has a very robust behavior