Search

The increase in the amounts of information used to analyze data is problematic since the memory necessary to store and process it is getting quite big. The interval inverted index representation was developed to reduce the required memory to store data, and Frag-Cubing is one of the most popular algorithms. In this paper, we propose two new data cubing algorithms: 3iCubing and M3iCubing. 3iCubing is a Frag-Cubing-based algorithm that uses the interval inverted index representation, while M3iCubing uses both a normal and interval inverted index data representation. The algorithms were compared using synthetic and real data sets in indexation and querying operations, both runtime and memory-wise. The experimental evaluation shows that 3iCubing can considerably reduce the memory needed to index a data set, reducing around 25% of the memory used by Frag-Cubing. Moreover, the results show that the interval inverted index representation is dependent on the data skewness to reduce the memory consumption, having positive results with highly skewed and real-world data sets.

Document Similarity Detection (DSD) is significant in our real life applications. However, the existing methods ignore the privacy of what is contained in the documents uploaded on remote servers, thus reducing the applicability of these methods. The proposed scheme allows documents to be compared without revealing to those remote servers. For each document, the fingerprint set is calculated. The inverted index is constructed on the basis of the whole fingerprint set. The inverted index is widely used for efficient retrieval. This index is under protection by Paillier cryptosystem before it gets uploaded to the server.

In the big data era, massive amount of multimedia data with geo-tags has been generated and collected by smart devices equipped with mobile communications module and position sensor module. This trend has put forward higher request on large-scale geo-multimedia retrieval. Spatial similarity join is one of the significant problems in the area of spatial database. Previous works focused on spatial textual document search problem, rather than geo-multimedia retrieval. In this paper, we investigate a novel geo-multimedia retrieval paradigm named spatial visual similarity join (SVS-JOIN for short), which aims to search similar geo-image pairs in both aspects of geo-location and visual content. Firstly, the definition of SVS-JOIN is proposed and then we present the geographical similarity and visual similarity measurement. Inspired by the approach for textual similarity join, we develop an algorithm named SVS-JOIN $_{B}$ by combining the PPJOIN algorithm and visual similarity. Besides, an extension of it named SVS-JOIN $_{G}$ is developed, which utilizes spatial grid strategy to improve the search efficiency. To further speed up the search, a novel approach called SVS-JOIN $_{Q}$ is carefully designed, in which a quadtree and a global inverted index are employed. Comprehensive experiments are conducted on two geo-image datasets and the results demonstrate that our solution can address the SVS-JOIN problem effectively and efficiently.

The size of a streaming graph is possibly unbounded, and it is updated by a continuous sequence of edges over time. Due to numerous types of real-world interactions, the nature of edge arrival in a streaming graph is dynamic and holds different types of temporal subgraphs, such as stars, bipartite forms, cliques, and chains. The most current techniques find such subgraphs in each snapshot of a dynamic graph and use a dictionary or hash-based summary to compress the graph before applying a stitching technique to demonstrate its temporal behavior. However, it remains difficult to discover those subgraph structures from the continuous stream of edges found in large and rapidly changing dynamic graphs. In this paper, we propose a streaming graph compression algorithm, StarZIP, that uses a new encoding scheme. Our motivational factor is real-world graphs that contain an overwhelmingly large number of stars and a few other structures. We have observed that all subgraph structures can be represented as star-shaped subgraphs. Moreover, the star-shaped representation can easily be arranged in the form of an inverted index, which enables the application of different inverted list encoding techniques for compression. Therefore, we shatter a graph into a uniform representation of stars to compress it. The evaluation of StarZIP on real-world datasets shows that our proposed system reduced the size of a highly dense graph to 60 times less than its original size. Moreover, the experimental results indicate that StarZIP compression is 4 times better than the state-of-the-art techniques.

