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]

Still diffraction patterns from peptide nanocrystals with small unit cells are challenging to index using conventional methods owing to the limited number of spots and the lack of crystal orientation information for individual images. New indexing algorithms have been developed as part of the Computational Crystallography Toolbox (cctbx) to overcome these challenges. Accurate unit-cell information derived from an aggregate data set from thousands of diffraction patterns can be used to determine a crystal orientation matrix for individual images with as few as five reflections. These algorithms are potentially applicable not only to amyloid peptides but also to any set of diffraction patterns with sparse properties, such as low-resolution virus structures or high-throughput screening of still images captured by raster-scanning at synchrotron sources. As a proof of concept for this technique, successful integration of X-ray free-electron laser (XFEL) data to 2.5 Å resolution for the amyloid segment GNNQQNY from the Sup35 yeast prion is presented.

With the increasing popularity of indoor positioning system technologies, many applications have become available that allow moving objects to be monitored and queried on the basis of their indoor locations. At the center of these applications is a data structure that is used for indexing the moving objects. For most of the current applications, the indexing is based on certain modifications of methods from the established research area of indexing objects moving in outdoor spaces. But the approach to indexing objects moving in indoor spaces should be more radically different. The nature of indoor spaces, which essentially consist of cells and connections between cells, and the concept of cell-based adjacency, as opposed to metric-based adjacency, require a significantly different focus and approach. In this paper, we present a cell-based index structure, which is called the C-tree ('C' for 'cell'), for efficiently grouping and managing updates of moving objects in indoor spaces. The C-tree can efficiently serve indoor spatial queries, topological queries, adjacency queries and density-based queries. In addition, as shown in the paper, the density of indoor cells can play an important role in the performance of the index data structure. Taking cell density into account, we extend the application of the C-tree to construct what is called a density-based index tree, which substantially improves the performance of the index structure when the indoor space contains high density cells. [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]

Recent advances in non-volatile memory technology have led to the introduction of solid state drives (SSD). NVMe SSDs are the latest development in flash based solid state drives and they were designed as a means of low latency and high bandwidth. Many research studies seek for taking advantage of this new technology to accelerate data management. Multidimensional indexes are fundamental for the efficiency of spatial query processing. In this work, we study the implication of high performance NVMe drives on spatial indexing. More specifically, we present an in-depth performance analysis of the Grid File in flash storage and we introduce LB-Grid, a write efficient variant of Grid File for flash based solid state drives. We present new query algorithms for both LB-Grid and Grid File that exploit the high internal parallelism and I/O bandwidth of NVMe SSDs. Experimental results unveil the efficiency of the proposed algorithms. Utilizing a test set of 500M points, LB-Grid appears to be up to 2.26 times faster than Grid File, up to 5.5 times faster than the R ∗ -tree, and up to 3.3 times faster than the FAST-Rtree in update intensive workloads. On the other hand, the Grid File presents better performance in read intensive workloads; exploiting a batch read operation, it achieves a speedup up to 10.2x in range queries, up to 1.56x in kNN and 4.6x in group point queries. [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]

The design process involves multiple stages to provide the solution for an actual or perceived need. The process needs different information at different stages to generate the desired output, but most of the time, the information is uncertain. Information uncertainty almost always makes design decision critical. The present work aims to reduce this information uncertainty in product design by reusing previous design knowledge. Reusing an existing ontology is an obvious way to minimize information uncertainty, and consequently, it can shorten the manufacturing lead time. However, the existing techniques have a few gaps that are still unaddressed. To fill these gaps, a methodology based on bionic engineering is proposed in this work for the purpose of design reuse in product development. Here, for the representation and manipulation of the knowledge, bionic-based reasoning approach is used for the development of the new product with the help of bionic reverse engineering. The proposed methodology is validated by illustrating an example of shoe design suitable to maneuver ill-conditioned roads. This work would be useful to the design and manufacturing practitioner in product development and decision making. [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]

