Search

Numerous research efforts have been proposed for efficient processing of range queries in high-dimensional space by either redesigning R-tree access structure for exploring massive parallelism on single GPU or exploring distributed framework of R-tree. However, none of the existing efforts explores the integration of the parallelization of the R-tree on a single GPU with a distributed framework for the R-tree. The problem of designing an efficient multi-GPU indexing method, which can effectively combine the parallelism maximization with distributed processing of the R-tree, remains an open challenge. In this article, we present a novel multi-GPU efficient parallel and distributed indexing method, called LBPG-tree. The rationale of the LBPG-tree is to combine the advantages of an instruction pipeline in CPU with the massive parallel processing potential of multiple GPUs by introducing two new optimization strategies: First, we exploit the GPU L2 cache for accelerating both index search and index node access on GPUs. Second, we further improve utilization of L2 cache on GPUs by compacting and sorting candidate nodes called Compact-and-Sort. Our experimental results show that the LBPG-tree outperforms G-tree, the previous representative GPU index method and effectively support multiple GPUs for providing efficient high dimensional range query service. [ABSTRACT FROM AUTHOR]

Recently, the compacted de Bruijn graph (cDBG) of complete genome sequences was successfully used in read mapping due to its ability to deal with the repetitions in genomes. However, current approaches are not flexible enough to fit frequently building the graphs with different $k$ k -mer lengths. Instead of building the graph directly, how can we build the compacted de Bruijin graph of longer $k$ k -mer based on the one of short $k$ k -mer? In this article, we present StLiter, a novel algorithm to build the compacted de Bruijn graph either directly from genome sequences or indirectly based on the graph of a short $k$ k -mer. For 100 simulated human genomes, StLiter can construct the graph of $k$ k -mer length 15-18 in 2.5-3.2 hours with maximal ∼70GB memory in the case of without considering the reverese complements of the reference genomes. And it costs 4.5-5.9 hours when considering the reverse complements. In experiments, we compared StLiter with TwoPaCo, the state-of-art method for building the graph, on 4 datasets. For $k$ k -mer length 15-18, StLiter can build the graph 5-9 times faster than TwoPaCo using less maximal memory cost. For $k$ k -mer length larger than 18, given the graph of a short $({\mathrm{k}}$ (k - ${\mathrm{x}})$ x) -mer, such as ${\mathrm{x}}$ x = 1-2, compared with TwoPaCo building the graph directly, StLiter can also build the graph more efficiently. The source codes of StLiter can be downloaded from web site https://github.com/BioLab-cz/StLiter. [ABSTRACT FROM AUTHOR]

Reading comprehension tasks are commonly used for developing students’ reading ability. In order to adaptively recommend reading comprehension materials to students engaged in computerized testing, the information in an item bank (a collection of test items stored in a dataset) must be effectively indexed. Familiarity with the topics present in the documents influences students’ reading performance. As different question types require different skills, we tag documents with topics and questions with their corresponding types to measure the students’ abilities and subsequently recommend relevant materials to them. However, automatic tagging has not been extensively studied in this field. In this article, we propose a document extraction attention network (DEAN) to accomplish the two aforementioned tasks. For topic tagging, DEAN utilizes questions to increase the sample size of documents implicitly through multitask learning. For type tagging, DEAN leverages the information gathered from documents, which aids in the task of prediction. Experiments demonstrate the effectiveness of our mutual use of information obtained from documents and questions. Results indicate that DEAN outperforms commonly used text classification methods when tested on a reading comprehension dataset. [ABSTRACT FROM AUTHOR]

In recent years, computerized adaptive testing (CAT) has gained popularity as an important means to evaluate students’ ability. Assigning tags to test questions is crucial in CAT. Manual tagging is widely used for constructing question banks; however, this approach is time-consuming and might lead to consistency issues. Automatic question tagging, an alternative, has not been studied extensively. In this paper, we propose a position-based attention model and keywords-based model to automatically tag questions with knowledge units. With regard to multiple-choice questions, the proposed models employ mechanisms to capture useful information from keywords to enhance tagging performance. Unlike traditional machine learning-based tagging methods, our models utilize deep neural networks to represent questions using contextual information. The experimental results show that our proposed models outperform some traditional classification and topic methods by a large margin on an English question bank dataset. [ABSTRACT FROM AUTHOR]

