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.
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.
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.
35412477
Processing partially specified queries over high-dimensional databases
In recent years, high-dimensional database applications deal with multidimensional ad hoc queries that refer to an arbitrary number of arbitrarily (unpredictably) chosen dimensions of high-dimensional data. This paper thoroughly and systematically investigates possible secondary-storage based solutions to the problems of processing multidimensional ad hoc query in transactional or semi-transactional environments. Then a complementary solution called the indexed and transposed access method (ITAM) is proposed. This method is based on two complementary measures - a multidimensional access method and a proposed access method called the Opus-path. The performance of multidimensional access methods deteriorates rapidly as the ratio of query dimensionality to data dimensionality decreases. On the other hand, the Opus-path shows retrieval performance that is actually better when the ratio is low.
15548673
Adaptive Query Processing in Point-Transformation Schemes
Point-transformation schemes transform multidimensional points to one-dimensional values so that conventional access methods can be used to index multidimensional points, enabling convenient integration of multidimensional query facilities into complex transactional database management systems. However, in high-dimensional data spaces, the computational complexity of the required query transformation is prohibitive. This paper proposes a near-optimal solution based on our novel ideas of adaptive Z-ordering. The experimental results show that the proposed approach significantly improves the query performance of point-transformation schemes. The idea can easily be generalized to accommodate any hierarchical space-filling curve, not just the Z-curve.
12078838
Scalable and reliable data delivery in mobile ad hoc sensor networks
This paper studies scalable data delivery algorithms in mobile ad hoc sensor networks with node and link failures. Many algorithms have been developed for data delivery and fusion in static microsensor networks, but most of them are not appropriate for mobile sensor networks due to their heavy traffic and long latency. In this paper we propose an efficient and robust data delivery algorithm for distributed data fusion in mobile ad hoc sensor networks, where each node controls its data flows and learns routing decisions solely based on their local knowledge. We analyze the localized algorithm in a formal model and validate our model using simulations. The experiments indicate that controlled data delivery processes significantly increase the probability of relevant data being fused in the network even with limited local knowledge of each node and relatively small hops of data delivery.
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.
14231097
Distributed Reputation Management for Electronic Commerce
One of the major challenges for electronic commerce is how to establish a relationship of trust between different parties. Establishing trust is nontrivial, because the traditional physical or social means of trust cannot apply directly in virtual settings. In many cases, the parties involved may not ever have interacted before. Reputation systems seek to address the development of trust by recording the reputations of different parties. However, most existing reputation systems are restricted to individual market websites. Further, relevant information about a party may come from several websites and from interactions that were not mediated by any website. 
 
 
 
This paper considers the problem of automatically collecting ratings about a given party from others. Our approach involves a distributed agent architecture and adapts the mathematical theory of evidence to represent and propagate the ratings that participants give to each other. When evaluating the trustworthiness of a given party, a peer combines its local evidence (based on direct prior interactions with the party) with the testimonies of others regarding the same party. This approach satisfies certain important properties of distributed reputation management and is experimentally evaluated through simulations.
10794980
Searching social networks
A referral system is a multiagent system whose member agents are capable of giving and following referrals. The specific cases of interest arise where each agent has a user. The agents cooperate by giving and taking referrals so each can better help its user locate relevant information. This use of referrals mimics human interactions and can potentially lead to greater effectiveness and efficiency than in single-agent systems.Existing approaches consider what referrals may be given and treat the referring process simply as path search in a static graph. By contrast, the present approach understands referrals as arising in and influencing dynamic social networks, where the agents act autonomously based on local knowledge. This paper studies strategies using which agents may search dynamic social networks. It evaluates the proposed approach empirically for a community of AI scientists (partially derived from bibliographic data). Further, it presents a prototype system that assists users in finding other users in practical social networks.
11368829
Video summarization based on user log enhanced link analysis
Efficient video data management calls for intelligent video summarization tools that automatically generate concise video summaries for fast skimming and browsing. Traditional video summarization techniques are based on low-level feature analysis, which generally fails to capture the semantics of video content. Our vision is that users unintentionally embed their understanding of the video content in their interaction with computers. This valuable knowledge, which is difficult for computers to learn autonomously, can be utilized for video summarization process. In this paper, we present an intelligent video browsing and summarization system that utilizes previous viewers' browsing log to facilitate future viewers. Specifically, a novel ShotRank notion is proposed as a measure of the subjective interestingness and importance of each video shot. A ShotRank computation framework is constructed to seamlessly unify low-level video analysis and user browsing log mining. The resulting ShotRank is used to organize the presentation of video shots and generate video skims. Experimental results from user studies have strongly confirmed that ShotRank indeed represents the subjective notion of interestingness and importance of each video shot, and it significantly improves future viewers' browsing experience.