Pivot-based retrieval algorithms are commonly used to solve similarity queries in a number of application domains, such as multimedia retrieval, biomedical databases, time series and computer vision. The query performances of pivot-based index algorithms can be significantly improved by properly choosing the set of pivots that is able to narrow down the database elements to only those relevant to a query. While many other approaches in the literature rely on empirical studies or intuitive observations and assumptions to achieve effective pivot strategies, this paper addresses the problem by using a formal mathematical approach. We conclude in our study that the optimal set of pivots in vector databases with L p metrics is a set of uniformly distributed points on the surface of an n -sphere defined by these metrics. To make the study mathematically tractable, a uniform distribution of data in the database is assumed, allowing us to outline the problem from a purely geometrical point of view. Then, we present experimental results demonstrating the usefulness of our characterization when applied to real databases in the ( R n , L p ) metric space. Our technique is shown to outperform comparable techniques in the literature. However, we do not propose a new pivot-selection technique but rather experiments that are designed exclusively to show the usefulness of such a characterization. [ABSTRACT FROM AUTHOR]

• A grid-based algorithm for exact DBSCAN is proposed for large databases. • Grid tree is devised to speed up non-empty neighboring grids queries. • Use the spatial relationships among points to omit unnecessary distance calculations. • The efficiency of the proposed algorithm is proved theoretically and experimentally. DBSCAN is a fundamental spatial clustering algorithm with numerous practical applications. However, a bottleneck of DBSCAN is its O (n 2) worst-case time complexity. To address this limitation, we propose a new grid-based algorithm for exact DBSCAN in Euclidean space called GriT-DBSCAN, which is based on the following two techniques. First, we introduce grid tree to organize the non-empty grids for the purpose of efficient non-empty neighboring grids queries. Second, by utilizing the spatial relationships among points, we propose a technique that iteratively prunes unnecessary distance calculations when determining whether the minimum distance between two sets is less than or equal to a certain threshold. We theoretically demonstrate that GriT-DBSCAN has excellent reliability in terms of time complexity. In addition, we obtain two variants of GriT-DBSCAN by incorporating heuristics, or by combining the second technique with an existing algorithm. Experiments are conducted on both synthetic and real-world data sets to evaluate the efficiency of GriT-DBSCAN and its variants. The results show that our algorithms outperform existing algorithms. [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]

Indexing methods are developed to effectively process user queries in many real-time and moving object management applications. The existing spatial data updating indexing methods are based on the Integrated binary Tree, R-Tree, R*-Tree, Oct-Tree, Quad-Tree, Grid-Tree and Hex-Tree. The depth of these trees is unbalanced and overlapping, hence the performance is reduced in the multi-structure indexing methods. D-Tree (Decompose - Tree) based multi-structure spatio-temporal index method is proposed to find the present, past and future data. The new multistructural model called DTNH-Tree used to find the present, past and future data. It consists of D-Tree, TB*-Tree, NTTree and hash table. The D-Tree indexing is used to get the spatial data and manage the moving objects in the road network. A set of TB*-Tree is used to index the history of moving object on road networks. A set of NT -Trees is used to manage the current position of the recently updated data and find present data of the moving objects. NT-Tree indexes the present and future information of the moving objects. Finally the set of hash tables is used for updating the data continuously. The proposed multi-structure indexing method supports different types of query processing compared to the existing indexing methods. Experimental results exhibits better updation and query performance compared to the MSMON-Tree and PPF*-Tree. [ABSTRACT FROM AUTHOR]