Search is one of the most popular and important web services. The inverted index is the standard data structure adopted by most full-text search engines. Recently, custom hardware accelerators for inverted index search have emerged to demonstrate much higher throughput than the conventional CPU or GPU. However, less attention has been paid to addressing the memory capacity pressure with inverted index. The conventional DDRx DRAM memory system significantly increases the system cost to make a terabyte-scale main memory. Instead, a shared memory pool composed of storage-class memory (SCM) devices is a promising alternative for scaling memory capacity at a much lower cost. However, this SCM-based pooled memory poses new challenges caused by the limited bandwidth of both SCM devices and the shared interconnect to the host CPU. Thus, we propose BOSS, the first near-data processing (NDP) architecture for inverted index search on SCM-based pooled memory, which maintains high throughput of query processing in this bandwidth- constrained environment. BOSS mitigates the impact of low bandwidth of SCM devices by employing early-termination search algorithms, reducing the footprint of intermediate data, and introducing a programmable decompression module that can select the best compression scheme for a given inverted index. Furthermore, BOSS includes a top-k selection module in hardware to substantially reduce the host-accelerator bandwidth consumption. Compared to Apache Lucene, a production-grade search engine library, running on 8 CPU cores, BOSS achieves a geomean speedup of 8.1× on various complex query types, while reducing the average energy consumption by 189×.

Graph similarity search is an important research problem in many applications, such as finding result graphs that have a similar structure to a given entity in biochemistry, data mining, and pattern recognition. Top-k graph similarity search is one of graph similarity search tasks, which aims to find the top-k graphs that are most similar to the query graph in a given graph database. In this paper, the top-k similarity search problem based on the graph edit distance is studied according to the corollary of the partitioned similarity theorem. Firstly, in order to speed up the online search process and avoid scanning each graph in the database one by one, an offline hierarchical inverted index is constructed to satisfy top-k search. Secondly, the offline hierarchical inverted index is used to filter the candidate graphs online and verify them, which reduces the time of searching the graphs. Finally, the good performance of the algorithm in running time and scalability is verified by running the similarity algorithm on real dataset and synthetic dataset.

Because the information in the field of engineering construction involves remote sensing recognition, intelligent transportation, etc. The rapid growth of various types of information makes highway data continue to develop toward the trend of big data in terms of scale, type, and structure, showing the characteristics of multi-source heterogeneous. This article discusses efficient data retrieval and query methods for specific highway basic databases and simulated highway spatial large data sets. In order to better manage spatial objects and maintain their positional relationship with grid cells, it is proposed to combine inverted index with grid index. In order to break the dependence of the rim radius on the previous traversal results, the serial rim access K nearest neighbor (KNN) algorithm is appropriately improved, and the rim radius is updated by increasing the mesh side length, combined with multi-threading technology Achieve access to multiple rims to improve the query performance of highway big data. Test data by modifying the size, spatial grid sides and these K values, the average performance are improved.

Recent technological developments have led to the rapid creation of large datasets of images at a low cost. Thus, it is necessary to develop methods capable of retrieving images from gigantic datasets quickly and reliably. Given the high computational cost of this task, it is necessary to create a compact representation of each element in the set of images to be searched. Sparse representation makes it possible to perform searches. Sparse signal representation is a powerful tool for capturing, representing and compressing signals in high dimensions. This collection is usually called a “dictionary”, and its elements are called “words” or “Atoms”. The idea of sparse representation represents images through a linear combination of few atoms in the dictionary. This research work is proposed to build an inverted index using sparse coding to ensure the relevant image retrieval. This work is devoted to studying and developing methods for image retrieval using dictionary learning. The proposed research work has developed a framework for dictionary learning and coefficient learning simultaneously. Here, KSVD based approach is used for dictionary learning and three optimization schemes viz. OR, LARS, Elastic-Net are used to optimize the sparse codes. From various aspects, the proposed framework shows consistent performance over existing approaches on two publically available & widely acceptable datasets, viz Coil and Caltech-256.

Currently, one method to deal with the storage and computation of multimedia retrieval applications is an approximate nearest neighbor (ANN) search. Hashing algorithms and Vector quantization (VQ) are widely used in ANN search. So, K-mean clustering is a method of VQ that can solve those problems. With the increasing growth of multimedia data such as text view, image view, video view, audio view, and 3D view. Thus, it is a reason that why multimedia retrieval is very important. We can retrieve the results of each media type by inputting a query of that type. Even though many hashing algorithms and VQ techniques are proposed to produce a compact or short binary codes. In the real-time purposes the exhaustive search is impractical, and Hamming distance computation in the Hamming space suffers inaccurate results. The challenge of this paper is focusing on how to learn multimedia raw data or features representation to search on each media type for multimedia retrieval. So we propose a new search method that utilizes K-mean hash codes by computing the probability of a cluster in the index code. The proposed employs the index code from the K-mean cluster number that is converted to hash code. The inverted index table is constructed basing on the K-mean hash code. Then we can improve the original K-mean index accuracy and efficiency by learning a deep neural network (DNN). We performed the experiments on four benchmark multimedia datasets to retrieve each view such as 3D, image, video, text, and audio, where hash codes are produced by K-mean clustering methods. Our results show the effectiveness boost the performance on the baseline (exhaustive search).

