共查询到20条相似文献,搜索用时 46 毫秒
1.
Nearest Neighbor (NN) search has been in the core of spatial and spatiotemporal database research during the last decade.
The literature on NN query processing algorithms so far deals with either stationary or moving query points over static datasets
or future (predicted) locations over a set of continuously moving points. With the increasing number of Mobile Location Services
(MLS), the need for effective k-NN query processing over historical trajectory data has become the vehicle for data analysis, thus improving existing or
even proposing new services. In this paper, we investigate mechanisms to perform NN search on R-tree-like structures storing
historical information about moving object trajectories. The proposed (depth-first and best-first) algorithms vary with respect
to the type of the query object (stationary or moving point) as well as the type of the query result (historical continuous
or not), thus resulting in four types of NN queries. We also propose novel metrics to support our search ordering and pruning
strategies. Using the implementation of the proposed algorithms on two members of the R-tree family for trajectory data (namely,
the TB-tree and the 3D-R-tree), we demonstrate their scalability and efficiency through an extensive experimental study using
large synthetic and real datasets.
相似文献
2.
Continuous Range (CR) query and Continuous K-Nearest Neighbor (C KNN) query are two important types of spatio-temporal queries. Given a time interval [ t
s
, t
e
] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [ t
s
, t
e
]. A C KNN query is to retrieve the K-Nearest Neighbors ( KNNs) of this query object q at each time instant within [ t
s
, t
e
]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity
of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing
spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely
the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the C KNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being
the result of a CR query or a C KNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches. 相似文献
3.
We propose a SAO index to approximately answer arbitrary linear optimization queries in a sliding window of a data stream.
It uses limited memory to maintain the most “important” tuples. At any time, for any linear optimization query, we can retrieve
the approximate top- K tuples in the sliding window almost instantly. The larger the amount of available memory, the better the quality of the answers
is. More importantly, for a given amount of memory, the quality of the answers can be further improved by dynamically allocating
a larger portion of the memory to the outer layers of the SAO index.
相似文献
4.
With the rapid advancements in positioning technologies such as the Global Positioning System (GPS) and wireless communications,
the tracking of continuously moving objects has become more convenient. However, this development poses new challenges to
database technology since maintaining up-to-date information regarding the location of moving objects incurs an enormous amount
of updates. Existing indexes can no longer keep up with the high update rate while providing speedy retrieval at the same
time. This study aims to improve k nearest neighbor (kNN) query performance while reducing update costs. Our approach is based
on an important observation that queries usually occur around certain places or spatial landmarks of interest, called reference
points. We propose the Reference-Point-based tree (RP-tree), which is a two-layer index structure that indexes moving objects
according to reference points. Experimental results show that the RP-tree achieves significant improvement over the TPR-tree.
相似文献
5.
Twig query pattern matching is a core operation in XML query processing. Indexing XML documents for twig query processing
is of fundamental importance to supporting effective information retrieval. In practice, many XML documents on the web are
heterogeneous and have their own formats; documents describing relevant information can possess different structures. Therefore
some “user-interesting” documents having similar but non-exact structures against a user query are often missed out. In this
paper, we propose the RRSi, a novel structural index designed for structure-based query lookup on heterogeneous sources of XML documents supporting
proximate query answers. The index avoids the unnecessary processing of structurally irrelevant candidates that might show
good content relevance. An optimized version of the index, oRRSi, is also developed to further reduce both space requirements and computational complexity. To our knowledge, these structural
indexes are the first to support proximity twig queries on XML documents. The results of our preliminary experiments show
that RRSi and oRRSi based query processing significantly outperform previously proposed techniques in XML repositories with structural heterogeneity.
相似文献
6.
This paper deals with just in time control of ( max,+)-linear systems. The output tracking problem, considered in previous studies, is generalized by considering additional
constraints in the control objective. The problem is formulated as an extremal fixed point computation. This control is applied
to timetables computation for urban bus networks.
相似文献
7.
We present an enhancement towards adaptive video training for PhoneGuide, a digital museum guidance system for ordinary camera-equipped
mobile phones. It enables museum visitors to identify exhibits by capturing photos of them. In this article, a combined solution
of object recognition and pervasive tracking is extended to a client–server-system for improving data acquisition and for
supporting scale-invariant object recognition. A static as well as a dynamic training technique are presented that preprocess
the collected object data differently and apply two types of neural networks (NN) for classification. Furthermore, the system
enables a temporal adaptation for ensuring a continuous data acquisition to improve the recognition rate over time. A formal
field experiment reveals current recognition rates and indicates the practicability of both methods under realistic conditions
in a museum.
相似文献
8.
Frequent pattern mining on data streams is of interest recently. However, it is not easy for users to determine a proper frequency
threshold. It is more reasonable to ask users to set a bound on the result size. We study the problem of mining top K frequent itemsets in data streams. We introduce a method based on the Chernoff bound with a guarantee of the output quality
and also a bound on the memory usage. We also propose an algorithm based on the Lossy Counting Algorithm. In most of the experiments
of the two proposed algorithms, we obtain perfect solutions and the memory space occupied by our algorithms is very small.
Besides, we also propose the adapted approach of these two algorithms in order to handle the case when we are interested in
mining the data in a sliding window. The experiments show that the results are accurate.
相似文献
9.
In this paper, a hybrid genetic approach is proposed to solve the problem of designing a subdatabase of the original one with
the highest classification performances, the lowest number of features and the highest number of patterns. The method can
simultaneously treat the double problem of editing instance patterns and selecting features as a single optimization problem,
and therefore aims at providing a better level of information. The search is optimized by dividing the algorithm into self-controlled
phases managed by a combination of pure genetic process and dedicated local approaches. Different heuristics such as an adapted
chromosome structure and evolutionary memory are introduced to promote diversity and elitism in the genetic population. They
particularly facilitate the resolution of real applications in the chemometric field presenting databases with large feature
sizes and medium cardinalities. The study focuses on the double objective of enhancing the reliability of results while reducing
the time consumed by combining genetic exploration and a local approach in such a way that excessive computational CPU costs
are avoided. The usefulness of the method is demonstrated with artificial and real data and its performance is compared to
other approaches.
相似文献
10.
Mining of music data is one of the most important problems in multimedia data mining. In this paper, two research issues of
mining music data, i.e., online mining of music query streams and change detection of music query streams, are discussed.
First, we proposed an efficient online algorithm, FTP-stream ( Frequent Temporal Pattern mining of streams), to mine all frequent melody structures over sliding windows of music melody sequence streams. An effective bit-sequence
representation is used in the proposed algorithm to reduce the time and memory needed to slide the windows. An effective list
structure is developed in the FTP-stream algorithm to overcome the performance bottleneck of 2-candidate generation. Experiments
show that the proposed algorithm FTP-stream only needs a half of memory requirement of original melody sequence data, and
just scans the music query stream once. After mining frequent melody structures, we developed a simple online algorithm, MQS-change
( changes of Music Query Streams), to detect the changes of frequent melody structures in current user-centered music query streams. Two music melody
structures (set of chord-sets and string of chord-sets) are maintained and four melody structure changes (positive burst,
negative burst, increasing change and decreasing change) are monitored in a new summary data structure, MSC-list (a list of Music Structure Changes). Experiments show that the MQS-change algorithm is an effective online method to detect the changes of music melody
structures over continuous music query streams.
相似文献
11.
Dynamically composing services requires mechanisms to ensure component services compatible with each other both at all of
the syntax, semantic and behavioral level. This paper focuses on the issue of behavioral compatibility in a service composition.
It adopts the π-calculus to model service behaviors and interactions in a formal way. Based on the formalization, it proposes a method to
automatically check the behavioral compatibility in a qualitative way. Furthermore, it presents an algorithm to compute the
compatibility degree in a quantitative way. The algorithm is implemented in a prototype and its performance analysis is also
carried out to show that it can help composing services on the fly and ensure the services compatible with each other to provide
functions with newly-added values.
相似文献
12.
Regularized energies with ℓ
1-fitting have attracted a considerable interest in the recent years and numerous aspects of the problem have been studied,
mainly to solve various problems arising in image processing. In this paper we focus on a rather simple form where the regularization
term is a quadratic functional applied on the first-order differences between neighboring pixels. We derive a semi-explicit
expression for the minimizers of this energy which shows that the solution is an affine function in the neighborhood of each
data set. We then describe the volumes of data for which the same system of affine equations leads to the minimum of the relevant
energy. Our analysis involves an intermediate result on random matrices constructed from truncated neighborhood sets. We also
put in evidence some drawbacks due to the ℓ
1-fitting. A fast, simple and exact optimization method is proposed. By way of application, we separate impulse noise from
Gaussian noise in a degraded image.
相似文献
13.
This paper proposes an efficient parallel algorithm for computing Lagrange interpolation on k-ary n-cube networks. This is done using the fact that a k-ary n-cube can be decomposed into n link-disjoint Hamiltonian cycles. Using these n link-disjoint cycles, we interpolate Lagrange polynomial using full bandwidth of the employed network. Communication in the
main phase of the algorithm is based on an all-to-all broadcast algorithm on the n link-disjoint Hamiltonian cycles exploiting all network channels, and thus, resulting in high-efficiency in using network
resources. A performance evaluation of the proposed algorithm reveals an optimum speedup for a typical range of system parameters
used in current state-of-the-art implementations.
相似文献
14.
Various techniques have been developed for different query types in content-based image retrieval systems such as sampling
queries, constrained sampling queries, multiple constrained sampling queries, k-NN queries, constrained k-NN queries, and multiple localized k-NN queries. In this paper, we propose a generalized query model suitable for expressing queries of different types, and investigate
efficient processing techniques for this new framework. We exploit sequential access and data sharing by developing new storage
and query processing techniques to leverage inter-query concurrency. Our experimental results, based on the Corel dataset,
indicate that the proposed optimization can significantly reduce average response time in a multiuser environment, and achieve
better retrieval precision and recall compared to two recent techniques.
相似文献
15.
Continuous K-nearest neighbor (C KNN) query is an important type of spatio-temporal queries. Given a time interval [ ts, te] and a moving query object q, a C KNN query is to find the K-nearest neighbors ( KNNs) of q at each time instant within [ ts, te]. In this paper, we focus on the issue of scalable processing of C KNN queries over moving objects with uncertain velocity. Due to the large amount of C KNN queries that need to be evaluated concurrently, efficiently processing such queries inevitably becomes more complicated. We propose an index structure, namely the CI-tree, to predetermine and organize the candidates for each query issued by the user from anywhere and anytime. When the C KNN queries are evaluated, their corresponding candidates can be rapidly retrieved by traversing the CI-tree so that the processing time is greatly reduced. A comprehensive set of experiments is performed to demonstrate the effectiveness and the efficiency of the CI-tree. 相似文献
16.
In scheduling hard-real-time systems, the primary objective is to meet all deadlines. We study the scheduling of such systems
with the secondary objective of minimizing the duration of time for which the system locks each shared resource. We abstract
out this objective into the resource hold time ( rht)—the largest length of time that may elapse between the instant that a system locks a resource and the instant that it subsequently
releases the resource, and study properties of the rht. We present an algorithm for computing resource hold times for every resource in a task system that is scheduled using Earliest
Deadline First scheduling, with resource access arbitrated using the Stack Resource Policy. We also present and prove the
correctness of algorithms for decreasing these rht’s without changing the semantics of the application or compromising application feasibility.
相似文献
18.
We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed
about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked
on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive,
although they had several important reservations about camera-phone technology more generally. Data from our pointing-device
task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device
trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings,
design lessons for camera-phone and visual-tag applications are presented.
相似文献
19.
Detecting and dealing with redundancy is an ubiquitous problem in query optimization, which manifests itself in many areas
of research such as materialized views, multi-query optimization, and query-containment algorithms. In this paper, we focus
on the issue of intra-query redundancy, redundancy present within a query. We present a method to detect the maximal redundancy present between a main (outer) query block and a subquery block.
We then use the method for query optimization, introducing query plans and a new operator that take full advantage of the
redundancy discovered. Our approach can deal with redundancy in a wider spectrum of queries than existing techniques. We show
experimental evidence that our approach works under certain conditions, and compares favorably to existing optimization techniques
when applicable.
相似文献
20.
This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary
Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition
and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational
intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process,
we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.
相似文献
|