Social media provides an environment of information exchange. They principally rely on their users to create content, to annotate others' content and to make on-line relationships. The user activities reflect his opinions, interests, etc. in this environment. We focus on analysing this social environment to detect user interests which are the key elements for improving adaptation. This choice is motivated by the lack of information in the user profile and the inefficiency of the information issued from methods that analyse the classic user behaviour (e.g. navigation, time spent on web page, etc.). So, having to cope with an incomplete user profile, the user social network can be an important data source to detect user interests. The originality of our approach is based on the proposal of a new technique of interests' detection by analysing the accuracy of the tagging behaviour of a user in order to figure out the tags which really reflect the content of the resources. So, these tags are somehow comprehensible and can avoid tags "ambiguity" usually associated to these social annotations. The approach combines the tag, user and resource in a way that guarantees a relevant interests detection. The proposed approach has been tested and evaluated in the Delicious social database. For the evaluation, we compare the result issued from our approach using the tagging behaviour of the neighbours (the egocentric network and the communities) with the information yet known for the user (his profile). A comparative evaluation with the classical tag-based method of interests detection shows that the proposed approach is better. [ABSTRACT FROM AUTHOR]

Current social-network-based and location-based-service applications need to handle continuous spatial approximate keyword queries over geo-textual streaming data of high density. The continuous query is a well-known expensive operation. The optimization of continuous query processing is still an open issue. For geo-textual streaming data, the performance issue is more serious since both location information and textual description need to be matched for each incoming streaming data tuple. The state-of-the-art continuous spatial-keyword query indexing approaches generally lack both support for approximate keyword matching and high-performance processing for geo-textual streaming data. Aiming to tackle this problem, this paper first proposes an indexing approach for efficient supporting of continuous spatial approximate keyword queries by integrating m i n - w i s e signatures into an AP-tree, namely AP-tree + . AP-tree + utilizes the one-permutation m i n - w i s e hashing method to achieve a much lower signature maintenance costs compared with the traditional m i n - w i s e hashing method because it only employs one hashing function instead of dozens. Towards providing a more efficient indexing approach, this paper has explored the feasibility of parallelizing AP-tree + by employing a Graphic Processing Unit (GPU). We mapped the AP-tree + data structure into the GPU’s memory with a variety of one-dimensional arrays to form the GPU-aided AP-tree + . Furthermore, a m i n - w i s e parallel hashing algorithm with a scheme of data parallel and a GPU-CPU data communication method based on a four-stage pipeline way have been used to optimize the performance of the GPU-aided AP-tree + . The experimental results indicate that (1) AP-tree + can reduce the space cost by about 11% compared with MHR-tree, (2) AP-tree + can hold a comparable recall and 5.64× query performance gain compared with MHR-tree while saving 41.66% maintenance cost on average, (3) the GPU-aided AP-tree + can attain an average speedup of 5.76× compared to AP-tree + , and (4) the GPU-CPU data communication scheme can further improve the query performance of the GPU-aided AP-tree + by 39.4%.

Retailer revenue is significantly impacted by item placement. Given the prevalence and popularity of medium-to-large-sized retail stores, several research efforts have been made towards facilitating item/itemset placement for improving retailer revenue. However, they fail to consider the issue of inventory of the items w.r.t. itemset placement. Notably, the inventory of a given item refers to the number of instances of that item that are available to the retailer for sales purposes. Moreover, efficient retrieval and placement of top-revenue itemsets in the retail store slots cannot be performed by existing approaches. Our key contributions are summarized as follows. First, we introduce the notion of inventory in retail itemset placement. Second, we propose an inventory-aware indexing scheme, designated as IRIS, for efficiently retrieving high-revenue itemsets. Moreover, we propose the IRPS inventory-aware itemset placement scheme, which exploits the IRIS indexing scheme, for facilitating improved retailer revenue. Third, we conduct a performance study with two real datasets to demonstrate the effectiveness of our proposed itemset indexing and placement schemes in improving retailer revenue. • We introduced the notion of inventory in retail itemset placement. • Inventory-aware itemset placement can significantly improve retailer revenue. • We have proposed an inventory-aware itemset retrieval and placement framework. • We conducted experiments with real datasets to demonstrate revenue improvement. [ABSTRACT FROM AUTHOR]

