Cache management is a critical concern for both key-value stores and relational DBMSs. The most significant challenge in cache management is the cache replacement strategy, which directly affects the throughput and latency of the cache manager. While the Least Recently Used (LRU) policy is widely adopted by many systems, it suffers from severe performance degradation in multi-threaded environments due to lock contention. This contention arises when multiple threads attempt to update the LRU list simultaneously. Motivated by this issue, we propose a new cache management scheme called twCache, designed to deliver high performance in concurrent environments. The novelty of twCache lies in two key aspects. First, it proposes to partition the replacement policy data structure into thread-wise sublists, each corresponding to one thread. Such a structure can enable thread isolation so that the requests from one thread will not introduce lock contention with other threads, yielding high concurrency performance. Second, we propose a low-cost technique to combine recency and hotness for victim selection during cache replacement. Each sublist is maintained as an LRU list, representing the recency of object requests. Each cached object's hot count is proposed to reflect its hotness, defined as the number of sublists visiting the object. We conducted extensive experiments to compare twCache with traditional algorithms (LRU, FIFO, and 2Q) and the state-of-the-art FrozenHot policy. Three types of trace are used, including 39 Twitter traces, 23 MSR traces, and 6 YCSB workloads. The results show that twCache achieves$12\times$and$7\times$higher throughputs than LRU on the Twitter and MSR traces, respectively. Meanwhile, twCache outperforms LRU by$4.8\times$in the average throughput under YCSB workloads.

Multimodal Summarization aims to use multimodal data to generate accurate and concise summaries for long sentences. While previous work has achieved promising success, they have overlooked the mismatching among multimodal semantics and lacked subject information guidance for adaptive referential images. Motivated by this observation, we propose ASSM, anAdaptiveSubject-focused modeling for multimodal summarization viaSemanticMatching. The novelty of ASSM lies in two aspects. First, we propose a multimodal semantic matching module that projects multimodal inputs into a shared joint embedding semantic space to determine whether the semantics between multimodalities are mismatching. Second, we propose an adaptive subject-focused guide module, which adaptively references images to learn subject tokens based on the multimodal semantic matching results. With these subject tokens, we are able to focus on the subject information, providing precise guidance for summary generation. We conduct extensive experiments on two standard benchmarks and compare ASSM with 17 existing models. The experimental results regarding ROUGE, BERTScore, and MoverScore show that the proposed ASSM model outperforms all competitors, achieving state-of-the-art performance and suggesting the effectiveness of our proposal. In addition, we provide a case study to further demonstrate the usability of ASSM.

LSM-tree has been widely used in key-value stores to offer high write throughputs. However, LSM-tree suffers from the block-cache invalidation problem caused by periodical compaction operations, which lowers the efficiency of the block cache and leads to poor read performance, especially for range queries. To address this problem, we propose a novel cache component named Range Cache to accelerate range queries on LSM-based key-value stores. The differences between Range Cache and the traditional block cache lie in two aspects. First, Range Cache caches the query results, i.e., key-value pairs, rather than data blocks. Second, in contrast to the traditional block cache that utilizes a hash table to index data, Range Cache incorporates an ordered index, which is more efficient for range queries. Further, we integrate Range Cache into LSM-based key-value stores without disturbing other components. With Range Cache, we can eliminate the impact of compaction operations on the block cache, avoiding the block-cache invalidation problem and reducing disk I/Os for point/range queries. We implement Range Cache on top of RocksDB and conduct system-to-system comparisons to compare Range Cache with LevelDB, RocksDB, LSbM-tree, and RemixDB under various settings. The experimental results show that Range Cache can significantly improve the cache efficiency and increase the throughput, especially for range queries.