Two major functions required in textual data modelling and knowledge discovery especially in modern customer interaction and research are search and sentiment analysis. Recent research has however not been able to combine these two in a way that instils flexibility into the iterative process of textual analysis for decision making. In this work, the Opinion and Context-Aware Inverted Index graph model is proposed for performing sentiment search and analysis on textual data. Unlike previous works, the use of the proposed model retrieves needed information without requiring re-processing of sentiment information. The proposed approach clarifies the difference between sentiment search and sentiment categorization. Furthermore, it shows how to perform opinion aware search based on graph traversals, pattern matching and aspect opinion filtering. To evaluate the flexibility and capabilities of the proposed scheme, the feature interest range, customer feature satisfaction/dissatisfaction intensity, feature co-mentions, and sentiment based ranking metrics of various bipartite projections for feature co-mention sub graphs using PageRank are extracted from a well-studied dataset on online product reviews with an extension of the proposed model. The chosen design and methodology is shown to be suitable for big data scale implementations.

Boolean AND queries (BAQ) are one of the most important types of queries used in text searching. In this paper, a graph-based indexing technique is proposed to improve the search latency of BAQ. It shows how a graph structure represented using a hash table can reduce the number of intersections needed for the execution of BAQ. The performance of the proposed technique is compared with one of the most widely used index structures for textual documents called Inverted Index. A detailed performance analysis is performed through prototyping and measurement on a system subjected to a synthetic workload. To get further performance insights, the proposed graph-based indexing technique is also compared with an enterprise-level search engine called Elasticsearch which uses Inverted Index at its core. The analysis shows that the graph-based indexing technique can reduce the latency for executing BAQ significantly in comparison to the other techniques.

This paper solves the problem of approximate nearest neighbor queries on high-dimensional large data sets. The two most representative methods to solve the approximate nearest neighbor query problem on high-dimensional and large-scale data sets are based on inverted multi-index and based on inverted index. The query algorithm based on the inverted multi-index requires frequent access operations to the memory, which causes more waste of resources than the query operation based on the distance order. Traditional query algorithms based on inverted indexes need to divide the entire feature space into a large number of regions to ensure the accuracy of query results when solving the problem of high-dimensional large data sets, so a large amount of space resources are required. Based on the inverted index, a query algorithm is proposed. Through the subdivision process of Voronoi Cells that are initially divided into part of the original data set, the purpose is to significantly improve the high-dimensional data set without dividing a large number of regions. On the query performance, and avoid frequent access operations to the random access memory. Theoretical analysis and experimental results show that the proposed method not only effectively improves the query processing efficiency, but also ensures the accuracy of the query.

Industrial big data analysis and mining are extremely complicated since it has complex correlations and heterogeneous structure from multiple data source. The growing industrial big data makes data analysis and mining extremely complicated. However, the traditional analysis approach based on relational databases or data warehouses are not flexible enough to deal with multi-source heterogeneous data and are less efficient to do search and analysis operation. Based on Spark and Elasticsearch, this paper presents a multi-dimensional analysis method and system for industrial big data. An OLAP model architecture based on JSON document structure is proposed, which can use Key-Value structure to flexibly define diverse industrial data, and the multi-dimensional structure model is easy to query and analyze. The table structure in the dimension information is converted into a JSON-based document structure, and the dimension information contained in the fact table is stored by the nested document. Elasticsearch is used to store the document structure tree and build an inverted index, which can improve the efficiency of the data analysis query. The query and analysis operations are transformed into the traversal and query operations in the document content. The time efficiency of the multi-dimensional analysis system based on Elasticsearch is much better than the analysis efficiency based on Hive.

A Bloom filter is a space-efficient probabilistic data structure that allows for set membership queries with some degree of false positives. In this paper, we propose a technique to add search functionality using a variant of Bloom filters - Spectral Bloom filters. Apart from being space-efficient, our proposed solution produces results comparable to search techniques such as Inverted Index and is a strong candidate for client-side searching.