Finding related nucleotide or protein sequences is a fundamental, diverse, and incompletely-solved problem in bioinformatics. It is often tackled by seed-and-extend methods, which first find “seed” matches of diverse types, such as spaced seeds, subset seeds, or minimizers. Seeds are usually found using an index of the reference sequence(s), which stores seed positions in a suffix array or related data structure. A child table is a fundamental way to achieve fast lookup in an index, but previous descriptions have been overly complex. This paper aims to provide a more accessible description of child tables, and demonstrate their generality: they apply equally to all the above-mentioned seed types and more. We also show that child tables can be used without LCP (longest common prefix) tables, reducing the memory requirement. [ABSTRACT FROM AUTHOR]

Efficient processing of skyline queries with partially ordered domains has been intensively addressed in recent years. To further reduce the query processing time to support high-responsive applications, the skyline queries that were previously processed with user preferences similar to those of the new query contribute useful candidate result points. Hence, the answered queries can be cached with both their results and the user preferences such that the query processor can rapidly retrieve the result for a new query only from the result sets of cached queries with compatible user preferences. When caching a significant number of queries accumulated over time, it is essential to adopt effective access methods to index the cached queries to retrieve a set of relevant cached queries for facilitating the cache-based skyline query computations. In this paper, we propose an extended depth-first search indexing method (e-DFS for short) for accessing user preference profiles represented by directed acyclic graphs (DAGs), and emphasize the design of the e-DFS encoding that effectively encodes a user preference profile into a low-dimensional feature point which is eventually indexed by an R-tree. We obtain one or more traversal orders for each node in a DAG by traversing it through a modified version of the depth-first search which is utilized to examine the topology structure and dominance relations to measure closeness or similarity. As a result, e-DFS which combines the criteria of similarity evaluation is able to greatly reduce the search space by filtering out most of the irrelevant cached queries such that the query processor can avoid accessing the entire data set to compute the query results. Extensive experiments are presented to demonstrate the performance and utility of our indexing method, which outperforms the baseline planning techniques by reducing 37 percent of the computational time on average. [ABSTRACT FROM AUTHOR]

In the information filtering paradigm, clients subscribe to a server with continuous queries that express their information needs and get notified every time appropriate information is published. To perform this task in an efficient way, servers employ indexing schemes that support fast matches of the incoming information with the query database. Such indexing schemes involve (i) main-memory trie-based data structures that cluster similar queries by capturing common elements between them and (ii) efficient filtering mechanisms that exploit this clustering to achieve high throughput and low filtering times. However, state-of-the-art indexing schemes are sensitive to the query insertion order and cannot adopt to an evolving query workload, degrading the filtering performance over time. In this paper, we present an adaptive trie-based algorithm that outperforms current methods by relying on query statistics to reorganise the query database. Contrary to previous approaches, we show that the nature of the constructed tries, rather than their compactness, is the determining factor for efficient filtering performance. Our algorithm does not depend on the order of insertion of queries in the database, manages to cluster queries even when clustering possibilities are limited, and achieves more than 96 percent filtering time improvement over its state-of-the-art competitors. Finally, we demonstrate that our solution is easily extensible to multi-core machines. [ABSTRACT FROM PUBLISHER]

Existing methods have addressed the issue of handling each individual skyline query performed on data sets with partially ordered domains. However, it is still very challenging to process such queries for on-line applications with low response time. In this paper, we introduce a cache-based framework, called CSS, for further reducing the query processing time to support high-responsive applications. Skyline queries that were previously processed with user preferences similar to those of the current query contribute useful candidate result points. Hence, the answered queries are cached with both their results and user preferences such that the query processor can rapidly retrieve the result for a new query only from the result sets of selected queries with compatible user preferences. We introduce a similarity measure that establishes the level of similarity between the user preferences of a new query and a cached query; hence the system can start with the most similar candidates. Furthermore, if a new query is only partially answerable from the cache, then the query processor utilizes the partial result sets and performs less expensive constraint skyline queries guided by violated preferences. Furthermore, we introduce two access methods for cached queries indexed by their user preferences to only access a set of relevant cached queries for similarity measures. Extensive experiments are presented to demonstrate the performance and utility of our novel approach. [ABSTRACT FROM AUTHOR]

