The reverse top-k query was proposed for market analysis over ten years ago. The query identifies users’ preferences whose top-k choices include a given object o. Users’ preferences are considered static in the traditional reverse top-k query. However, preferences change over time due to factors like mood, seasons, and economic conditions. In this paper, to address the dynamic nature of preference in market analysis, a new query, called the Durable Impact Period Query, is proposed. Taking a query object o and a time period I as inputs, the durable impact period query aims to determine whether I is a durable impact period of o. This involves checking whether, for most of the time in I, more than a certain proportion of users include o in their top-k choices. The impact period serves as a critical determinant in the decision-making process for product launches. To process durable impact period queries efficiently, three algorithms are proposed. First, an exhaustive search algorithm is designed. Then, by transforming the durable impact period query into the halfspace range thresholding query, a pruning-based algorithm is proposed. Notably, the pruning-based algorithm demonstrates a significant reduction in time cost, often by two orders of magnitude compared with the exhaustive search algorithm. Moreover, a sampling-based approximate algorithm is presented to further enhance efficiency. Finally, extensive experiments show that the proposed algorithms are correct and efficient.

With the widespread deployment of indoor positioning systems, an unprecedented scale of indoor trajectories is being produced. By considering the inherent uncertainties and the text information contained in such an indoor trajectory, a new definition named Indoor Uncertain Semantic Trajectory is defined in this paper. In this paper, we focus on a new primitive, yet quite essential query named Indoor Uncertain Semantic Trajectory Similarity Join (IUST-Join for short), which is to match all similar pairs of indoor uncertain semantic trajectories from two sets. IUST-Join targets a number of essential indoor applications. With these applications in mind, we provide a purposeful definition of an indoor uncertain semantic trajectory similarity metric named IUS. To process IUST-Join more efficiently, both an inverted index on indoor uncertain semantic trajectories named 3IST and the first acceleration strategy are proposed to form a filtering-and-verification framework, where most invalid pairs of indoor uncertain semantic trajectories are pruned at quite low computation cost. And based on this filtering-and-verification framework, we present a highly-efficient algorithm named Indoor Uncertain Semantic Trajectory Similarity Join Processing (USP for short). In addition, lots of novel and effective acceleration strategies are proposed and embedded in the USP algorithm. Thanks to these techniques, both the time complexity and the time overhead of the USP algorithm are further reduced. The results of extensive experiments demonstrate the superior performance of the proposed work.

Kernel is a kind of data summary which is elaborately extracted from a large dataset. Given a problem, the solution obtained from the kernel is an approximate version of the solution obtained from the whole dataset with a provable approximate ratio. It is widely used in geometric optimization, clustering, and approximate query processing, etc., for scaling them up to massive data. In this paper, we focus on the minimum ε-kernel (MK) computation that asks for a kernel of the smallest size for large-scale data processing. For the open problem presented by Wang et al. that whether the minimum ε-coreset (MC) problem and the MK problem can be reduced to each other, we first formalize the MK problem and analyze its complexity. Due to the NP-hardness of the MK problem in three or higher dimensions, an approximate algorithm, namely Set Cover-Based Minimum ε-Kernel algorithm (SCMK), is developed to solve it. We prove that the MC problem and the MK problem can be Turing-reduced to each other. Then, we discuss the update of MK under insertion and deletion operations, respectively. Finally, a randomized algorithm, called the Randomized Algorithm of Set Cover-Based Minimum ε-Kernel algorithm (RA-SCMK), is utilized to further reduce the complexity of SCMK. The efficiency and effectiveness of SCMK and RA-SCMK are verified by experimental results on real-world and synthetic datasets. Experiments show that the kernel sizes of SCMK are 2x and 17.6x smaller than those of an ANN-based method on real-world and synthetic datasets, respectively. The speedup ratio of SCMK over the ANN-based method is 5.67 on synthetic datasets. RA-SCMK runs up to three times faster than SCMK on synthetic datasets.

Array partitioning is an important research problem in array management area, since the partitioning strategies have important influence on storage, query evaluation, and other components in array management systems. Meanwhile, compression is highly needed for the array data due to its growing volume. Observing that array partitioning can affect the compression performance significantly, this paper aims to design an efficient partitioning method for array data to optimize the compression performance. As far as we know, there still lacks research efforts on this problem. In this paper, the problem of array partitioning for optimizing the compression performance (PPCP for short) is firstly proposed. We adopt a popular compression technique which allows to process queries on the compressed data without decompression. Secondly, because the above problem is NP-hard, two essential principles for exploring the partitioning solution are introduced, which can explain the core idea of the partitioning algorithms proposed by us. The first principle shows that the compression performance can be improved if an array can be partitioned into two parts with different sparsities. The second principle introduces a greedy strategy which can well support the selection of the partitioning positions heuristically. Supported by the two principles, two greedy strategy based array partitioning algorithms are designed for the independent case and the dependent case respectively. Observing the expensive cost of the algorithm for the dependent case, a further optimization based on random sampling and dimension grouping is proposed to achieve linear time cost. Finally, the experiments are conducted on both synthetic and real-life data, and the results show that the two proposed partitioning algorithms achieve better performance on both compression and query evaluation.