In this paper, we present a finite-state approach to efficiently decode a sequence of Rice codes. The proposed method is capable of decoding a byte stream for any Golomb parameter for unboundedly large alphabets with constant space complexity. Performance of the approach is evaluated in comparison to the conventional bit-level decoding algorithm on compressed inverted indexes with respect to various parameter values. It is observed that decoding performance of the method increases with the mean value of encoded integers. Speed gains up to about a factor of 2 are empirically obtained in comparison with the conventional decoding from the point where the optimal value of the divisor is computed as 128. Results show that it is particularly effective for tasks in which a stream of large integers are encoded such as compression of document identifier gaps in inverted indexes.

This paper introduces a new graph-based indexing (GBI) technique for big data systems. It uses a directed graph structure that effectively captures the simultaneous occurrence of multiple keywords in the same document. The objective is to use the relationship between the search keywords captured in the graph structure to effectively retrieve all results of Boolean AND queries at once. The performance of the proposed technique is compared with the conventional inverted index-based technique. This paper highlights that, irrespective of the intersection algorithm used to evaluate Boolean AND queries, GBI always returns Boolean AND search results faster than the inverted index. This is due to the fact that GBI always performs a smaller number of intersection operations and avoids intersection if search keywords do not have a common document. A preliminary performance analysis is performed through prototyping and measurement on a system subjected to a synthetic workload. The analysis shows that GBI improves search latency when executing Boolean AND queries by an average of 69% to 99.9% in comparison to the inverted index.

Aiming at the problem of existing bag-of-visual words based image retrieval algorithm, such as poor stability and low retrieval accuracy, a bag-of-visual words based improved image retrieval algorithm (IBVW) is proposed, which extracts features from the images in the database. The approximate K-means algorithm is adopted to cluster the image features into visual words and store them in the database. And then, the feature extraction and the inverted index in the online stage are implemented on the query image to find the images with high similarity in the database. At last, the best matching image is acquired through the similarity calculation, voting scheme and homography based matching algorithm. Simulation results and performance analysis show that the accuracy of our retrieval algorithm is improved by about 10% compared with existing methods for vision indoor positioning.

A binary program can be abstracted as a set of hashes computed on pieces of disassembled code. Associating these pieces of code with other programs can provide extra information for malware researcher, useful for detection, attribution and for determining the Indicators of Compromise. Current methods for searching files that contain a given piece of code provide poor performance. The paper presents an original solution which is efficient, providing a scalable approach at the same time. The code hashes are indexed using the inverted index, which is designed and implemented as an in-memory lookup table, providing constant time for getting the files that contain a code hash and is optimized for storage efficiency. The lookup table associates a code hash to the files that contain it. Furthermore, our solution offers support for computing code similarity, which is achieved by using, along with our indexing mechanism, a traditional NoSQL database that stores the forward index (association between a file and its code hashes) and the file metadata. Our solution provides fast update capability, due to the batch operations proposed when adding new files. When it comes to building the inverted index, our solution is 50 times faster than MongoDB given a collection of one million samples.

Large enterprise systems often produce a large volume of event logs, and event log parsing is an important log management task. The goal of log parsing is to construct log templates from log messages and convert raw log messages into structured log messages. A log parser can help engineers monitor their systems and detect anomalous behaviors and errors. Most existing log parsing methods focus on offline methods, which require all log data to be available before parsing. In addition, the massive volume of log messages makes the process complex and time-consuming. In this paper, we propose Paddy, an online event log parsing method. Paddy uses a dynamic dictionary structure to build an inverted index, which can search the template candidates efficiently with a high rate of recall. The use of Jaccard similarity and length feature to rank candidates can improve parsing precision. We evaluated our proposed method on 16 real log datasets from various sources including distributed systems, supercomputers, operating systems, mobile systems, and standalone software. Our experimental results demonstrate that Paddy achieves the highest accuracy on eight data sets out of sixteen datasets compared to other baseline methods. We also evaluated the robustness and runtime efficiency of the methods and the experimental results show that our method Paddy achieves superior stableness and is scalable with a large volume of log messages.