Few-shot learning (FSL) is a machine learning method aimed at learning problem-solving models from a small number of samples. Few-shot classification is a task that utilizes few-shot learning for image classification. However, the existing models have poor classification performance when dealing with datasets with large differences in target scale distribution. In view of the large difference in the scale distribution of the sample target in the few-shot learning dataset, this paper proposes a novel few-shot classification model based on multi-scale Vision Transformer using semantic prompt. This model uses the Transformer block which has more generalization ability and long-range dependencies, and constructs a multi-scale feature fusion model on the large-scale cross-domain and cross-scale dataset Meta-Dataset which consists of 10 datasets, including natural image datasets, handwritten characters, and graffiti datasets. By using an explicit multi-scale feature fusion method, the model can obtain category features with cross scale information, thereby improving the robustness of the model to sample targets of different scales. In addition, the model improved its performance by learning additional semantic prompt, achieving a 2.43% improvement.

The log-structured merge tree (LSM-tree) has been widely adopted as a backbone of modern key-value stores. However, the multiple exponentially increased levels of LSM-tree makes it suffer from high write amplification. Existing studies often improve the write performance by sacrificing the read performance, which is inefficient to make trade-offs between the update and search efficiency. In this paper, we exploit nonvolatile memory (NVM) to address the write amplification issue for systems with NVM-SSD hybrid storage, and further propose a reinforcement learning method to navigate between update and search efficiency on the varying workloads. Specifically, we first propose a lightweight hot data identification method to efficiently capture access recency as well as frequency in NVM with relative large capacity. On this basis, we can eliminate different versions of frequently updated data in high-performance NVM without pushing them to SSD. To improve the data access locality and facilitate fine-grained index tuning in each level, we devise a virtual-split method to partition the key space gradually without extra write amplification. Finally, we propose a cost based Q-learning algorithm to adaptively tune the data organizations of each partition according to the changing access patterns. Experimental results show that our approach outperforms existing methods by up to 2.67×.

The emergence of Zoned Namespaces SSDs, known as ZNS SSDs, has introduced new challenges and opportunities for key-value stores. Since LSM-tree has been widely adopted in key-value stores, such as RocksDB and HBase. Compared with traditional SSDs, ZNS SSDs have the advantages of lower over-provisioning costs, higher and more stable performance, and better space efficiency. However, ZNS SSDs also have some limitations like sequential writes on zones. To make ZNS SSDs efficient in LSM-tree-based key-value stores, it is necessary to revisit the LSM-tree to make it adapt to ZNS SSDs. In this paper, we first analyze the challenges of adapting LSM-tree to ZNS SSDs. Then, we propose a high-level architecture for a ZNS-SSD-aware LSM-tree-based key-value store.

With the development of big data applications, online analytics systems that aim to offer decision support for various businesses and tasks have become a research focus, which calls for efficient approaches to handling OLAP queries. However, traditional OLAP systems suffer from the costly interactions with disks or SSDs, making them hard to deliver high performance for OLAP query processing. In this paper, we propose to use the emerging persistent memory to construct an efficient in-memory analytics system to improve the performance for OLAP query processing. We present the overall architecture as well as the detailed algorithms for the proposed system, which is named PM-Picker, and finally discuss the implementation issue of the system.

In recent years, weakly supervised object detection (WSOD) methods using only image-level labels have received increasing attention, Due to the difficulty of manually labeling large-scale remote sensing images. However, existing methods cannot generate high-quality proposals when applying proposal generation methods to RSIs. Meanwhile, these methods ignore the fact that there are a large number of objects of different scales in RSIs. To address these issues, we propose a unique end-to-end dynamic feature fusion network (DFFNet) for WSOD in RSIs. First, we propose an intersection-over-union selective search (IoU-SS) algorithm to generate high-quality proposals by preferentially merging regions with high IoU. Furthermore, we design a novel and flexible dynamic feature fusion (DFF) module to dynamically acquire features of objects at different scales based on the information of the input image. The performance of WSOD in RSIs is further improved by using high-quality proposals and dynamically fused features. Comprehensive experiments and comparisons with state-of-the-art methods on two datasets of RSIs, i.e., NWPU VHR-10.v2 and DIOR, demonstrate the superiority of our proposed method.