Phase change memory (PCM) has been considered an attractive alternative to flash memory and DRAM. It has promising features, including non-volatile storage, byte addressability, fast read and write operations, and supports random accesses. However, there are challenges in designing algorithms for PCM-based memory systems, such as longer write latency and higher energy consumption compared to DRAM. In this paper, we propose a new predictive B \(^{+}\) -tree index, called the B \(^{p}\) -tree, which is tailored for database systems that make use of PCM. Our B \(^{p}\) -tree reduces data movements caused by tree node splits and merges that arise from insertions and deletions. This is achieved by pre-allocating space on PCM for near future data. To ensure the space are allocated where they are needed, we propose a novel predictive model to ascertain future data distribution based on the current data. In addition, as in [4], when keys are inserted into a leaf node, they are packed but need not be in sorted order. We have implemented the B \(^{p}\) -tree in PostgreSQL and evaluated it in an emulated environment. Our experimental results show that the B \(^{p}\) -tree significantly reduces the number of writes, therefore making it write and energy efficient and suitable for a PCM-like hardware environment. [ABSTRACT FROM PUBLISHER]

Recently, the management of transportation systems has become increasingly important in many real applications such as location-based services, supply chain management, traffic control, and so on. These applications usually involve queries over spatial road networks with dynamically changing and complicated traffic conditions. In this paper, we model such a network by a probabilistic time-dependent graph (PT-Graph), whose edges are associated with uncertain delay functions. We propose a useful query in the PT-Graph, namely a trip planner query (TPQ), which retrieves trip plans that traverse a set of query points in PT-Graph, having the minimum traveling time with high confidence. To tackle the efficiency issue, we present the pruning methods time interval pruning and probabilistic pruning to effectively rule out false alarms of trip plans. Furthermore, we design a pre-computation technique based on the cost model and construct an index structure over the pre-computed data to enable the pruning via the index. We integrate our proposed pruning methods into an efficient query procedure to answer TPQs. Through extensive experiments, we demonstrate the efficiency and effectiveness of our TPQ query answering approach. [ABSTRACT FROM PUBLISHER]

This paper studies bundled range aggregation, which is conceptually equivalent to running a range aggregate query separately on multiple datasets, returning the query result on each dataset. In particular, the queried datasets can be arbitrarily chosen from a large number (hundreds or even thousands) of candidate datasets. The challenge is to minimize the query cost no matter how many and which datasets are selected. We propose a fully-dynamic data structure called aggregate bundled B-tree (aBB-tree) to settle bundled range aggregation. Specifically, the aBB-tree requires linear space, answers any query in \(O(\log _B N)\) I/Os, and can be updated in \(O(\log _B N)\) I/Os (where \(N\) is the total size of all the candidate datasets, and \(B\) the disk page size), under the circumstances where the number of datasets is \(O(B)\) . The practical efficiency of our technique is demonstrated with extensive experiments. [ABSTRACT FROM PUBLISHER]

We study the problem of clustering uncertain objects whose locations are described by probability density functions (pdfs). We show that the UK-means algorithm, which generalizes the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (EDs) between objects and cluster representatives. For arbitrary pdfs, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculations. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organize the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods. [ABSTRACT FROM AUTHOR]

Multidimensional point indexing plays a critical role in a variety of data-centric applications, including image retrieval, sequence matching, and moving object database search. A common choice of indexing method for these applications is often the "ubiquitous" R*-tree. Choosing the right indexing method requires careful consideration of various factors such as query operations and index construction methods. In this work, we present an experimental study comparing the R*-tree and Quadtree using various criteria including the query operations and index construction methods. Although a variety of query operations can be performed using these index structures, previous work has largely focused only on the range search operation. We go beyond this previous work and compare the performance of these index structures using k-nearest neighbor (kNN) and distance join queries. In addition, we also consider the impact of index construction methods in evaluating these index structures. Our study sheds light on how the choice of the underlying index structure affects the performance of different query operations, and shows that the method used for constructing the index and the dynamic nature of the data set has a dramatic impact on the performance of these index structures. [ABSTRACT FROM AUTHOR]

