Search

With the emergence of applications that require content based similarity retrieval, techniques to support such a retrieval paradigm over database systems have emerged as a critical area of research. User subjectivity is an important aspect of such queries, i.e., which objects are relevant to the user and which are not depends on the perception of the user. Query refinement is used to handle user subjectivity in similarity search systems. This paper explores how to enhance database systems with query refinement for content-based (similarity) searches in object-relational databases. Query refinement is achieved through relevance feedback where the user judges individual result tuples and the system adapts and restructures the query to better reflect the users information need. We present a query refinement framework and an array of strategies for refinement that address different aspects of the problem. Our experiments demonstrate the effectiveness of the query refinement techniques proposed in this paper., Sponsored in part by National Science Foundation Grant no. IIS-9734300. Presented at the Conference on Extending Database Technology (8th) held in Prague, Czech Republic, on 24-28 Mar 2002 and published in proceedings, p15-33, 2002. Cataloger's note: Slightly longer version available online at the Univ. of California at Irvine Information and Computer Science Database Research Group website.

Many emerging application domains require database systems to support efficient access over highly multidimensional datasets. The current state-of-the-art technique to indexing high dimensional data is to first reduce the dimensionality of the data using Principal Component Analysis and then indexing the reduced dimensionality space using a multidimensional index structure. The above technique, referred to as global dimensionality reduction (GDR), works well when the data set is globally correlated, i.e. most of the variation in the data can be captured by a few dimensions. In practice, datasets are often not globally correlated. In such cases, reducing the data dimensionality using GDR causes significant loss of distance information resulting in a large number of false positives and hence a high query cost. Even when a global correlation does not exist, there may exist subsets of data that are locally correlated. In this paper, we propose a technique called Local Dimensionality Reduction (LDR) that tries to find local correlations in the data and performs dimensionality reduction on the locally correlated clusters of data individually. We develop an index structure that exploits the correlated clusters to efficiently support point, range and k-nearest neighbor queries over high dimensional datasets. Our experiments on synthetic as well as real-life datasets show that our technique (1) reduces the dimensionality of the data with significantly lower loss in distance information compared to GDR and (2) significantly outperforms the GDR, original space indexing and linear scan techniques in terms of the query cost for both synthetic and real-life datasets., Sponsored in part by National Science Foundation Grant no. IIS-9734300. VLDB Submission Number 138. Presented at the International Conference on Very large Data Bases (26th) held in Cario, Egypt on 10-14 Sep 2000 and final version published in proceedings of the same, ISBN 1-55860-715-3, p89-100, 2000.

This paper presents a novel approach to representing 2-dimensional shapes that adaptively models different portions of the shape at different resolutions, having higher resolution where it improves the quality of the representation and lower resolution elsewhere. The proposed representation is invariant to scale, translation, and rotation. The representation is amenable to indexing using existing multidimensional index structures and can thus support efficient similarity retrieval. The experiments reported here show that the adaptive resolution technique performs significantly better compared to the fixed resolution approach previously proposed in the literature., Prepared in cooperation with the Department of Information and Computer Science, University of California at Irvine, Irvine, CA. Sponsored in part by the National Science Foundation under Grant No. IIS-9734300 and the NSF/DARPA/NASA Digital Library Initiative Program under Cooperative Agreement No. 94-11318.

Feature based similarity search is emerging as an important search paradigm in database systems. The technique used is to map the data items as points into a high dimensional feature space which is indexed using a multidimensional data structure. Similarity search then corresponds to a range search over the data structure. Although several data structures have been proposed for feature indexing, none of them is known to scale beyond 10-15 dimensional spaces. This paper introduces the hybrid tree a multidimensional data structure for indexing high dimensional feature spaces. Unlike other multidimensional data structures, the hybrid tree cannot be classified as either a pure data partitioning (DP) index structure (e.g., R-tree, SS-tree, SRtree) or a pure space partitioning (SP) one (e.g., KDB-tree, hBtree); rather, it combines positive aspects of the two types of index structures a single data structure to achieve search performance more scalable to high dimensionalities than either of the above techniques (hence, the name hybrid ). Furthermore, unlike many data structures (e.g., distance based index structures like SS-tree, SR-tree), the hybrid tree can support queries based on arbitrary distance functions. Our experiments on real high dimensional large size feature databases demonstrate that the hybrid tree scales well to high dimensionality and large database sizes. It significantly outperforms both purely DP-based and SP-based index mechanisms as well as linear scan at all dimensionalities for large sized databases., Sponsored in part the National Science Foundation Grant No. IIS-9734300. A version of this paper was presented at the Interantional Conference on Data Engineering (15th) held in Sydney, Australia on 23-26 Mar 1999 and published in proceedings of the same, p440-447, 1999.

The importance of multidimensional index structures to numerous emerging database applications is well established. However, before these index structures can be supported as access methods (AMs) in a commercial-strength database management system (DBMS), efficient techniques to provide transactional access to data via the index structure must be developed. Concurrent accesses to data via index structures introduce the problem of protecting ranges specified in the retrieval from phantom insertions and deletions (the phantom problem). This paper presents a dynamic granular locking approach to phantom protection in Generalized Search Trees (GiSTs), an index structure supporting an extensible set of queries and data types. The granular locking technique offers a high degree of concurrency and has a low lock overhead. Our experiments show that the granular locking technique (1) scales well under various system loads and (2) similar to the B-tree case, provides a significantly more efficient implementation compared to predicate locking for multidimensional AMs as well. Since a wide variety of multidimensional index structures can be implemented using GiST, the developed algorithms provide a general solution to concurrency control in multidimensional AMs. To the best of our knowledge, this paper provides the first such solution based on granular locking.