LSM-tree has been widely used as a write-optimized storage engine in many key-value stores, such as LevelDB and RocksDB. However, conventional compaction operations on the LSM-tree need to read, merge, and write many SSTables, which we call Table Compaction in this paper. Table Compaction will cause two major problems, namely write amplification and block-cache invalidation. They will lower both write and read performance of the LSM-tree. To address these issues, we propose a novel compaction scheme named Block Compaction that adopts a block-grained merging policy to perform compaction operations on the LSM-tree. Block Compaction identifies the boundaries of data blocks and tries to avoid reusing data blocks, which not only reduces the write amplification but also alleviates the block-cache invalidation. We present cost analysis to theoretically demonstrate that Block Compaction is more efficient than the existing Table Compaction. Furthermore, we analyze the side-effects of Block Compaction and present three optimizations: (1) Selective Compaction is to reduce the space amplification of Block Compaction by integrating Table Compaction with Block Compaction. (2) Parallel Merging divides a compaction task into several sub-tasks and uses multiple workers to accomplish sub-tasks in parallel. (3) Lazy Deletion mitigates the overhead caused by traversing files at the tail of compaction operations. We implement a new key-value store named BlockDB based on Block Compaction and its optimizations. Then, we compare BlockDB with LevelDB, RocksDB, and L2SM using the YCSB benchmark. The results show that BlockDB can reduce write amplification up to 32% and running time by up to 43.6%, compared to its competitors. In addition, it can maintain the high performance for point lookups and range scans.

Non-Volatile Memory (NVM) has emerged as an alternative to next-generation main memories. Although many tree indices have been proposed for NVM, they generally use B+-tree-like structures. To further improve the performance of NVM-aware indices, we consider integrating learned indexes into NVM. The challenges of such an integration are two fold: (1) existing NVM indices rely on small nodes to accelerate insertions with crash consistency, but learned indices use huge nodes to obtain a flat structure. (2) the node structure of learned indices is not NVM friendly, meaning that accessing a learned node will cause multiple NVM block misses. Thus, in this paper, we propose a new persistent learned index called PLIN. The novelty of PLIN lies in four aspects: an NVM-aware data placement strategy, locally unordered and globally ordered leaf nodes, a model copy mechanism, and a hierarchical insertion strategy. In addition, PLIN is proposed for the NVM-only architecture, which can support instant recovery. We also present optimistic concurrency control and fine-grained locking mechanisms to make PLIN scalable to concurrent requests. We conduct experiments on real persistent memory with various workloads and compare PLIN with APEX, PACtree, ROART, TLBtree, and Fast&Fair. The results show that PLIN achieves 2.08x higher insertion performance and 4.42x higher query performance than its competitors on average. Meanwhile, PLIN only needs ~30 μs to recover from a system crash.

Recently, Zoned Namespaces (ZNS) SSDs have emerged as a hot topic in both academics and industries. Compared to conventional SSDs, ZNS SSDs have the advantages of less overhead of garbage collection and lower over-provisioning cost. However, ZNS SSDs only accept sequential writes, and the zones inside ZNS SSDs need to be carefully managed to maximize the advantages of ZNS SSDs. Therefore, how to make data management systems adapt to ZNS SSDs is becoming a challenging issue. Current database systems, either SQL databases or NoSQL data stores, are mainly designed toward magnetic disks or traditional SSDs (without zoned namespaces). In this paper, we explore the challenges and research opportunities of revising index structures for ZNS SSDs and focus on the B+-tree and LSM-tree, which represent the index structures for SQL databases and key-value stores. After summarizing the features of ZNS SSDs, we discuss the key issues of adapting the B+-tree to ZNS SSDs and the challenges of revising the LSM-tree (Log-Structured Merge tree) for ZNS SSDs. Finally, we suggest some future research work on this topic.

