535125
The D-tree: an index structure for planar point queries in location-based wireless services
Location-based services (LBSs), considered as a killer application in the wireless data market, provide information based on locations specified in the queries. In this paper, we examine the indexing issue for querying location-dependent data in wireless LBSs; in particular, we focus on an important class of queries, planar point queries. To address the issues of responsiveness, energy consumption, and bandwidth contention in wireless communications, an index has to minimize the search time and maintain a small storage overhead. It is shown that the traditional point-location algorithms and spatial index structures fail to achieve either objective or both. This paper proposes a new index structure, called D-tree, which indexes spatial regions based on the divisions that form the boundaries of the regions. We describe how to construct a binary D-tree index, how to process queries based on the D-tree, and how to page the binary D-tree. Moreover, two parameterized methods for partitioning the original space, called fixed grid assignment (FGA) and adaptive grid assignment (AGA), are proposed to enhance the D-tree. The performance of the D-tree is evaluated using both synthetic and real data sets. Experimental results show that the proposed D-tree outperforms the well-known indexes such as the R/sup */-tree, and that both the FGA and AGA approaches can achieve different performance trade-offs between the index search time and storage overhead by fine-tuning their algorithmic parameters.
728279
Performance evaluation of an optimal cache replacement policy for wireless data dissemination
Data caching at mobile clients is an important technique for improving the performance of wireless data dissemination systems. However, variable data sizes, data updates, limited client resources, and frequent client disconnections make cache management a challenge. We propose a gain-based cache replacement policy, Min-SAUD, for wireless data dissemination when cache consistency must be enforced before a cached item is used. Min-SAUD considers several factors that affect cache performance, namely, access probability, update frequency, data size, retrieval delay, and cache validation cost. The paper employs stretch as the major performance metric since it accounts for the data service time and, thus, is fair when items have different sizes. We prove that Min-SAUD achieves optimal stretch under some standard assumptions. Moreover, a series of simulation experiments have been conducted to thoroughly evaluate the performance of Min-SAUD under various system configurations. The simulation results show that, in most cases, the Min-SAUD replacement policy substantially outperforms two existing policies, namely, LRU and SAIU.
11936603
Energy efficient index for querying location-dependent data in mobile broadcast environments
We are witnessing in recent years growing interest for location-dependent information services among mobile users. We examine the issue of processing location-dependent queries in a mobile broadcast environment. Different from a traditional environment, mobile users are concerned with not only access latencies but also power conservation. The planar point location algorithms and conventional spatial index structures are shown inefficient. We propose a new index data structure, called D-tree, for querying location-dependent data in mobile broadcast environments. The basic idea is to index data regions based on the divisions between them. We describe how to construct the binary D-tree index, how to process location-dependent queries based on this index structure, and how to page the D-tree to fit the packet capacity. The performance of the D-tree is evaluated using both synthetic and real datasets. Experimental results show that the proposed D-tree provides a much better overall performance than the well-known existing schemes such as the R*-tree.
3800033
Exponential index: a parameterized distributed indexing scheme for data on air
Wireless data broadcast has received a lot of attention from industries and academia in recent years. Access efficiency and energy conservation are two critical performance concerns in a wireless data broadcast environment. To improve the efficiency of energy consumption on mobile devices, traditional disk-based indexing techniques such as B$^+$-tree have been extended to index broadcast data on a wireless channel. However, existing designs are mostly based on centralized tree structures. Most of these indexing techniques are not flexible in the sense that the trade-off between access efficiency and energy conservation is not adjustable based on application specific requirements. We propose in this paper a novel parameterized index, called the exponential index, which can be tuned to optimize the access latency with the tuning time bounded by a given limit, and vice versa. The proposed index is very efficient because it facilitates replication naturally by sharing links in multiple search trees and thus minimizes storage overhead. Experimental results show that the exponential index not only achieves better performance than the state-of-the-art indexes but also enables great flexibility in trade-offs between access latency and tuning time.
15546337
On processing nested queries in distributed object-oriented database systems
In this paper, we discuss nested query processing in a distributed object-oriented database system. We present three query processing strategies to exploit parallelism in a distributed environment. Then, we review three access methods designed for centralized systems and discuss how they can be applied to the distributed environment. Heuristics for selecting attributes for indexing and determining where to store the indexes are also presented. Finally, a replication strategy is proposed for the path dictionary method.<<ETX>>
14482048
Face recognition using computer-generated database
Many face database and recognition systems have been constructed in specially designed studios with various illuminations, poses, and expressions. However, none of these databases yet satisfies a large variation of poses and illuminations that permit the study of systematic 3D human face information, which results in an unsatisfactory success rate. It is caused primarily by the difficulty of data collection of facial images to satisfy the large variation of poses and illuminations to fully represent the 3D characteristics of human faces. We present how computer-generated database can be used for face recognition experiment focused on multiview face recognition/descriptor. We show multiview face data collection using rendering of 3D models. We also illustrate our approach how to build a face descriptor containing 3D information of human face using multiview concepts. This multiview face recognition descriptor is a 3D descriptor using the concept how much powerful a view influences over nearby views, so called as "quasiview " size
2157536
A framework for constructing features and models for intrusion detection systems
Intrusion detection (ID) is an important component of infrastructure protection mechanisms. Intrusion detection systems (IDSs) need to be accurate, adaptive, and extensible. Given these requirements and the complexities of today's network environments, we need a more systematic and automated IDS development process rather that the pure knowledge encoding and engineering approaches. This article describes a novel framework, MADAM ID, for Mining Audit Data for Automated Models for Instrusion Detection. This framework uses data mining algorithms to compute activity patterns from system audit data and extracts predictive features from the patterns. It then applies machine learning algorithms to the audit records taht are processed according to the feature definitions to generate intrusion detection rules. Results from the 1998 DARPA Intrusion Detection Evaluation showed that our ID model was one of the best performing of all the participating systems. We also briefly discuss our experience in converting the detection models produced by off-line data mining programs to real-time modules of existing IDSs.
7272352
Nearest Surrounder Queries
In this paper, we present a new type of spatial queries called Nearest Surrounder (NS) queries. An NS query determines the nearest polygon-shaped spatial objects (referred to as nearest surrounder objects) and their orientations with respect to a query point from an object set. Besides, we derive two NS query variants, namely, multitier NS (m-NS) queries and angle-constrained NS (ANS) queries. An m-NS query searches multiple layers of NS objects for the same range of angles from a query point. An ANS query searches for NS objects within a specified range of angles. To evaluate NS queries and their variants, we explore angle-based and distance-based bound properties of polygons, and devise two efficient algorithms, namely, Sweep and Ripple, based on R-tree. The algorithms access objects in an order according to their orientations and distances with respect to a given query point, respectively. They are efficient as they can finish a search with one index lookup. Besides, they can progressively deliver a query result. Through empirical studies, we evaluate the proposed algorithms and report their performance for both synthetic and real object sets.
9802917
An End-to-end Workflow Pipeline for Large-scale Grid Computing
In this paper we describe a service-based, software architecture that enables end-to-end, high-level workflow processing in a Grid environment consisting of many heterogeneous resources. Our architecture is essentially a pipeline that extends from the abstract application specification phase to the deployment and execution stages through to returning the results to the user. We envision a large-scale Grid environment that contains heterogeneous resources. Our architecture caters for flexible deployment, performance, reliability and charging for resource usage. These are addressed at the specification level as well as at the realisation (brokering) and execution levels. The proposed architecture is derived from previous work in LeSC that has produced the ICENI pipeline, and our experience with e-Science projects, such as GENIE, e-Protein and RealityGrid from which we derive a set of key requirements.
36896311
Genetic Algorithmic Topology Control for Two-Tiered Wireless Sensor Networks
This paper proposes an optimized topology control scheme (GA-OTC) based on a genetic algorithm for clustering-based hierarchical wireless sensor networks (WSNs). By using a genetic algorithm, we can obtain optimal solutions to multiple objective functions according to the two criteria of both balanced energy consumption and minimized total energy consumption of cluster heads while the entire WSNs field is covered by clusters. Through performance evaluation studies, we show that GA-OTCachieves desirable properties.