33239543
Implementing KDB-trees to support high-dimensional data
The problem of retrieving large volumes of high dimensional data is an important and timely issue in the area of database management. The guiding idea of the paper is to develop a general-purpose point access method that attacks the limitations of KDB-trees in high-dimensional spaces, while preserving their relatively good performance in low-dimensional situations. The proposed structure, called high-dimensional KDB-tree, eliminates downward propagation of splits associated with the original KDB-tree structure, which results in low storage utilization and rapid deterioration of the retrieval performance. Additional improvements in the storage and retrieval performance are achieved by removing certain redundant information from the interior nodes. Experimental results show that, in high-dimensional spaces, the proposed structure outperforms the original KDB-trees by a significant margin, while incurring no loss of performance in low-dimensional spaces. The structure also outperforms two other variants of KDB-trees investigated in the paper.
12972206
Interpolating and Using Most Likely Trajectories in Moving-Objects Databases
In recent years, many emerging database applications deal with large sets of continuously moving data objects. Since no computer system can commit continuously occurring infinitesimal changes to the database, related data management techniques view a moving object's trajectory as a sequence of discretely reported spatiotemporal points. For each pair of consecutive committed trajectory points, a spatiotemporal uncertainty region representing all possible in-between trajectory points is defined. To support trajectory queries with a non-uniform probability distribution model, the query system needs to compute (interpolate) the “most likely” trajectories in the uncertainty regions to determine the peak points of the probability distributions. This paper proposes a generalized trajectory interpolation model using parametric trajectory representations. In addition, the paper expands and investigates three practical specializations of our proposed model using a moving object with momentum, i.e., a vehicle, as the exemplar.
41617522
Validation-based reprocessing scheme for updating spatial data in mobile computing environments
This paper introduces a novel reprocessing-transaction model that handles the update conflicts between mobile transactions without abortion. The proposed model executes a new subtransaction, called a reprocessing transaction, which reupdates only conflicted objects using foreign conflicted objects. We also propose a progressive reprocessing scheme to allow the non-conflicted objects of a mobile transaction to be incrementally exposed to other concurrent transactions in order to alleviate starvation of reprocessing transactions.
10366637
Inverted-space storage organization for persistent data of very high dimensionality
Contemporary database technology is severely limited in managing the high-dimensional data of many advanced applications, such as multimedia systems and data mining. The main concern of this paper is the well-known performance degradation of multi-dimensional access methods in spaces with many dimensions. The paper proposes an elaborate storage organization, called the inverted space, which can support efficient processing of data in spaces with very high dimensionality. The organization allows system administrators to control the size of spatial indexes and thereby to avoid the negative impact of extremely high data dimensionality on the retrieval performance. In addition, this paper introduces a new point access method designed to address numerous other problems that contemporary retrieval schemes experience in high-dimensional situations. This mechanism is envisioned to serve as the core indexing structure of inverted-space storage organizations.
7968424
Curve-based representation of moving object trajectories
In recent years, many emerging database applications deal with continuously moving data objects - each data object moves continuously and frequently reports its current location, moving direction, and speed to the database server. A database server for these applications keeps track of the trajectories of individual moving objects and processes queries referring to the past or future trajectories. Related techniques view a moving object trajectory as a sequence of connected line segments. However, most natural moving objects, such as airplanes, vessels, and vehicles, draw a smooth trajectory with no angles. This paper presents our curve-based trajectory representation models. The presented results show that the curve-based models provide much more accurate trajectories than the line-based models when we have the same amount of data (same number of reported points). In other words, the curve-based models require a smaller amount of data while providing the same accuracy in trajectory representation.
9205595
A spatiotemporal uncertainty model of degree 1.5 for continuously changing data objects
To support emerging database applications that deal with continuously changing (or moving) data objects (CCDO), one requires an efficient data management system that can store, update, and retrieve large sets of CCDOs. Although actual CCDOs can continuously change, computer systems cannot deal with continuously occurring infinitesimal changes. Thus, in the data management system, each object's spatiotemporal values are always associated with a certain degree of uncertainty at every point in time, and the queries are mostly processed over estimates characterizing the uncertainty. Unfortunately, there is a marked lack of formal explication of the uncertainty of multidimensional CCDOs in space-time. This paper presents our logical and mathematical bases for capturing, representing, and processing CCDOs of varying dimensionality.
25386929
Spatially adaptive wavelet thresholding with context modeling for image denoising
The method of wavelet thresholding for removing noise, or denoising, has been researched extensively due to its effectiveness and simplicity. Much of the literature has focused on developing the best uniform threshold or best basis selection. However, not much has been done to make the threshold values adaptive to the spatially changing statistics of images. Such adaptivity can improve the wavelet thresholding performance because it allows additional local information of the image (such as the identification of smooth or edge regions) to be incorporated into the algorithm. This work proposes a spatially adaptive wavelet thresholding method based on context modeling, a common technique used in image compression to adapt the coder to changing image characteristics. Each wavelet coefficient is modeled as a random variable of a generalized Gaussian distribution with an unknown parameter. Context modeling is used to estimate the parameter for each coefficient, which is then used to adapt the thresholding strategy. This spatially adaptive thresholding is extended to the overcomplete wavelet expansion, which yields better results than the orthogonal transform. Experimental results show that spatially adaptive wavelet thresholding yields significantly superior image quality and lower MSE than the best uniform thresholding with the original image assumed known.
39243731
A rate of convergence result for a universal D-semifaithful code
The problem of optimal rate universal coding is considered in the context of rate-distortion theory. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to approach its lower bound, the rate-distortion function, at a rate O(n/sup -1/log n), and this is conjectured to be optimal based on a result of A.J. Pilc (1968). Issues of constructiveness and universality are addressed. >
12479973
Adaptive wavelet thresholding for image denoising and compression
The first part of this paper proposes an adaptive, data-driven threshold for image denoising via wavelet soft-thresholding. The threshold is derived in a Bayesian framework, and the prior used on the wavelet coefficients is the generalized Gaussian distribution (GGD) widely used in image processing applications. The proposed threshold is simple and closed-form, and it is adaptive to each subband because it depends on data-driven estimates of the parameters. Experimental results show that the proposed method, called BayesShrink, is typically within 5% of the MSE of the best soft-thresholding benchmark with the image assumed known. It also outperforms SureShrink (Donoho and Johnstone 1994, 1995; Donoho 1995) most of the time. The second part of the paper attempts to further validate claims that lossy compression can be used for denoising. The BayesShrink threshold can aid in the parameter selection of a coder designed with the intention of denoising, and thus achieving simultaneous denoising and compression. Specifically, the zero-zone in the quantization step of compression is analogous to the threshold value in the thresholding function. The remaining coder design parameters are chosen based on a criterion derived from Rissanen's minimum description length (MDL) principle. Experiments show that this compression method does indeed remove noise significantly, especially for large noise power. However, it introduces quantization noise and should be used only if bitrate were an additional concern to denoising.
2174351
On Model Selection Consistency of Lasso
Sparsity or parsimony of statistical models is crucial for their proper interpretations, as in sciences and social sciences. Model selection is a commonly used method to find such models, but usually involves a computationally heavy combinatorial search. Lasso (Tibshirani, 1996) is now being used as a computationally feasible alternative to model selection. Therefore it is important to study Lasso for model selection purposes. 
 