Join selectivity estimation is a fundamental problem in query optimization, which aims to estimate the cardinality returned by a join query. While join selectivity estimation has been extensively studied in relational databases, there are few studies toward join selectivity estimation for cross-model joins in multi-model databases, such as relation-tree joins between a relational table and a tree-structured document like a BSON file in MongoDB. So far, due to the popularity of MongoDB, many applications use both MongoDB and MySQL to organize heterogeneous data. Thus, it is necessary to devise efficient approaches for processing relation-tree joins running on relational and tree models. In this paper, we present an effective and efficient approach to estimate the join selectivity for relation-tree joins, which consists of a value join estimation and a structural join estimation. In particular, we propose a two-level sampling method that samples the relational tuples and tree nodes at two levels. Then, we apply the discrete learning algorithm to the tree node samples to estimate the join value distribution of the tree nodes. With this mechanism, we can capture the correlation between relational tuples and tree nodes and improve the estimation accuracy. We conduct experiments on the DBLP dataset and compare our approach to existing solutions, and the results suggest the effectiveness and efficiency of our proposal.

Existing approaches based on the SGR (single granularity recognition) improve the recognition accuracy by expanding the dataset, learning more robust feature representation or locating and amplifying significant parts. These approaches often suffer from heavy computational costs, high model complexity or additional non-classsification losses. In this paper, we propose a feature fusion method based on multi-classification losses, which can classify different granularity features and make the network focus on more useful information. The complexity and computational costs of our model have only increased slightly, which can be ignored. The results of comparative experiments show the effectiveness of our proposal on Stanford Cars dataset.

LSM-tree is widely used as a write-optimized storage engine in many NoSQL systems. However, the periodical compaction operations in LSM-tree cost many I/O bandwidths and CPU resources of the local server, resulting in throughput drops of the system. To address this issue, this paper proposes a new compaction scheme based on the FaaS (Functions as a Service) architecture, which is called FaaS Compaction. It utilizes the elastic computing capability of FaaS and always pushes compactions to a FaaS cluster. The FaaS cluster will perform actual compaction operations, which will not affect the processing of the local server. Therefore, we can maintain stable performance even when periodical compactions are triggered. We also present a Parallel Slight Compaction method to solve the timeout problem caused by heavy compactions. We implement the FaaS Compaction based on TerarkDB and a real FaaS cluster and experimentally compare the FaaS Compaction with the RocksDB's local compaction scheme and the state-of-the-art offloading compaction policy. The results suggest the efficiency, stability, and elasticity of our proposal.

With the rapid advance of Non-Volatile Memory (NVM), it has been a hot topic to improve traditional tree indices like B+-tree for NVM. However, due to the high cost of the writing operations on NVM, few existing tree indices can offer high performance for both read and write operations. For example, the WB-tree with unsorted leaf nodes is write-optimized but has poor search performance. To address this problem, in this paper, we propose a read/write-optimized tree index called TLBtree (Two-Layer B+-tree) for NVM. TLBtree consists of a read-optimized top layer and a write-optimized bottom layer. We notice that the top levels of a B+-tree are read frequently, while the bottom levels are written frequently. Motivated by such an observation, we propose to design a read-optimized top layer and a write-optimized layer for the TLBtree index. We offer several read optimizations to implement the top layer and employ write-optimized structures to organize the bottom layer. With this mechanism, we can alleviate the read and write tradeoff of the index on NVM. We conduct extensive experiments on a server with Intel Optane DC Persistent Memory and compare TLBtree with state-of-the-art NVM-based tree indices, including WB-tree, Fast&fair, and FPtree. The results show that TLBtree outperforms other indices in write-intensive workloads by up to 1.7x throughput and achieves comparable read-only performance with read-optimized indices.

Data-intensive systems are typical applications in the big data era. Most data-intensive systems employ LSM (Log-Structured Merge)-tree-based key-value stores, such as RocksDB and LevelDB. The LSM-tree has a multi-level data structure and can transform random writes into sequential ones by a special operation called compaction. However, compaction operations are costly and will increase the processing latency and lower the throughput of the LSM-tree. In this paper, we propose an adaptive lazy compaction method called ALC for the LSM-tree. The main idea of ALC is to delay compactions operations when the current workload is high, and to perform compactions when the system is low-loaded. With this mechanism, we can lower the impact of compactions on the system's performance and achieve high stability and low latency. Our preliminary experiments show that ALC outperforms RocksDB and the state-of-the-art method SILK in latency and throughput-stability.