Recent interests on XML, the Semantic Web, and Web ontology, among other topics, have sparked a renewed interest on graph-structured databases. A fundamental query on graphs is the reachability test of nodes. Recently, 2-hop labeling has been proposed to index a large collection of XML and/or graphs for efficient reachability tests. However, there has been few work on updates of 2-hop labeling. This is compounded by the fact that data may often change over time. In response to these, this paper studies incremental maintenance of 2-hop labeling. We identify the main reason for the inefficiency of updates of existing 2-hop labels. We propose three updatable 2-hop labelings, hybrids of 2-hop labeling, and their incremental maintenance algorithms. The proposed 2-hop labeling is derived from graph connectivity, as opposed to SET COVER which is used by most previous works. Our experimental evaluation illustrates the space efficiency and update performance of various kinds of 2-hop labelings. Our results show that our incremental maintenance algorithm can be two orders of magnitude faster than previous methods and the size of our 2-hop labeling can be comparable to existing 2-hop labeling. We conclude that there is a natural way to spare some index size for update performance in 2-hop labeling. [ABSTRACT FROM AUTHOR]

Multidimensional databases are beginning to be used in a wide range of applications. To meet this fast-growing demand, the R-tree family is being applied to support fast access to multidimensional data, for which the R+-tree exhibits outstanding search performance. In order to support efficient concurrent access in multiuser environments, concurrency control mechanisms for multidimensional indexing have been proposed. However, these mechanisms cannot be directly applied to the R+-tree because an object in the R+-tree may be indexed in multiple leaves. This paper proposes a concurrency control protocol for R-tree variants with object clipping, namely, Granular Locking for clIPping indexing (GLIP). GLIP is the first concurrency control approach specifically designed for the R+-tree and its variants, and it supports efficient concurrent operations with serializable isolation, consistency, and deadlock-free. Experimental tests on both real and synthetic data sets validated the effectiveness and efficiency of the proposed concurrent access framework. [ABSTRACT FROM AUTHOR]

The K-Nearest Neighbors (KNN) query has been of significant interest in many studies and has become one of the most important spatial queries in mobile sensor networks. Applications of KNN queries may include vehicle navigation, wildlife social discovery, and squad/platoon searching on the battlefields. Current approaches to KNN search in mobile sensor networks require a certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free itinerary-based approach called Density-aware Itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme takes into account several challenging issues such as the trade-off between degree of parallelism and network interference on query response time, and the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. To optimize the performance of DIKNN, a detailed analytical model is derived that automatically determines the most suitable degree of parallelism under various network conditions. This model is validated by extensive simulations. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as k increases and as the sensor node mobility increases. It outperforms the second runner with up to a 50 percent saving in energy consumption and up to a 40 percent reduction in query response time, while rendering the same level of query result accuracy. [ABSTRACT FROM AUTHOR]

We introduce a new probabilistic proximity search algorithm for range and K-nearest neighbor (K-NN) searching in both coordinate and metric spaces. Although there exist solutions for these problems, they boil down to a linear scan when the space is intrinsically high dimensional, as is the case in many pattern recognition tasks. This, for example, renders the K-NN approach to classification rather slow in large databases. Our novel idea is to predict closeness between elements according to how they order their distances toward a distinguished set of anchor objects. Each element in the space sorts the anchor objects from closest to farthest to it and the similarity between orders turns out to be an excellent predictor of the closeness between the corresponding elements. We present extensive experiments comparing our method against state-of-the-art exact and approximate techniques, both in synthetic and real, metric and nonmetric databases, measuring both CPU time and distance computations. The experiments demonstrate that our technique almost always improves upon the performance of alternative techniques, in some cases by a wide margin. [ABSTRACT FROM AUTHOR]

Similarity search has a growing usefulness in a range of applications like time series, image and multimedia databases, biological data, and so on. These searches are implemented by means of neighbour queries in the multidimensional spaces where the data resides. Faced with a large volume of data, it becomes imperative the use of indexing methods with specific algorithms capable of reducing the queries response time. The balanced indexing structures based on kd-trees generate a partition of multidimensional space in holey regions that complicate the underlying topology, hindering the calculation of distances between points and regions. In this paper, we introduce a nearest neighbour search algorithm that exploits this topology for efficiency. The experimental results that are included in this study support the usefulness of the proposed method. [ABSTRACT FROM PUBLISHER]

