Reducing amount of data transmitted enables conserving scarce battery power in wireless sensor networks. In our previous work, we propose two data approximation algorithms for data reduction in sensor networks, maintaining the accuracy of query results within certain bounds. In this paper, we provide a performance study and analysis of these algorithms with emphasis on the types of data for which the algorithms are appropriate. We experimented with different data sets to determine the reduction ratios achieved , energy consumed, errors introduced, complexity of query answering obtained. We provide comparison of our algorithms with related methods. The presented results indicate the superiority of our methods in terms of data reduction and accuracy of query results.

We are addressing the problem of query processing in large sensor networks. Each sensor produces a large amount of streaming data and it may not be possible to store all the data. By caching some of the data in aggregated format, we will be able to answer queries referring to past data. We are investigating a hierarchical caching model where summarized data is cached. The granularity of aggregation becomes coarser as we move up the levels, starting from the actual data of the immediate past stored at the lowest level. We categorize queries into two types: queries that can be answered exactly and those that can be answered approximately. We have provided an analysis of the conditions under which the exact and approximate answers can be provided for a given query. When the query answer is approximate, an estimation of the error is provided.

Content based retrieval systems have been developed for querying image data in which the users can pose queries based on visual properties such as color and texture. These systems, which have advanced the state of the art in image database systems, remarkably lack formal query languages. The traditional query languages are unable to capture the inherent fuzzy nature of the image data and content based querying. The fuzzy object query language (FOQL) presented in this paper addresses the need to support fuzzy values and fuzzy collections required for image databases. It can be used for defining schemas and high level concepts, and for querying image databases. It captures the inherent fuzzy nature of content based retrieval by keeping the query results fuzzy as against other query languages. The users can interactively refine their queries and high level concept definitions using recursive and named query definition constructs in FOQL. Being an extension of ODMG-OQL, FOQL can be easily mapped to ODMG-compliant visual query languages.

