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.
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.
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.
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.
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.
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.
1444182
Detecting deception in reputation management
We previously developed a social mechanism for distributed reputation management, in which an agent combines testimonies from several witnesses to determine its ratings of another agent. However, that approach does not fully protect against spurious ratings generated by malicious agents. This paper focuses on the problem of deception in testimony propagation and aggregation. We introduce some models of deception and study how to efficiently detect deceptive agents following those models. Our approach involves a novel application of the well-known weighted majority technique to belief function and their aggregation. We describe simulation experiments to study the number of apparently accurate witnesses found in different settings, the number of witnesses on prediction accuracy, and the evolution of trust networks.
1366256
Convexity of Minimal Total Dominating Functions in Graphs
A total dominating function (TDF) of a graph G=(V, E) is a function f ∶ V → [0,1] such that for each v ∈ V, the sum of f values over all neighbours of ν (i.e., all vertices adjacent to v) is at least one. Integer-valued TDFs are precisely the characteristic functions of total dominating sets of G. A minimal TDF (MTDF) is one such that decreasing any value of it makes it non-TDF. An MTDF f is called universal if convex combinations of f and any other MTDF are minimal. We give a sufficient condition for an MTDF to be universal which generalizes previous results. Also we define a splitting operation on a graph G as follows: take any vertex ν in G and a vertex ω not in G and join ω with all the neighbours of v. A graph G has a universal MTDF if and only if the graph obtained by splitting G has a universal MTDF. A corollary is that graphs obtained by the operation from paths, cycles, complete graphs, wheels, and caterpillar graphs have a universal MTDF.
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.