Background: Facing a growing workload and dwindling resources, the US National Library of Medicine (NLM) created the Indexing Initiative project in 1996. This cross-library team's mission is to explore indexing methodologies for ensuring quality and currency of NLM document collections. The NLM Medical Text Indexer (MTI) is the main product of this project and has been providing automated indexing recommendations since 2002. After all of this time, the questions arise whether MTI is still useful and relevant. Methods: To answer the question about MTI usefulness, we track a wide variety of statistics related to how frequently MEDLINE indexers refer to MTI recommendations, how well MTI performs against human indexing, and how often MTI is used. To answer the question of MTI relevancy compared to other available tools, we have participated in the 2013 and 2014 BioASQ Challenges. The BioASQ Challenges have provided us with an unbiased comparison between the MTI system and other systems performing the same task. Results: Indexers have continually increased their use of MTI recommendations over the years from 15.75% of the articles they index in 2002 to 62.44% in 2014 showing that the indexers find MTI to be increasingly useful. The MTI performance statistics show significant improvement in Precision (+0.2992) and F1 (+0.1997) with modest gains in Recall (+0.0454) over the years. MTI consistency is comparable to the available indexer consistency studies. MTI performed well in both of the BioASQ Challenges ranking within the top tier teams. Conclusions: Based on our findings, yes, MTI is still relevant and useful, and needs to be improved and expanded. The BioASQ Challenge results have shown that we need to incorporate more machine learning into MTI while still retaining the indexing rules that have earned MTI the indexers' trust over the years. We also need to expand MTI through the use of full text, when and where it is available, to provide coverage of indexing terms that are typically only found in the full text. The role of MTI at NLM is also expanding into new areas, further reinforcing the idea that MTI is increasingly useful and relevant. [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]

Still diffraction patterns from peptide nanocrystals with small unit cells are challenging to index using conventional methods owing to the limited number of spots and the lack of crystal orientation information for individual images. New indexing algorithms have been developed as part of the Computational Crystallography Toolbox ( cctbx) to overcome these challenges. Accurate unit-cell information derived from an aggregate data set from thousands of diffraction patterns can be used to determine a crystal orientation matrix for individual images with as few as five reflections. These algorithms are potentially applicable not only to amyloid peptides but also to any set of diffraction patterns with sparse properties, such as low-resolution virus structures or high-throughput screening of still images captured by raster-scanning at synchrotron sources. As a proof of concept for this technique, successful integration of X-ray free-electron laser (XFEL) data to 2.5 Å resolution for the amyloid segment GNNQQNY from the Sup35 yeast prion is presented. [ABSTRACT FROM AUTHOR]

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]

Abstract: After two decades of research, the techniques for efficient similarity search in metric spaces have combined virtually all the available tricks resulting in many structural index designs. As the representative state-of-the-art metric access methods (also called metric indexes) that vary in the usage of filtering rules and in structural designs, we could mention the M-tree, the M-Index and the List of Clusters, to name a few. In this paper, we present the concept of cut-regions that could heavily improve the performance of metric indexes that were originally designed to employ simple ball-regions. We show that the shape of cut-regions is far more compact than that of ball-regions, yet preserving simple and concise representation. We present three re-designed metric indexes originating from the above-mentioned ones but utilizing cut-regions instead of ball-regions. We show that cut-regions can be fully utilized in the index structure, positively affecting not only query processing but also the index construction. In the experiments we show that the re-designed metric indexes significantly outperform their original versions. [Copyright &y& Elsevier]

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]

Let S be a set of n points in a fixed axis-parallel rectangle $R\subseteq \Re^{2}$, i.e. in the two-dimensional space (2D). Assuming that those points are stored in an R-tree, this paper presents several algorithms for finding the empty rectangle in R with the largest area, sides parallel to the axes of the space, and containing only a query point q. This point can not be part of S, that is, it is not stored in the R-tree. All algorithms follow the basic idea of discarding part of the points of S, in such a way that the problem can be solved only considering the remaining points. As a consequence, the algorithms only have to access a very small portion of the nodes (disk blocks) of the R-tree, saving main memory resources and computation time. We provide formal proofs of the correctness of our algorithms and, in order to evaluate the performance of the algorithms, we run an extensive set of experiments using synthetic and real data. The results have demonstrated the efficiency and scalability of our algorithms for different dataset configurations. [ABSTRACT FROM AUTHOR]