Similarity search for 3D structure data sets is fundamental to many database applications such as molecular biology, image registration, and computer-aided design. Identifying the common 3D subtructures between two objects is an important research problem. However, it is well known that computing structural similarity is very expensive due to the high exponential time complexity of structure similarity measures. As the structure databases keep growing rapidly, real-time search from large-structure databases becomes problematic. In this paper, we present a novel statistical model, that is, the multiresolution Localized Co-Occurrence Model (LCM), to approximately measure the similarity between the two point-based 3D structures in linear time complexity for fast retrieval. LCM could capture both distribution characteristics and spatial structure of 3D data by localizing the point co-occurrence relationship within a predefined neighborhood system. As a step further, a novel structure query processing method called the incremental and Bounded search (iBound) is also proposed to speed up the search process. iBound avoids a large amount of expensive computation at higher resolution LCMs. By superposing two LCMs, their largest common substructure can also be found quickly. Finally, our experiment results prove the effectiveness and efficiency of our methods. [ABSTRACT FROM AUTHOR]

We consider the problem of creating sample view of a database table. A sample view is an indexed, materialized view that permits efficient sampling from an arbitrary range query over the view. Such "sample views" are very useful to applications that require random samples from a database: approximate query processing, online aggregation, data mining, and randomized algorithms are a few examples. Our core technical contribution is a new file organization called the ACE Tree that is suitable for organizing and indexing a sample view. One of the most important aspects of the ACE Tree is that it supports online random sampling from the view. That is, at all times, the set of records returned by the ACE Tree constitutes a statistically random sample of the database records satisfying the relational selection predicate over the view. Our paper presents experimental results that demonstrate the utility of the ACE Tree. [ABSTRACT FROM AUTHOR]

This paper describes BoostMap, a method for efficient nearest neighbor retrieval under computationally expensive distance measures. Database and query objects are embedded into a vector space in which distances can be measured efficiently. Each embedding is treated as a classifier that predicts for any three objects X, A, B whether X is closer to A or to B. It is shown that a linear combination of such embedding-based classifiers naturally corresponds to an embedding and a distance measure. Based on this property, the BoostMap method reduces the problem of embedding construction to the classical boosting problem of combining many weak classifiers into an optimized strong classifier. The classification accuracy of the resulting strong classifier is a direct measure of the amount of nearest neighbor structure preserved by the embedding. An important property of BoostMap is that the embedding optimization criterion is equally valid in both metric and nonmetric spaces. Performance is evaluated in databases of hand images, handwritten digits, and time series. In all cases, BoostMap significantly improves retrieval efficiency with small losses in accuracy compared to brute-force search. Moreover, BoostMap significantly outperforms existing nearest neighbor retrieval methods such as Lipschitz embeddings, FastMap, and VP-trees. [ABSTRACT FROM AUTHOR]

We present an automatic focus area estimation method, working with a single image without a priori information about the image, the camera, or the scene. It produces relative focus maps by localized blind deconvolution and a new residual error-based classification. Evaluation and comparison is performed and applicability is shown through image indexing. [ABSTRACT FROM AUTHOR]

Broadcasting in wireless mobile computing environments is an effective technique to disseminate information to a massive number of clients equipped with powerful, battery operated devices. To conserve the usage of energy, which is a scarce resource, the information to be broadcast must be organized so that the client can selectively tune in at the desired portion of the broadcast. In this paper, the efficient, energy conserving transaction processing in mobile broadcast environments is examined with widely accepted approaches to indexed data organizations suited for a single item retrieval. The basic idea is to share the index information on multiple data items based on the predeclaration technique. The analytical and simulation studies have been performed to evaluate the effectiveness of our methodology, showing that predeclaration-based transaction processing with selective tuning ability can provide a significant performance improvement of battery life, while retaining a low access time. Tolerance to access failures during transaction processing is also described. [ABSTRACT FROM AUTHOR]

