3168260
Processing in-route nearest neighbor queries: a comparison of alternative approaches
Nearest neighbor query is one of the most important operations in spatial databases and their application domains, e.g., location-based services, advanced traveler information systems, etc. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Several experiments using real road map datasets are conducted to examine the behavior of the solutions in terms of three parameters affecting the performance. Our experiments show that the computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decreases with increase in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.
5800531
A join-less approach for co-location pattern mining: a summary of results
Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. Co-location pattern discovery presents challenges since the instances of spatial features are embedded in a continuous space and share a variety of spatial relationships. A large fraction of the computation time is devoted to identifying the instances of co-location patterns. We propose a novel join-less approach for co-location pattern mining, which materializes spatial neighbor relationships with no loss of co-location instances and reduces the computational cost of identifying the instances. The join-less co-location mining algorithm is efficient since it uses an instance-lookup scheme instead of an expensive spatial or instance join operation for identifying co-location instances. The experimental evaluations show the join-less algorithm performs more efficiently than a current join-based algorithm and is scalable in dense spatial datasets.
413415
A partial join approach for mining co-location patterns
Spatial co-location patterns represent the subsets of events whose instances are frequently located together in geographic space. We identified the computational bottleneck in the execution time of a current co-location mining algorithm. A large fraction of the join-based co-location miner algorithm is devoted to computing joins to identify instances of candidate co-location patterns. We propose a novel <i>partial-join</i> approach for mining co-location patterns efficiently. It transactionizes continuous spatial data while keeping track of the spatial information not modeled by transactions. It uses a transaction-based <i>Apriori</i> algorithm as a building block and adopts the instance join method for residual instances not identified in transactions. We show that the algorithm is correct and complete in finding all co-location rules which have prevalence and conditional probability above the given thresholds. An experimental evaluation using synthetic datasets and a real dataset shows that our algorithm is computationally more efficient than the join-based algorithm.
39295391
An Efficient Cache Conscious Multi-dimensional Index Structure
Recently, to relieve the performance degradation caused by the bottleneck between CPU and main memory, cache conscious multi-dimensional index structures have been proposed. The ultimate goal of them is to reduce the space for entries so as to widen index trees, and minimize the number of cache misses. They can be classified into two approaches according to their space reduction methods. One approach is to compress minimum bounding regions (MBRs) by quantizing coordinate values to the fixed number of bits. The other approach is to store only the sides of MBRs that are different from their parents. In this paper, we investigate the existing multi-dimensional index structures for main memory database systems through experiments under the various work loads. Then, we propose a new index structure that exploits the properties of the both techniques. We implement existing multi-dimensional index structures and the proposed index structure, and perform various experiments to show that our approach outperforms others.
6485837
On the Hidden Terminal Problem in Multi-rate Ad Hoc Wireless Networks
Multi-hop ad hoc wireless networks generally use the IEEE 802.11 Distributed Coordination Function (DCF) MAC protocol, which utilizes the request-to-send/clear-to-send (RTS/CTS) mechanism to prevent the hidden terminal problem. It has been pointed out that the RTS/CTS mechanism cannot completely solve the hidden terminal problem in ad hoc networks because the interference range could exceed the basic rate transmission range. In this paper we provide a worst-case analysis of collision probability induced by the hidden terminal problem in ad hoc networks with multi-rate functionality. We show that the interference caused by the nodes in the area that is not covered by the RTS/CTS is bounded by C′R−4, where C′ is a constant and R is the distance between the two transmitting nodes. The analytic result showed that the interference could shorten the data transmission range up to 30 percent. We then propose a simple multi-rate MAC protocol that could prevent the hidden terminal problem when transmit power control (TPC) is employed.
1331520
Concept formation in numeric domains
COBWEB is a concept formation system that organizes observations into a classification tree. However, it can only handles symbolic data. COBWEB/3 handles numeric data assuming a normal distribution of attribute values. However, COBWEB/Q requires a userspecified acuity value that has to be carefully tuned to obtain the optimal concept hierarchy. However, single acuity value may not be appropriate to all attributes which may have various ranges of values. In this paper, we show how important the normalization of each attribute is, and present an algorithm that can properly handle symbolic and/or numeric data. Topics : Artificial Intelligence, Machine Learning
15854952
An On-Demand Energy-Efficient Routing Algorithm for Wireless Ad Hoc Networks
Ad hoc networks are non-infrastructure networks which consist of mobile nodes. Since the mobile nodes have limited battery power, it is very important to use energy efficiently in ad hoc networks. In order to maximize the lifetime of ad hoc networks, traffic should be sent via a route that can be avoid nodes with low energy while minimizing the total transmission power. In addition, considering that the nodes of ad hoc networks are mobile, on-demand routing protocols are preferred for ad hoc networks. However, most existing power-aware routing algorithms do not meet these requirements. Although some power-aware routing algorithms try to compromise between two objectives, they have difficulty in implementation into on-demand version. In this paper, we propose a novel on-demand power aware routing algorithm called DEAR. DEAR prolongs its network lifetime by compromising between minimum energy consumption and fair energy consumption without additional control packets. DEAR also improves its data packet delivery ratio.