Abstract: With the fast growth of the knowledge bases built over the Internet, storing and querying millions or billions of RDF triples in a knowledge base have attracted increasing research interests. Although the latest RDF storage systems achieve good querying performance, few of them pay much attention to the characteristic of dynamic growth of the knowledge base. Since the building of the knowledge base is usually a continuous process, incremental update over the RDF storage system is in great need. In this paper, to consider the efficiency of both querying and incremental update in RDF data, we propose a hAsh-based tWo-tiEr rdf sTOrage system (abbr. to AWETO) with new index architecture and query execution engine. The performance of our system is systematically measured over two large-scale datasets. Compared with the other three state-of-the-art open source RDF storage systems, our system achieves the best incremental update efficiency meanwhile, the query efficiency is competitive. [Copyright &y& Elsevier]

Abstract: In information retrieval, efficient similarity search in multimedia collections is a critical task. In this paper, we present a rigorous comparison of three different approaches to the image retrieval problem, including cluster-based indexing, distance-based indexing, and multidimensional scaling methods. The time and accuracy trade-offs for each of these methods are demonstrated on three different image data sets. Similarity of images is obtained either by a feature-based similarity measure using four MPEG-7 low-level descriptors or by a whole image-based similarity measure. The effect of these similarity measurement techniques on the retrieval process is also evaluated through the performance tests performed on several data sets. We show that using low-level features of images in the similarity measurement function results in significantly better accuracy and time performance compared to the whole-image based approach. Moreover, an optimization of feature contributions to the distance measure for feature-based approach can identify the most relevant features and is necessary to obtain maximum accuracy. We further show that multidimensional scaling can achieve comparable accuracy, while speeding-up the query times significantly by allowing the use of spatial access methods. [Copyright &y& Elsevier]

Abstract: We present pest, a novel approach to the approximate querying of graph-structured data such as RDF that exploits the data''s structure to propagate term weights between related data items. We focus on data where meaningful answers are given through the application semantics, e.g., pages in wikis, persons in social networks, or papers in a research network such as Mendeley. The pest matrix generalizes the Google Matrix used in PageRank with a term-weight dependent leap and accommodates different levels of (semantic) closeness for different relations in the data, e.g., friend vs. co-worker in a social network. Its eigenvectors represent the distribution of a term after propagation. The eigenvectors for all terms together form a (vector space) index that takes the structure of the data into account and can be used with standard document retrieval techniques. In extensive experiments including a user study on a real life wiki, we show how pest improves the quality of the ranking over a range of existing ranking approaches, yet achieves a query performance comparable to a plain vector space index. [Copyright &y& Elsevier]

Gestures are an important modality for human–machine communication. Computer vision modules performing gesture recognition can be important components of intelligent homes, assistive environments, and human–computer interfaces. A key problem in recognizing gestures is that the appearance of a gesture can vary widely depending on variables such as the person performing the gesture, or the position and orientation of the camera. This paper presents a database-based approach for addressing this problem. The large variability in appearance among different examples of the same gesture is addressed by creating large gesture databases, that store enough exemplars from each gesture to capture the variability within that gesture. This database-based approach is applied to two gesture recognition problems: handshape categorization and motion-based recognition of American Sign Language signs. A key aspect of our approach is the use of database indexing methods, in order to address the challenge of searching large databases without violating the time constraints of an online interactive system, where system response times of over a few seconds are oftentimes considered unacceptable. Our experiments demonstrate the benefits of the proposed database-based framework, and the feasibility of integrating large gesture databases into online interacting systems. [ABSTRACT FROM AUTHOR]

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]

