The non-volatile memory (NVM) with DRAM-like performance and disk-like persistency has attracted considerable attention in a variety of index structures, including hash table, B-Tree and R-Tree. However, existing NVM-optimized consistent R-Tree is still suboptimal because its single level system neglects the potential boost that DRAM can bring. In this paper, we first propose a hybrid DRAM-NVM consistent R-Tree (HR-Tree), which separately stores internal nodes in DRAM and leaf nodes in NVM. To avoid inconsistency, HR-Tree uses several auxiliary flag bits and pointers to record the process of writes to NVM and employs persistence operations to strictly control the order of writes to NVM. To reduce DRAM consumption, which mainly depends on the metadata size of a leaf node, we present a shared byte strategy to abolish restrictions on metadata size while still keeping HR-Tree consistency. Next, for further shortening search time, we propose an alternative Hilbert-curve-based hybrid R-Tree (HHR-Tree). It has better search efficiency yet leads to insertion performance degradation. Contrary to in-place update in HR-Tree, HHR-Tree applies out-of-place mechanism to enforce data consistency. We conduct comprehensive evaluations on Intel Optane DC Persistent Memory. The proposed HR-Tree outperforms FBR-Tree in terms of insertion, deletion and search throughput while HHR-Tree exhibits a significant improvement for search performance by sacrificing insertion efficiency.

Summary Tables on the web provide rich information. To make sufficient usage of web tables, the semantics of columns should be identified correctly. The absence, misspelling, and abbreviation in column names bring the challenges in column semantics identification. Facing this challenge, we extract multiple features including keywords, concepts, and structure from the content in the column. Thus, we could identify the column semantics by matching these multiple features. For the extraction and matching with these features, we propose efficient algorithms. Experimental results on real data sets show that our solution achieves high performance.

Abstract This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., $$\subseteq$$ ⊆ ) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as frequency-hashjoin or $${\mathsf {FreshJoin}}$$ FreshJoin in short, to evaluate SCJ efficiently. $${\mathsf {FreshJoin}}$$ FreshJoin builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that $${\mathsf {FreshJoin}}$$ FreshJoin can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose $${\mathsf {FreshJoin}}$$ FreshJoin from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that $${\mathsf {FreshJoin}}$$ FreshJoin usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time.

String similarity join (SSJ) is essential for many applications where near-duplicate objects need to be found. This paper targets SSJ with edit distance constraints. The existing algorithms usually adopt the filter-andrefine framework. They cannot catch the dissimilarity between string subsets, and do not fully exploit the statistics such as the frequencies of characters. We investigate to develop a partition-based algorithm by using such statistics. The frequency vectors are used to partition datasets into data chunks with dissimilarity between them being caught easily. A novel algorithm is designed to accelerate SSJ via the partitioned data. A new filter is proposed to leverage the statistics to avoid computing edit distances for a noticeable proportion of candidate pairs which survive the existing filters. Our algorithm outperforms alternative methods notably on real datasets.

Simulation is an essential means for evaluating WSN applications. As many WSN applications embrace in-network data processing functionalities, more sophisticated simulation tools with data-enriched test case scenarios, such as extensive environment input and accurate hardware models, are necessary. This work devises TOSSIM DB, a data-enriched WSN simulation framework, allowing unmodified applications to be evaluated as if virtually deployed in a third-party environment. Notable features of TOSSIM DB include i) integrating third-party sensor datasets as virtual test scenarios, ii) emulating the statistical properties of sensor devices, and iii) seamless integration with the TinyOS tool-chain.

World wide web provides plenty of multimedia resources for creating rich media web applications. However, the collected music and other media resources always mismatch in the metric of time length. Existent music resizing approaches suffer from perceptual artifacts which degrade the performance of resized music. In this paper, a novel structure-aware music resizing approach is proposed. Through lyrics analysis, our approach can compress different parts of a music piece in variant compression rates. Experimental results show that the proposed method can effectively generate resized songs with good quality.

This paper introduces a fast data dissemination method for structured peer-to-peer networks. The work is motivated on one side by the increase in non-volatile memory available on mobile devices and, on the other side, by observed behavioral patterns of the users. We envision a scenario where users come together for short periods of time (e.g. public transport, conference sessions) and wish to be able to share large collections of data. With hundreds and even thousands of data, items stored on small devices, content publication is simply too energy and time consuming. By indexing summary information obtained by a combination of multi-resolution analysis and k-means, our method (Hyper-Ad) is able to cut down the overall construction time of an overlay network such as CAN by an order of magnitude, as well as provide fast approximate similarity search on such a network. The results of our extensive experimental studies confirm that Hyper-M is both energy and time efficient, and provides good precision and recall.

This paper describes a PC-cluster based parallel DBMS, InfiniteDB, developed by the authors. InfiniteDB aims at efficiently storing and processing of massive databases in response to the rapidly growing in database size and the need of high performance analyzing of massive databases. It supports the parallelisms of intra-query, inter-query, intra-operation, inter-operation and pipelining. It provides effective strategies for processing massive databases including the multiple data declustering methods, the declustering-aware algorithms for the execution of relational operations and other database operations, and the adaptive query optimization method. It also provides the functions of parallel data warehousing and data mining, the coordinator-wrapper mechanism to support the integration of heterogeneous information resources on the Internet, and the fault tolerant and resilient infrastructures. It has been used in many applications and has proved quite effective for storing and processing massive databases in practice.

A music data model, its query language and its application are proposed in this paper. Firstly, a music data model and its algebraic operations are given, which can be used to describe and manipulate musical data efficiently. Secondly, a structured query language on the model is proposed, which can be used to define and manage musical data. Finally, a digital music library, one of the applications of this model, is presented, which can be used to retrieve musical information, especially against musical instruments.