In this paper, to improve the read performance of LSM-tree, we propose an enhanced LSM-tree called HotKey-LSM. The key idea of HotKey-LSM is to put hot keys and cold keys in two separated column families. Thus, when a hot key is not in the block cache, LSM-tree only needs to access a small hot-key LSM-tree to read the key. With this mechanism, most hot-key requests will be answered with low latency: if the hot key is in the block cache, we can return the memory address of the key; if it is not in the cache, we search the small hot-key LSM-tree. This differs from the traditional LSM-tree in that a hot-key request may traverse a large LSM-tree, which causes a high read latency. We implement HotKey-LSM on RocksDB and compare HotKey-LSM with the original RocksDB. The result in terms of QPS suggests the efficiency of our proposal.

Classification for big image data is an essential field of big data technology. Big image data classification has a wide range of applications, such as face recognition, object detection, and human posture recognition. Traditional methods for big image data classification usually ignore the close connection between different levels of features in neural networks. In this paper, we propose a new way for big image data classification that improves the previous method through the Multi-Level Feature Connection Network (MFC-Net). MFC-Net presents a multi-level feature connection module to mine more useful features for classification. Experiments show that MFC-Net significantly improves its baseline SSD (Single Shot Multibox Detector) and other advanced classification neural networks in the classic datasets Pascal VOC and Microsoft COCO.

Non-Volatile Memory (NVM) has emerged as an alternative to next-generation memories. Compared to the traditional DRAM, NVM offers data persistency and higher density. However, so far, NVM has higher accessing latency than DRAM. Therefore, to ensure the high performance of data accessing, we still need to consider using DRAM in memory architecture. This leads to the hybrid memory architecture involving DRAM and NVM. Some previous benchmark works have shown that such hybrid memory architecture is more efficient than NVM-only architecture. Due to NVM's unique properties, the traditional memory B+-tree becomes unsuitable for NVM because of its high cost of maintaining node orderliness and high space-filling feature. In this paper, we propose to optimize the Adaptive Radix Tree (ART) for the hybrid memory architecture and offer a new index called HART (Hybrid Adaptive Radix Tree). HART takes advantage of ART's deterministic structure to get good query performance. Meanwhile, we only selectively persist linked list to reduce NVM access cost. In particular, we exploit the compression path to improve the leaf node's space utilization, making the subtree shorter. We run a preliminary experiment on a server with Intel Optane DC Persistent Memory and compare HART with several NVM-aware indexes. The results suggest the efficiency of our proposal.

In this paper, we propose RotaryDS to provide fast storage service for massive data streams. RotaryDS uses a rotation storage model, which employs distributed data buckets to accept highly-arriving data streams. All data buckets have a state, i.e., they can be in the state of data idle waiting, data filling, write waiting, and data dumping. The state of a data bucket is changed according to the data operations. With the rotation storage model, we distribute massive data streams among multiple data buckets, thereby improving the write throughput of the storage system. We implement RotaryDS based on the rotation storage model and conduct preliminary experiments to compare it with MongoDB. The results suggest the efficiency of our proposal.