In this paper, we prove that a single condition, which we call the Irrepresentable Condition, is almost necessary and sufficient for Lasso to select the true model both in the classical fixed p setting and in the large p setting as the sample size n gets large. Based on these results, sufficient conditions that are verifiable in practice are given to relate to previous works and help applications of Lasso for feature selection and sparse representation. 
 
This Irrepresentable Condition, which depends mainly on the covariance of the predictor variables, states that Lasso selects the true model consistently if and (almost) only if the predictors that are not in the true model are "irrepresentable" (in a sense to be clarified) by predictors that are in the true model. Furthermore, simulations are carried out to provide insights and understanding of this result.
15189341
Wavelet thresholding for multiple noisy image copies
This correspondence addresses the recovery of an image from its multiple noisy copies. The standard method is to compute the weighted average of these copies. Since the wavelet thresholding technique has been shown to effectively denoise a single noisy copy, we consider in this paper combining the two operations of averaging and thresholding. Because thresholding is a nonlinear technique, averaging then thresholding or thresholding then averaging produce different estimators. By modeling the signal wavelet coefficients as Laplacian distributed and the noise as Gaussian, our investigation finds the optimal ordering to depend on the number of available copies and on the signal-to-noise ratio. We then propose thresholds that are nearly optimal under the assumed model for each ordering. With the optimal and near-optimal thresholds, the two methods yield similar performance, and both show considerable improvement over merely averaging.