Symmetric searchable encryption (SSE) for geo-textual data has attracted significant attention. However, existing schemes rely on task-specific, incompatible indices for isolated specific secure queries (e.g., range or k-nearest neighbor spatial-keyword queries), limiting practicality due to prohibitive multi-index overhead. To address this, we propose RISK, a model for rich spatial-keyword queries on encrypted geo-textual data. In a textual-first-then-spatial manner, RISK is built on a novel k-nearest neighbor quadtree (kQ-tree) that embeds representative and regional nearest neighbors, with the kQ-tree further encrypted using standard cryptographic tools (e.g., keyed hash functions and symmetric encryption). Overall, RISK seamlessly supports both secure range and k-nearest neighbor queries, is provably secure under IND-CKA2 model, and extensible to multi-party scenarios and dynamic updates. Experiments on three real-world and one synthetic datasets show that RISK outperforms state-of-the-art methods by at least 0.5 and 4 orders of magnitude in response time for 1% range queries and 10-nearest neighbor queries, respectively.

The proliferation of online graph data - such as produced on social networks, citation networks, and online graph databases - calls for space-efficient graph indexing methods that support fast graph queries and graph analytics. Labeled property multidigraphs as a model of representing complicated graph data are widely used in practice. However, the fundamental problem of compressing and indexing labeled property multidigraphs has remained unsolved. In this paper, we focus on the static data case and propose a novel self-index, called CGraphIndex, to compress and index labeled property multidigraphs that for the first time achieves the high-order entropy space for multidigraph properties (the dominant term in practice) and the 1st-order graph entropy for multidigraph structures. A self-index actually encodes the original input and thus there is no need to store the input separately. CGraphIndex supports fundamental and navigational operations on the structures and on the properties in constant time, and supports fast property extraction on vertices and edges. Our experimental results on the large LDBC SNB benchmarks demonstrate that CGraphIndex outperforms the popular graph database systems (Community Editions), generally several times to orders of magnitude faster in query time and several times less in space usage for the compared interactive complex queries, business intelligence queries, as well as typical graph analytics BFS and PageRank.

Compressed self-indexes are used widely in string processing applications, such as information retrieval, genome analysis, data mining, and web searching. The index not only indexes the data, but also encodes the data, and it is in compressed form. Moreover, the index and the data it encodes can be operated upon directly, without need to uncompress the entire index, thus saving time while maintaining small storage space. In some applications, such as in genome analysis, existing methods do not exploit the full possibilities of compressed self-indexes, and thus we seek faster and more space-efficient indexes. In this paper, we propose a practical high-order entropy-compressed self-index for efficient pattern matching in a text. We give practical implementations of compressed suffix arrays using a hybrid encoding in the representation of the neighbor function . We analyze the performance in theory and practice of our recommended indexing method, called GeCSA. We can improve retrieval time further using an iterated version of the neighbor function. Experimental results on the tested data demonstrate that the proposed index GeCSA has good overall advantages in space usage and retrieval time over the state-of-the-art indexing methods, especially on the repetitive data.

Graph similarity search under the graph edit distance constraint has received considerable attention in many applications, such as bioinformatics, data mining, pattern recognition and social networks. Existing methods for this problem have limited scalability because of the huge amount of memory they consume when handling very large graph databases with tens of millions of graphs. In this article, we present a succinct index that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5-15 percent of the previous state-of-the-art indexing size while at the same time achieving several times acceleration in query time on the tested data. We also improve the query performance by augmenting the global filter with range searching, which allows us to perform similarity search in a reduced region. In addition, we propose two effective lower bounds together with a boosting technique to obtain the smallest possible candidate set. Extensive experiments demonstrate that our proposed approach is superior both in space and filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index for this problem that successfully scales to cope with the large dataset of 25 million chemical structure graphs from the PubChem dataset. The source code is available online.

Chien et al. [1, 2] introduced the geometric Burrows-Wheeler transform (GBWT) as the first succinct text index for I/O-efficient pattern matching in external memory; it operates by transforming a text T into point set S in the two-dimensional plane. In this paper we introduce a practical succinct external memory text index, called mKD-GBWT. We partition S into σ2subregions by partitioning the x-axis into σ intervals using the suffix ranges of characters of T and partitioning the y-axis into σ intervals using characters of T, where σ is the alphabet size of T. In this way, we can represent a point using fewer bits and perform a query in a reduced region so as to improve the space usage and I/Os of GBWT in practice. In addition, we plug a crit-bit tree into each node of string B-trees to represent variable-length strings stored. Experimental results show that mKD-GBWT provides significant improvement in space usage compared with the state-of-the-art indexing techniques. The source code is available online [3].

Suffix array is a fundamental data structure for many applications that involve string searching and data compression. We obtain the first linear time inplace suffix array construction algorithm which is optimal both in time and space for read-only integer alphabets. Our algorithm settles the open problem posed by Franceschini and Muthukrishnan [1]. The open problem asked to design in-place algorithms in o(n log n) time and ultimately, in O(n) time for integer alphabets with |Σ| ≤ n. Our result is in fact slightly stronger since we allow |Σ| = O(n). Besides, we extend it to obtain an optimal O(n log n) time in-place suffix sorting algorithm for read-only general alphabets (i.e., only comparisons are allowed).

Next generation sequencing technologies generate normous amount of short reads, which poses a significant computational challenge for short read alignment. Furthermore, because of sequence polymorphisms in a population, repetitive sequences, and sequencing errors, there still exist difficulties in correctly aligning all reads. We propose a space-efficient compressed suffix array-based method for short read alignment (CS2A) whose space achieves the high-order empirical entropy of the input string. Unlike BWA that uses two bits to represent a nucleotide, suitable for constant-sized alphabets, our encoding scheme can be applied to the string with any alphabet set. In addition, we present approximate pattern matching on compressed suffix array (CSA) for short read alignment. Our CS2A supports both mismatch and gapped alignments for single-end and paired-end reads mapping, being capable of efficiently aligning short sequencing reads to genome sequences. The experimental results show that CS2A can compete with the popular aligners in memory usage and mapping accuracy. The source code is available online.

In this paper we develop a simple and practical text indexing scheme for compressed suffix arrays (CSA). For a text of n characters, our CSA can be constructed in linear time and needs 2nHk+ n + o(n) bits of space for any k ≤ clogσn - 1 and any constant ckdenotes the kth order entropy. We compare the performance of our method with two established compressed indexing methods, the FM-index and the Sad-CSA. Experiments on the Canterbury Corpus and the Pizza&Chili Corpus show significant advantages of our algorithm over two other indexes in terms of compression and query time. Our storage scheme achieves better performance on all types of data present in these two corpora, except for evenly distributed data, such as DNA. The source code for our CSA is available online.