Non-volatile memory (NVM) as a new kind of future memory has several special properties such as non-volatility, read/write asymmetry, and byte address-ability. This makes it difficult to directly replace DRAM with NVM in the current memory hierarchy. Thus, a practical way is to construct a hybrid memory composed of both NVM and DRAM. Such hybrid memory architecture introduces many new challenges for existing algorithms. In this paper, we focus on the data placement issue in NVM-based hybrid memory systems, i.e., how to place the data on DRAM and NVM for a data-centric algorithm so that it can achieve high performance on hybrid memory. Particularly, we propose an optimal data placement model (ODP) to properly store data structures on DRAM and NVM during the execution of an algorithm. We present the theoretical proof to ODP to ensure the correctness of the model. To demonstrate the efficiency of ODP, we apply the ODP to two kinds of data-centric algorithms, namely sorting and database join. For sorting algorithms, we implement four ODP-based sorting algorithms, including Insertion Sort, Selection Sort, Heapsort, and Merge Sort. For join algorithms, we implement four ODP-based join strategies, including Nested Loops Join, Sort Join, Hash Join, and Virtual Partitioning Join. We conduct comparative experiments to evaluate the performance of the sorting/join algorithms. The results show that the ODP-based sorting/join strategies are much faster than the classical sorting/join algorithms that are not NVM-aware. In addition, the ODP-based implementation can reduce more NVM writes, showing that it is more NVM-friendly.

Flash memory based solid state drives (SSDs) have emerged as a new alternative to replace magnetic disks due to their high performance and low power consumption. However, random writes on SSDs are much slower than SSD reads. Therefore, traditional index structures, which are designed based on the symmetrical I/O property of magnetic disks, cannot completely exert the high performance of SSDs. In this paper, we propose an SSD-optimized linear hashing index called Self-Adaptive Linear Hashing (SALhashing) to reduce small random-writes to SSDs that are caused by index operations. The contributions of our work are manifold. First, we propose to organize the buckets of a linear hashing index into groups and sets to facilitate coarse-grained writes and adaptivity to access patterns. A group consisting of a fixed number of buckets is proposed to transform small random writes to buckets into coarsegrained writes and in turn improve write performance of the index. A set consists of a number of groups, and we propose to employ different split strategies for each set. With this mechanism, SAL-hashing is able to adapt to the changes of access patterns. Second, we attach a log region to each set, and amortize the cost of reads and writes by committing updates to the log region in batch. Third, in order to reduce search cost, each log region is equipped with Bloom filters to index update logs. We devise a cost-based online algorithm to adaptively merge the log region with the corresponding set when the set becomes search-intensive. Fourth, we propose a new technique called virtual split to optimize the search performance of SAL-hashing. Finally, we propose a new scheme for the management of the log buffer. We conduct extensive experiments on real SSDs. The results suggest that our proposal is self-adaptive according to the change of access patterns, and outperforms several competitors under various workloads.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracityproblem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges, since a probabilistic database can have exponential number of possible worlds under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. We study two types of aggregation: convolution and sketch-based, which take polynomial time complexities for aggregation and jointly enable efficient query processing. Also, our proposal is versatile in terms of: 1) its capability of supporting common aggregation functions, i.e., SUM, COUNT, MAX, and AVG; 2) its adaptivity to different materialization strategies, e.g., full versus partial materialization, with support of our devised cost models and parallelization framework; 3) its coverage of common OLAP operations, i.e., probabilistic slicing and dicing queries. Extensive experiments over real and synthetic datasets show that our techniques are effective and scalable.

Company acquisition relation reflects a company's development intent and competitive strategies, which is an important type of enterprise competitive intelligence. In the traditional environment, the acquisition of competitive intelligence mainly relies on newspapers, internal reports, and so on, but the rapid development of the Web introduces a new way to extract company acquisition relation. In this paper, the authors study the problem of extracting company acquisition relation from huge amounts of Web pages, and propose a novel algorithm for company acquisition relation extraction. The authors' algorithm considers the tense feature of Web content and classification technology of semantic strength when extracting company acquisition relation from Web pages. It first determines the tense of each sentence in a Web page, which is then applied in sentences classification so as to evaluate the semantic strength of the candidate sentences in describing company acquisition relation. After that, the authors rank the candidate acquisition relations and return the top-k company acquisition relation. They run experiments on 6144 pages crawled through Google, and measure the performance of their algorithm under different metrics. The experimental results show that the algorithm is effective in determining the tense of sentences as well as the company acquisition relation.