With the development of science and technology, a lot of information and data are generated rapidly in the process of using computers, and the amount of data also presents an explosive growth. Traditional relational databases such as mysql are gradually unable to meet the needs of users for quick retrieval. But Elasticsearch makes up for this slow retrieval by providing users with a quick way to do it. Therefore, in this paper, we use the Flask framework in python to write a system for rapid retrieval and visualization of media data. Firstly, a nonrelational database like MongoDB was used to store the raw media data we crawled from the network. Then import the data into the cluster set up by Elasticsearch, create a map of the data, add a Chinese word segmentation parser, and set up an inverted index, so that the data can be used to accurately retrieve information in the future. At the same time, Kibana can be used to visually display and present the data.

Counting frequent k-mers as patterns in a long sequence is a typical data-mining problem and contributes to broad applications in bioinformatics. Existing methods of k-mer counting usually produce all the possible contiguous subsequences of length k that are contained in a given sequence. However, these methods often spawn numerous redundant and possibly meaningless k-mers. This inherently gives rise to excessive runtime and space overhead at sequence analysis. Moreover, most of the k-mer counting algorithms consider only single-length contiguous subsequences, which limits the diversity of data mining and knowledge discovery. Previous studies have demonstrated that closed patterns contain the complete information regarding the corresponding patterns. Inspired by the application of the upperclosure property of sequential patterns, we propose an efficient algorithm, called CloKmer, to find closed k-mers of various lengths that are compact yet lossless representation of k-mers. CloKmer utilizes the inverted index to project the original sequence onto an equivalent set and then mines closed k-mers by exploiting space pruning and upper-closure checking. Our experimental results demonstrate that CloKmer generates average 44% less patters but still achieves a comparable accuracy when classifying transcription factor binding sites (TFBSs), compared to traditional (k-mer-based classification) methods.

The big data revolution has created a hefty demand for searching large-scale electronic health records (EHRs) to support clinical practice, research, and administration. Despite the volume of data involved, fast and accurate identification of clinical narratives pertinent to a clinical case being seen by any given provider is crucial for decision-making at the point of care. In the general domain, this capability is accomplished through a combination of the inverted index data structure, horizontal scaling, and information retrieval (IR) scoring algorithms. These technologies are also being used in the clinical domain, but have met limited success, particularly as clinical cases become more complex. One barrier affecting clinical performance is that contextual information, such as negation, temporality, and the subject of clinical mentions, impact clinical relevance but is not considered in general IR methodologies. In this study, we implemented a solution by identifying and incorporating the aforementioned semantic contexts as part of IR indexing/scoring with Elasticsearch. Experiments were conducted in comparison to baseline approaches with respect to: 1) evaluation of the impact on the quality (relevance) of the returned results, and 2) evaluation of the impact on execution time and storage requirements. The results showed a 5.1-23.1% improvement in retrieval quality, along with achieving 35% faster query execution time. Cost-wise, the solution required 1.5-2 times larger space and about 3 times increase in indexing time. The higher relevance demonstrated the merit of incorporating contextual information into clinical IR, and the near-constant increase in time and space suggested promising scalability.

The increasing concern with false information has stimulated research in joint Fact Extraction and VERification (FEVER). Now we propose a system by deep learning which can help people identify the authenticity of most claims as well as providing evidences selected from knowledge source like Wikipedia. In this paper, we examine how to use deep learning method to improve the performance of the automatic fact verification system. Firstly, the inverted index of the knowledge base is established by using a Python package named Whoosh. Secondly, the claim is regularized by the Named Entity Recognition (NER) tool, and the most relevant documents are filtered based on the relevance ranking algorithm. Thirdly, top 20 relevant sentences for each claim are filtered by word embeddings. Finally, the effectiveness of each sentence and the label of claim is judged based on the two-level pre-training model. Our approach achieved a 0.89 document.

Similarity search of massive high-dimensional data is an important issue in the field of text data computation and search, which seriously affects the efficiency and convenience of text search and use. This paper proposes a high-performance text vector similarity search method, and proposes overlapping degree to describe the statistical characteristics of query vectors recurring in inverted index. Based on overlapping degree, candidate data sets are generated and sorted, distance calculation is carried out in candidate data set sequence, unnecessary calculation is reduced, and computation scale is reduced. Similar vectors of query vectors can be quickly obtained with very short index construction time and small memory overhead. The experimental results show that compared with the representative four methods, the index construction time of our method is shortened to 22-223 times, the index size memory overhead is reduced by 2-18 times, and the query speed advantage can be obtained with high recall rate, which greatly improves the performance and efficiency of text data similarity search.