The proliferation of digital images and the widespread distribution of digital data that has been made possible by the Internet has increased problems associated with copyright infringement on digital images. Watermarking schemes have been proposed to safeguard copyrighted images, but watermarks are vulnerable to image processing and geometric distortions and may not be very effective. Thus, the content-based detection of pirated images has become an important application. In this paper, we discuss two important aspects of such a replica detection system: distance functions for similarity measurement and scalability. We extend our previous work on perceptual distance functions, which proposed the Dynamic Partial Function (DPF), and present enhanced techniques that overcome the limitations of DPF. These techniques include the Thresholding, Sampling, and Weighting schemes. Experimental evaluations show superior performance compared to DPF and other distance functions. We then address the issue of using these perceptual distance functions to efficiently detect replicas in large image data sets. The problem of indexing is made challenging by the high-dimensionality and the nonmetric nature of the distance functions. We propose using Locality Sensitive Hashing (LSH) to index images while using the above perceptual distance functions and demonstrate good performance through empirical studies on a very large database of diverse images. [ABSTRACT FROM AUTHOR]

We propose a new Spectral text retrieval method using the Discrete Cosine Transform (DOT). By taking advantage of the properties of the DOT and by employing the fast query and compression techniques found in vector space methods (VSM), we show that we can process queries as fast as VSM and achieve a much higher precision. [ABSTRACT FROM AUTHOR]

We present a query formulation language (called MashQL) in order to easily query and fuse structured data on the web. The main novelty of MashQL is that it allows people with limited IT skills to explore and query one (or multiple) data sources without prior knowledge about the schema, structure, vocabulary, or any technical details of these sources. More importantly, to be robust and cover most cases in practice, we do not assume that a data source should have—an offline or inline—schema. This poses several language-design and performance complexities that we fundamentally tackle. To illustrate the query formulation power of MashQL, and without loss of generality, we chose the Data web scenario. We also chose querying RDF, as it is the most primitive data model; hence, MashQL can be similarly used for querying relational databases and XML. We present two implementations of MashQL, an online mashup editor, and a Firefox add on. The former illustrates how MashQL can be used to query and mash up the Data web as simple as filtering and piping web feeds; and the Firefox add on illustrates using the browser as a web composer rather than only a navigator. To end, we evaluate MashQL on querying two data sets, DBLP and DBPedia, and show that our indexing techniques allow instant user interaction. [ABSTRACT FROM PUBLISHER]

This paper presents a solution to extend the IEEE LOM standard with ontology-based semantic annotations for efficient use of learning objects outside Learning Management Systems. The data model corresponding to this approach is first presented. The proposed indexing technique for this model development in order to acquire a better annotation of learning resources is further presented. This technique extends and combines two consecrated alternative methods for structure-based indexing of textual resources: the mathematical approach of the latent semantic indexing and the linguistic-oriented WordNet-based text processing. Thus, the reason behind the good results provided by the first method becomes more transparent due to the linguistic controlled choices proposed by the second method. The paper results are important in the context of adopting semantic web technologies in the e-learning field, but also as a progress in the area of ontology-based indexing of textual resources. [ABSTRACT FROM PUBLISHER]

We consider approaches for similarity search in correlated, high-dimensional data sets, which are derived within a clustering framework. We note that indexing by “vector approximation” (VA-File), which was proposed as a technique to combat the “Curse of Dimensionality,” employs scalar quantization, and hence necessarily ignores dependencies across dimensions, which represents a source of suboptimality. Clustering, on the other hand, exploits interdimensional correlations and is thus a more compact representation of the data set. However, existing methods to prune irrelevant clusters are based on bounding hyperspheres and/or bounding rectangles, whose lack of tightness compromises their efficiency in exact nearest neighbor search. We propose a new cluster-adaptive distance bound based on separating hyperplane boundaries of Voronoi clusters to complement our cluster based index. This bound enables efficient spatial filtering, with a relatively small preprocessing storage overhead and is applicable to euclidean and Mahalanobis similarity measures. Experiments in exact nearest-neighbor set retrieval, conducted on real data sets, show that our indexing method is scalable with data set size and data dimensionality and outperforms several recently proposed indexes. Relative to the VA-File, over a wide range of quantization resolutions, it is able to reduce random IO accesses, given (roughly) the same amount of sequential IO operations, by factors reaching 100X and more. [ABSTRACT FROM PUBLISHER]