change memory (PCM) as a newly developed storage medium has many attractive properties such as non-volatility, byte addressability, high density and low energy consumption. Thus, PCM can be used to build non-volatile main memory databases. However, PCM's long write latency and high write energy bring challenges to PCM-based memory systems. In this paper, we propose an improvement over the B+-tree for PCM. Particularly, we consider the read/write tendency of leaf nodes. For write-intensive leaf nodes, we use an overflow-node technique to reduce PCM writes, while for read-intensive ones, we adjust the tree structure to remove overflow nodes to improve read performance. Our experimental results suggest that our proposal outperforms the traditional B+-tree and the overflow B+-tree.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracity problem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges as even simple operations are #P-hard under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM and COUNT, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. For aggregation, we focus on how to maximize the sharing of computation among cells and cuboids. We present two aggregation methods: convolution and sketch-based. The two methods scale down the time complexities of building a probabilistic cuboid to polynomial and linear, respectively. Each of the two supports both full and partial data cube materialization. Then, we devise a cost model which guides the aggregation methods to be deployed and combined during the cube materialization. We further provide algorithms for probabilistic slicing and dicing queries on the data cube. Extensive experiments over real and synthetic datasets are conducted to show that the techniques are effective and scalable.

We study safe zones for service subscriptions in a volunteered geographic service setting, covering the concepts, properties, and algorithms needed for the use of weighted imprecise Voronoi cells as safe zones. Empirical performance studies on both synthetic and real datasets offer insights into the efficiency and scalability of our proposal. For a comprehensive coverage, see the full version of the paper.

Flash memory based solid state drives (SSDs) have emerged as a new alternative to replace magnetic disks due to their high performance and low power consumption. However, random writes on SSDs are much slower than SSD reads. Therefore, traditional index structures, which are designed based on the symmetrical I/O property of magnetic disks, cannot completely exert the high performance of SSDs. In this paper, we propose an SSD-optimized linear hashing index called Self-Adaptive Linear Hashing (SAL-Hashing) to reduce small random writes to SSDs that are caused by index operations. The contributions of our work are manifold. First, we propose to organize buckets into groups and sets to facilitate coarse-grained writes and lazy-split so as to avoid intermediate writes on the hash structure. A group consists of a fixed number of buckets and a set consists of a number of groups. Second, we attach a log region to each set, and amortize the cost of reads and writes by committing updates to the log region in batch. Third, in order to reduce search cost, each log region is equipped with Bloom filters to index update logs. We devise a cost-based online algorithm to adaptively merge the log region with the corresponding set when the set becomes search-intensive. Finally, in order to exploit the internal package-level parallelisms of SSDs, we apply coarse-grained writes for merging or split operations to achieve a high bandwidth. Our experimental results suggest that our proposal is self-adaptive according to the change of access patterns, and outperforms several competitors under various workloads on two commodity SSDs.

We provide techniques that enable a scalable so-called Volunteered Geographic Services system. This system targets the increasing populations of online mobile users, e.g., smartphone users, enabling such users to provide location-based services to each other, thus enabling citizen reporter or citizen as a sensor scenarios. More specifically, the system allows users to register as service volunteers, or micro-service providers, by accepting service descriptions and periodically updated locations from such volunteers; and the system allows users to subscribe to notifications of available, nearby relevant services by accepting subscriptions, formalized as continuous queries, that take service preferences and user locations as arguments and return relevant services. Services are ranked according to their relevance and distance to a query, and the highest ranked services are returned. The key challenge addressed is that of scalably providing up-to-date results to queries when the query locations change continuously. This is achieved by the proposal of a new so-called safe-zone model. With safe zones, query results are accompanied by safe zones with the property that a query result remains the same for all locations in its safe zone. Then, query users need only notify the system when they exit their current safe zone. Existing safe-zone models fall short in the papers setting. The new model is enabled by (i) weighted and (ii) set weighted imprecise Voronoi cells. The paper covers underlying concepts, properties, and algorithms, and it covers applications in VGS tracking and presents findings of empirical performance studies.