In the dictionary based string matching problem, the positions in which a short sequence of symbols, query, occurs in a longer sequence, source, have to be retrieved. To improve the query search efficiency, the source can be pre-processed to build an inverted index, that is a table storing positions of occurrences of certain substrings in the text. Given an inverted index, various algorithms can be utilized to retrieve the position of the query in the source. In the literature, motivated by text retrieval and web search applications, the small v/s small (SvS) algorithm is often considered for the case in which the substrings stored are k-gram codes, i.e. all possible substrings of length k. In [9] we have proposed a novel approach to the string matching problem by letting the strings generating the inverted index be a variable length code, i.e. posting code, to be optimally design for a given performance metric. Posting codes [9] generalize classic k-gram codes and enable new query retrieval algorithms with potentially lower complexity than the SvS algorithm. In this paper, we propose a new query retrieval algorithm, the forward-backward SvS (FB-SvS) algorithm which can be applied when the posting code is a complete fix-free code. The complexity of the FB-SvS algorithm for various fix-free codes is investigated and numerical experiments using the human DNA sequence as the source are presented.

Cross-modal hashing, which searches nearest neighbors across different modalities in the Hamming space, has become a popular technique to overcome the storage and computation barrier in multimedia retrieval recently. Although dozens of cross-modal hashing algorithms are proposed to yield compact binary code representation, applying exhaustive search in a large-scale dataset is impractical for the real-time purpose, and the Hamming distance computation suffers inaccurate results. In this paper, we propose a novel index scheme over binary hash codes in cross-modal retrieval. The proposed indexing scheme exploits a few binary bits of the hash code as the index code. Based on the index code representation, we construct an inverted index structure to accelerate the retrieval efficiency and train a neural network to improve the indexing accuracy. Experiments are performed on two benchmark datasets for retrieval across image and text modalities, where hash codes are generated by three cross-modal hashing methods. Results show the proposed method effectively boosts the performance over the benchmark datasets and hash methods.

With the rapid development and comprehensive popularization of information technology, in order to reduce resource consumption and environmental pollution, all walks of life have made efforts to promote the construction of information technology in response to the call of the state to achieve paperlessness. When more and more information data is accumulated at the PB level per second, usually we use a kind of information retrieval method to filter the files in the database that quickly and accurately search the data file which users care. This paper proposes a retrieval cluster structure based on distributed network design and performs unsupervised machine learning on the unstructured data content according to the classification learning model, so that the child nodes have the function of automatically identifying the semantics of the article, then the second inverted index is obtained by feedback learning results that it was based on the original index . The practical application results show that the design model is feasible, not only significantly improves the retrieval effect and the accuracy of data screening, but also provides strong support for subsequent big data analysis.

The evolutionary multi-objective optimization algorithm was used to optimize the clustering and splitting of nodes in the construction of inverted spatial objects index tree(ITSR) in this paper. Considering the objective factors including object's coverage, overlap, group center distance, directory rectangle perimeter and the word similarity between tree nodes, etc., a multi-objective optimization model for solving the optimal ITSR construction is established. To solve the model, this paper find a novel method of constructing high efficiency inverted text-spatial R-tree index. The experimental results show that the algorithm supports the multi-objective optimal clustering of ITSR with high efficiency and accuracy .

Community search that finds only the communities pertaining to the query input has been widely studied from simple graphs to attributed graphs. However, a significant limitation of previous studies is that they all require the input of query nodes, which makes it difficult for users to specify exact queries if they are unfamiliar with the queried graph. To address this issue, in this paper we study a novel problem of keyword-centric community search (KCCS) over attributed graphs. In contrast to prior studies, no query nodes, but only query keywords, need to be specified to discover relevant communities. Specifically, given an attributed graph G, a query Q consisting of query keywords WQ, and an integer k, KCCS serves to find the largest subgraph of k-core of G that achieves the strongest keyword closeness w.r.t. WQ. We design a new function of keyword closeness and propose efficient algorithms to solve the KCCS problem. Furthermore, a novel core-based inverted index is developed to optimize performance. Extensive experiments on large real networks demonstrate that our solutions are more than three times faster than the baseline approach, and can find cohesive communities closely related to the query keywords.