Most current research on Location-Based Services (LBSs, for short) assumes point-to-point wireless communication, where the server processes a query and returns the query result to the user via a point-to-point wireless channel. However, LBSs via point-to-point wireless channel suffer from a tremendous amount of traffic and service requests from the user and thereby result in poor performance. In this paper, we present broadcast-based spatial query processing algorithms designed to support k-NN ( k-Nearest Neighbor) and range queries via a wireless network. The task of the query processor is to selectively monitor the wireless broadcast channel, when the data items are disseminated by the server, according to their locations. Experiments are conducted to evaluate the performance of the proposed algorithms. Comprehensive experiments illustrate that the presented algorithms are highly scalable and are more efficient than the previous techniques in terms of both access time and energy consumption. [ABSTRACT FROM AUTHOR]

Repositories of complex data types, such as images, audio, video and free text, are becoming increasingly frequent in various fields. A general searching approach for such data types is that of similarity search, where the search is for similar objects and similarity is modeled by a metric distance function. An important class of access methods for similarity search in metric data is that of dynamic clustered metric trees, where the index is structured as a paged and balanced tree and the space is partitioned hierarchically into compact regions. While access methods of this class allow dynamic insertions typically of single objects, the problem of efficiently inserting a given data set into the index in bulk is largely open. In this article we address this problem and propose novel algorithms corresponding to its two cases, where the index is initially empty (i.e. bulk loading), and where the index is initially non empty (i.e. bulk insertion). The proposed bulk loading algorithm builds the index bottom-up layer by layer, using a new sampling based clustering method, which improves clustering results by improving the quality of the selected sample sets. The proposed bulk insertion algorithm employs the bulk loading algorithm to load the given data into a new index structure, and then merges the new and the existing structures into a unified high quality index, using a novel decomposition method to reduce overlaps between the structures. Both algorithms yield significantly improved construction and search performance, and are applicable to all dynamic clustered metric trees. Results from an extensive experimental study show that the proposed algorithms outperform alternative methods, reducing construction costs by up to 47% for CPU costs and 99% for I/O costs, and search costs by up to 48% for CPU costs and 30% for I/O costs. [ABSTRACT FROM AUTHOR]

Abstract: Similarity search is a very active area of research because of its usefulness in a set of modern applications, such as content-based image retrieval (CBIR), time series, spatial databases, data mining and multimedia databases in general. The usual way to do a similarity search is to map the objects to feature vectors and to model the search as a nearest neighbor query in the multidimensional space where vectors reside. The main critical issues to this process are: the distance function used to measure the proximity between vectors and the index method to accelerate the search. In this paper we propose a formal framework to perform similarity search that provides the user with a high degree of freedom in the choice of both the distance and the index structure used to organize the feature space. More specifically, we introduce a function to approximate eventually any distance function that can be used in conjunction with index structures that divide the feature space in multidimensional rectangular regions. Cases of use and experimental work are presented to demonstrate the applicability and the overhead of the framework. [Copyright &y& Elsevier]

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]

Abstract: The metric space model abstracts many proximity or similarity problems, where the most frequently considered primitives are range and k-nearest neighbor search, leaving out the similarity join, an extremely important primitive. In fact, despite the great attention that this primitive has received in traditional and even multidimensional databases, little has been done for general metric databases. We solve two variants of the similarity join problem: (1) range joins: Given two sets of objects and a distance threshold r, find all the object pairs (one from each set) at distance at most r; and (2) k-closest pair joins: Find the k closest object pairs (one from each set). For this sake, we devise a new metric index, coined List of Twin Clusters (LTC), which indexes both sets jointly, instead of the natural approach of indexing one or both sets independently. Finally, we show how to use the LTC in order to solve classical range queries. Our results show significant speedups over the basic quadratic-time naive alternative for both join variants, and that the LTC is competitive with the original list of clusters when solving range queries. Furthermore, we show that our technique has a great potential for improvements. [Copyright &y& Elsevier]

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]