Multimedia database systems are essential for the effective and efficient use of large collections of image data. The aim of such systems is to enable retrieval of images based on their contents. As part of our research in this area, we are building a prototype content-based image retrieval system called CHITRA. This uses a four-level data model, and we have defined a fuzzy object query language (FOQL) for this system. This system enables retrieval based on high-level concepts, such as "retrieve images of mountains and sunset". A problem faced in this system is the processing of complex queries such as "retrieve all images that have a similar color histogram and a similar texture to the given example image". Such problems have attracted research attention in recent times. R. Fagin (1996) has given an algorithm for processing such queries and provided a probabilistic upper bound for the complexity of the algorithm (which has been implemented in IBM's Garlic project). In this paper, we provide a theoretical (probabilistic) analysis of the expected cost of this algorithm. We propose a new multi-step query processing algorithm and prove that it performs better than Fagin's algorithm in all cases. Our algorithm requires fewer database accesses. We have evaluated both algorithms against an image database of 1000 images on our CHITRA system. We have used both color histogram and Gabor texture features. Our analysis is presented and the reported experimental results validate our algorithm (which has a significant performance improvement).

No abstract available.

Hashing is critical for high performance computer architecture. Hashing is used extensively in hardware applications, such as page tables, for address translation. Bit extraction and exclusive ORing hashing "methods" are two commonly used hashing functions for hardware applications. There is no study of the performance of these functions and no mention anywhere of the practical performance of the hashing functions in comparison with the theoretical performance prediction of hashing schemes. In this paper, we show that, by choosing hashing functions at random from a particular class, called H/sub 3/, of hashing functions, the analytical performance of hashing can be achieved in practice on real-life data. Our results about the expected worst case performance of hashing are of special significance, as they provide evidence for earlier theoretical predictions.

The bounded disorder file organization proposed by W. Litwin and D.B. Lomet (1987) uses a combination of hashing and tree indexing. Lomet provided an approximate analysis with the mention of the difficulty involved in exact modeling of data nodes, which motivated this work. In an earlier paper (M.V. Ramakrishna and P. Mukhopadhyay, 1988) we provided an exact model and analysis of the data nodes, which is based on the solution of a classical sequential occupancy problem. After summarizing the analysis of data nodes, an alternate file growth method based on repeated trials using universal hashing is proposed and analyzed. We conclude that the alternate file growth method provides simplicity and significant improvement in storage utilization.>

G.H. Gonnet and P.A. Larson (1982) proposed a hashing scheme for external files which guarantees single access retrieval. They provided an asymptotic analysis of the scheme assuming uniform distribution of the signatures. This paper addresses an open problem posed by them in a second work (J. ACM, vol.35, no.1, p.161-84, 1988) about the performance of signatures having a skew distribution. An optimization problem is formulated to obtain the optimal signature distribution which maximizes the resulting load factor. Numerical results indicate that the optimal signature distribution results in significant reduction in the cost of insertions, which is of practical significance.>

Perfect hashing functions are determined that are suitable for hardware implementations. A trial-and-error method of finding perfect hashing functions is proposed using a simple universal/sub 2/ class (H/sub 3/) of hashing functions. The results show that the relative frequency of perfect hashing functions within the class H/sub 3/ is the same as predicted by the analysis for the set of all functions. Extensions of the basic scheme can handle dynamic key sets and large key sets. Perfect hashing functions can be found using software, and then loaded into the hardware hash address generator. Inexpensive associative memory can be used as a general memory construct offered by the system services of high-performance (super) computers. It has a potential application for storing operating system tables or internal tables for software development tools, such as compilers, assemblers and linkers. Perfect hashing in hardware may find a number of other applications, such as high speed event counting and text searching.>

A dynamic hashing scheme that guarantees single access retrieval from the disk is proposed. This is based on the external hashing scheme proposed by G.H. Gonnet and P.A. Larson (see JACM, vol.35, no.1, p.161-84, 1988). The performance of the scheme is achieved at the cost of a small amount of internal memory which remains proportional to the file size. The necessary algorithms for address computation, insertions and file expansions are presented. Since theoretical analysis appears too difficult, the performance is studied using simulations with real-life files.>

Perfect hashing refers to hashing with no overflows. We propose and analyze a composite perfect hashing scheme for large external files. The scheme guarantees retrieval of any record in a single disk access. Insertions and deletions are simple, and the file size may vary considerably without adversely affecting the performance. A simple variant of the scheme supports efficient range searches in addition to being a completely dynamic file organization scheme. These advantages are achieved at the cost of a small amount of additional internal storage and increased cost of insertions.

The author presents an exact probability model for finite hash tables and applies the model to solve a few problems in the analysis of hashing techniques. The model enables exact computation of table sufficiency index, a parameter useful in the design of small hash tables. The author also presents an exact analysis of the expected length of the longest probe sequence in hashing with separate chaining, and successful search length in infinite uniform hashing giving explicit expressions. It appears that the model can be extended to analyze other hashing schemes such as bounded disorder index method, and to problems in robust data structures, etc.>

Recently Litwin and Lomet proposed the Bounded Disorder (BD) file organization which uses a combination of hashing and tree indexing Lomet provided an approximate analysis with a mention of the difficulty involved in exact modeling and analysis. The performance analysis of the method involves solving a classical sequential occupancy problem. We encountered this problem in our attempt to obtain a general model for single access and almost single access retrieval methods developed in the recent years. In this paper, we develop a probability model and present some preliminary results of the exact analysis.

Much of the literature on hashing deals with overflow handling (collision resolution) techniques and its analysis. What does all the analytical results mean in practice and how can they be achieved with practical files? This paper considers the problem of achieving analytical performance of hashing techniques in practice with reference to successful search lengths, unsuccessful search lengths and the expected worst case performance (expected length of the longest probe sequence). There has been no previous attempt to explicitly link the analytical results to performance of real life files. Also, the previously reported experimental results deal mostly with successful search lengths. We show why the well known division method performs “well” under a specific model of selecting the test file. We formulate and justify an hypothesis that by choosing functions from a particular class of hashing functions, the analytical performance can be obtained in practice on real life files. Experimental results presented strongly support our hypothesis. Several interesting problems arising are mentioned in conclusion.

A hashing functton 1s perfect if tt does not create any overflow records The use of perfect hashing functions has previously been studied only for small static sets stored m mam memory In this paper we describe a perfect hashing scheme for large external files which we are currently mvestigatmg The scheme guarantees retrieval of any record m a single disk access This 1s achieved at the cost of a small m-core table and increased cost of insertions We also suggest a pohcy for limrtmg the cost of msertrons and we study the tradeoff between expected storage utthzatron, size of the internal table and cost of msertrons under this pohcy The results obtained so far are very promrsmg They indicate that it may indeed by posstble to destgn practical perfect hashing schemes for external files based on the suggested approach Electronic mad uucp {decvax,allegra,lhnp4] ~watmath~watdalsy~(palarson,mvramalmshn) csnet {palarson,mvramakruhn)% watdauy@ Waterloo csnet Permtsston to copy wtthout fee all or part of this matenal IS granted prowled that the coplea are not made or dlstrlbuted for dwect commercial advantage, the ACM copyright nouce and the tnle of the pubhcatlon and its date appear, and nottcc IS gwen that copymg IS by permlsslon of the Assoclatlon for Computing Machmery To copy otherwse, or to repubhsh, reqmres a fee and/or specific permIssIon