With the explosive growth of online images and the popularity of search engines, a great demand has arisen for small and medium-sized enterprises to build and outsource large-scale image retrieval systems to cloud platforms. While reducing storage and retrieval burdens, enterprises are at risk of facing untrusted cloud service providers. In this paper, we take the first step in studying the problem of query authentication for large-scale image retrieval. Due to the large size of image files, the main challenges are to (i) design efficient authenticated data structures (ADSs) and (ii) balance search, communication, and verification complexities. To address these challenges, we propose two novel ADSs, the Merkle randomized k-d tree and the Merkle inverted index with cuckoo filters, to ensure the integrity of query results in each step of image retrieval. For each ADS, we develop corresponding search and verification algorithms on the basis of a series of systemic design strategies. Furthermore, we put together the ADSs and algorithms to design the final authentication scheme for image retrieval, which we name ImageProof. We also propose several optimization techniques to improve the performance of the proposed ImageProof scheme. Security analysis and extensive experiments are performed to show the robustness and efficiency of ImageProof.

We are witnessing increasing interests in longitudinal analytics on social media data. Longitudinal analytics takes into account an interval and considers the temporal popularity of social media data in the interval, rather than only considering recently generated social media data in real-time search. We study a fundamental functionality in longitudinal analytics - the top-k temporal keyword (TkTK) querying. A TkTK query takes as input a set of query keywords and an interval, and returns the top-k most significant social items, e.g., tweets, where the significance of a social item is defined based on a combination of the textual relevance and temporal popularity. We model social media data as a forest of linkage trees along the time dimension, which well models the propagation processes, e.g., replies and forwards, among different social items. Based on the forest, we model the temporal popularity of a social item across time as a popularity time series. We design two indexing structures that index social items' popularity time series and textual content in a holistic manner - the temporal popularity inverted index (TPII) and the log-structured merge octree (LSMO). Empirical studies with two substantial social media data sets offer insight into the design properties of the indexes and confirm that LSMO enables both efficient query processing and indexing structure updates.

This paper investigates a new query, called an MIO query, that retrieves the Most Interactive Object in a given spatial dataset. Consider that an object consists of many spatial points. Given a distance threshold, we say that two objects interact with each other if they have a pair of points whose distance is within the threshold. An MIO query outputs the object that interacts with other objects the most, and it is useful for analytical applications e.g., neuroscience and trajectory databases. The MIO query processing problem is challenging: a nested loop algorithm is computationally inefficient and a theoretical algorithm is computationally efficient but incurs a quadratic space cost. Our solution efficiently processes MIO queries with a novel index, BIGrid (a hybrid index of compressed Bitset, Inverted list, and spatial Grid structures), with a practical memory cost. Furthermore, our solution is designed so that previous query results and multi-core environments can be exploited to accelerate query processing efficiency. Our experiments on synthetic and real datasets demonstrate the efficiency of our solution.

A set containment join operates on two set-valued attributes with a subset (⊆) relationship as the join condition. It has many real-world applications, such as in publish/subscribe services and inclusion dependency discovery. Existing solutions can be broadly classified into union-oriented and intersection-oriented methods. Based on several recent studies, union-oriented methods are not competitive as they involve an expensive subset enumeration step. Intersection-oriented methods build an inverted index on one attribute and perform inverted list intersection on another attribute. Existing intersection-oriented methods intersect inverted lists one-by-one. In contrast, in this paper, we propose to intersect all the inverted lists simultaneously while skipping many irrelevant entries in the lists. To share computation, we utilize the prefix tree structure and extend our novel list intersection method to operate on the prefix tree. To further improve the efficiency, we propose to partition the data and use different methods to process each partition. We evaluated our methods using both real-world and synthetic datasets. Experimental results show that our approach outperforms existing methods by up to 10×.

Static index pruning techniques remove postings from inverted index structures in order to decrease index size and query processing cost, while minimizing the resulting loss in result quality. A number of authors have proposed pruning techniques that use basic properties of postings as well as results of past queries to decide what postings should be kept. However, many open questions remain, and our goal is to address some of them using a machine learning based approach that tries to predict the usefulness of a posting. In this paper, we explore the following questions: (1) How much does an approach that learns from a rich set of features outperform previous work that uses heuristic approaches or just a few features? (2) What is the relationship between index size and query processing speed in static index pruning? We show that an approach that prunes postings using a rich set of features including post-hits and doc-hits can significantly outperform previous approaches, and that there is a very pronounced trade-off between index size and query processing speed for static index pruning that has not been previously explored.