Current Conditional Functional Dependency (CFD) discovery algorithms always need a well-prepared training dataset. This condition makes them difficult to apply on large and low-quality datasets. To handle the volume issue of big data, we develop the sampling algorithms to obtain a small representative training set. We design the fault-tolerant rule discovery and conflict-resolution algorithms to address the low-quality issue of big data. We also propose parameter selection strategy to ensure the effectiveness of CFD discovery algorithms. Experimental results demonstrate that our method can discover effective CFD rules on billion-tuple data within a reasonable period.

Incomplete data has been a longstanding issue in the database community, and the subject is yet poorly handled by both theories and practices. One common way to cope with missing values is to complete their imputation (filling in) as a preprocessing step before analyses. Unfortunately, not a single imputation method could impute all missing values correctly in all cases. Users could hardly trust the query result on such complete data without any confidence guarantee. In this paper, we propose to directly estimate the aggregate query result on incomplete data, rather than to impute the missing values. An interval estimation, composed of the upper and the lower bound of aggregate query results among all possible interpretations of missing values, is presented to the end users. The ground-truth aggregate result is guaranteed to be among the interval. We believe that decision support applications could benefit significantly from the estimation, since they can tolerate inexact answers, as long as there are clearly defined semantics and guarantees associated with the results. Our main techniques are parameter-free and do not assume prior knowledge about the distribution and missingness mechanisms. Experimental results are consistent with the theoretical results and suggest that the estimation is invaluable to better assess the results of aggregate queries on incomplete data.

Time intervals are often associated with tuples to represent their valid time in temporal relations, where overlap join is crucial for various kinds of queries. Many existing overlap join algorithms use indices based on tree structures such as quad-tree, B⁺-tree and interval tree. These algorithms usually have high CPU cost since deep path traversals are unavoidable, which makes them not so competitive as data-partition or plane-sweep based algorithms. This paper proposes an efficient overlap join algorithm based on a new two-layer flat index named as Overlap Interval Inverted Index (i.e., O2i Index). It uses an array to record the end points of intervals and approximates the nesting structures of intervals via two functions in the first layer, and the second layer uses inverted lists to trace all intervals satisfying the approximated nesting structures. With the help of the new index, the join algorithm only visits the must-be-scanned lists and skips all others. Analyses and experiments on both real and synthetic datasets show that the proposed algorithm is as competitive as the state-of-the-art algorithms.

An Energy-Harvesting Wireless Sensor Network (EH-WSN) depends on harvesting energy from theenvironment to prolong network lifetime. Subjected to limited energy in complex environments, an EH-WSN encounters difficulty when applied to real environments as the network efficiency is reduced. Existing EH-WSN studies are usually conducted in assumed conditions in which nodes are synchronized and the energy profile is knowable or calculable. In real environments, nodes may lose their synchronization due to lack of energy. Furthermore, energy harvesting is significantly affected by multiple factors, whereas the ideal hypothesis is difficult to achieve in reality. In this paper, we introduce a general Intermittent Energy-Aware (IEA) EH-WSN platform. For the first time, we adopted a double-stage capacitor structure to ensure node synchronization in situations without energy harvesting, and we used an integrator to achieve ultra-low power measurement. With regard to hardware and software, we provided an optimized energy management mechanism for intermittent functioning. This paper describes the overall design of the IEA platform, and elaborates the energy management mechanism from the aspects of energy management, energy measurement, and energy prediction. In addition, we achieved node synchronization in different time and energy environments, measured the energy in reality, and proposed the light weight energy calculation method based on measured solar energy. In real environments, experiments are performed to verify the high performance of IEA in terms of validity and reliability. The IEA platform is shown to have ultra-low power consumption and high accuracy for energy measurement and prediction.

In this era of big data, data are often collected from multiple sources that have different reliabilities, and there is inevitable conflict with respect to the various information obtained when it relates to the the same object. One important task is to identify the most trustworthy value out of all the conflicting claims, and this is known as truth discovery. Existing truth discovery methods simultaneously identify the most trustworthy information and source reliability degrees and are based on the idea that more reliable sources often provide more trustworthy information, and vice versa. However, there are often semantic constrains defined upon relational database, which can be violated by a single data source. To remove violations, an important task is to repair data to satisfy the constrains, and this is known as data cleaning. The two problems above may coexist, but considering them together can provide some benefits, and to the authors knowledge, this has not yet been the focus of any research. In this paper, therefore, a schema-decomposing based method is proposed to simultaneously discover the truth and to clean the data, with the aim of improving accuracy. Experimental results using real world data sets of notebooks and mobile phones, as well as simulated data sets, demonstrate the effectiveness and efficiency of our proposed method.