Indoor moving objects management has been a research focus in recent years. In order to get the trajectory data of indoor moving objects, people have to deploy a lot of positioning equipment, such as RFID readers and tags, which takes lots of money, time, and other costs. In addition, it is a very complex and costly process to construct different environment settings for various indoor applications. Aiming to provide experimental trajectory data for various indoor operations and mining algorithms, in this paper we present a flexible tool to generate trajectories for indoor moving objects, which is named IndoorSTG (Indoor Spatiotemporal Trajectory Generator). IndoorSTG can simulate different indoor environments using various elements including rooms, doors, corridors, stairs, elevators, and virtual positioning devices such as RFID or Bluetooth readers. Meanwhile, it can generate semantic-based trajectories for indoor moving objects in a specific indoor space. After an overview of the general features of IndoorSTG, we discuss the architecture and implementation of IndoorSTG. And finally, a case study of IndoorSTG's demonstration is presented.

Most Web pages contain temporal information, which can be utilized by search engines to improve searching performance for users. However, traditional search engines have little support in processing temporal-textual Web queries. Aiming at solving this problem, in this paper we present and implement a prototype system for time-sensitive queries, which is called TASE (Time-Aware Search Engine). TASE extracts both the explicit and implicit temporal expressions for each Web page, and calculates the relevant score between the Web page and each temporal expression, and then re-rank search results based on the temporal-textual relevance between Web pages and the queries. It is demonstrated that TASE can improve the effectiveness of temporal-textual Web queries.

Flash disks have become a popular alternative for magnetic disks, due to their fast I/O speed and other features such as small-size, shock-resistance, energy-efficient and non-volatile. However, flash disks also have characteristics of out-of-place update and asymmetric I/O latencies for read, write, and erase operations, which introduce new challenges into the indexing mechanism for flash disks. Traditional index structures do not take the flash I/O characteristics into account and, therefore, will cause poor performance. To address this problem, we present a new hybrid index structure for flash disks in this paper, which is called HashTree. HashTree aims at getting better update performance while keeping relatively high search efficiency. The HashTree uses a hash-based index to split the indexed records into several buckets, and then we develop a new tree structure named FTree to organize the records in each bucket. Compared with the previous tree-based indexes, our policy can reduce the costs of maintaining the hierarchical tree structure. We also introduce a tuning mechanism into the HashTree so that we can obtain appropriate trade-off between search performance and update performance. We conducted an experiment on a commercial SSD to evaluate the performance of HashTree. Compared with its competitors such as BFTL and FD-tree, our experimental results show that HashTree performs best in terms of both update performance and overall performance.

In this paper, we present a flexible simulation environment for the performance evaluation of flash-aware algorithms, which is called Flash-DBSim. The main purpose of Flash-DBSim is to provide a configurable virtual flash disk for upper systems, such as file system and DBMS, so that the algorithms in those systems can be easily evaluated on different types of flash disks. Moreover, it also offers a prototyping environment for those algorithms inside flash disk, e.g. the algorithms for garbage collection or wear-leveling. After an overview of the general features of Flash-DBSim, we discuss the architecture of Flash-DBSim. And finally, a case study of Flash-DBSim's demonstration is presented.

Flash disks are becoming an important alternative to conventional magnetic disks. Although accessed through the same interface by applications, flash disks have some distinguished characteristics that make it necessary to reconsider the design of the software to leverage their performance potential. This paper addresses this problem at the buffer management layer of database systems and proposes a flash-aware replacement policy that significantly improves and outperforms one of the previous proposals in this area.

In this paper, we present a CASE tool supporting conceptual modeling for moving objects database applications, which is called STXER (spatio-temporal extended entity-relational model). The main purpose of STXER is to support the database design for moving objects applications on typical object-relational DBMS. The STXER tool enhances the traditional ER model with moving characteristics. It can express rich spatiotemporal semantics for moving objects applications. After an overview of the general features of STXER, we discuss the architecture of STXER. And finally, a case study of STXER's demonstration is presented.