共查询到20条相似文献,搜索用时 31 毫秒
1.
Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a "hard" problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor (κ-NN) search in high-dimensional spaces. In CDT, all (n) data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^+-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree. 相似文献
2.
This paper presents an optimized 64-bit parallel adder. Sparse-tree architecture enables low carry-merge fan-outs and inter-stage wiring complexity. Single-rail and semi-dynamic circuit improves operation speed. Simulation results show that the proposed adder can operate at 485ps with power of 25.6mW in 0.18μm CMOS process. It achieves the goal of higher speed and lower power. 相似文献
3.
Continually Answering Constraint <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="Italic">NN</Emphasis> Queries in Unstructured P2P Systems
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Bin Wang Xiao-Chun Yang Guo-Ren Wang Ge Yu Lei Chen X. Sean Wang and Xue-Min Lin 《计算机科学技术学报》2008,23(4):538-556
We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer (P2P) system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle (MBR)-based query approaches, especially for continuous queries. 相似文献
4.
In this paper we introduce a cryptosystem based on the quotient groups of the group of rational points of an elliptic curve defined over p-adic number field. Some additional parameters are taken in this system, which have an advantage in performing point multiplication while keeping the security of ECC over finite fields. We give a method to select generators of the cryptographic groups, and give a way to represent the elements of the quotient groups with finitely bounded storage by establishing a bijection between these elements and their approximate coordinates. The addition formula under this representation is also presented. 相似文献
5.
Given a query workload, a database and a set of constraints, the view-selection problem is to select views to materialize
so that the constraints are satisfied and the views can be used to compute the queries in the workload efficiently. A typical
constraint, which we consider in the present work, is to require that the views can be stored in a given amount of disk space.
Depending on features of SQL queries (e.g., the DISTINCT keyword) and on whether the database relations on which the queries
are applied are sets or bags, the queries may be computed under set semantics, bag-set semantics, or bag semantics. In this
paper we study the complexity of the view-selection problem for conjunctive queries and views under these semantics. We show
that bag semantics is the “easiest to handle” (we show that in this case the decision version of view selection is in NP),
whereas under set and bag-set semantics we assume further restrictions on the query workload (we only allow queries without
self-joins in the workload) to achieve the same complexity. Moreover, while under bag and bag-set semantics filtering views
(i.e., subgoals that can be dropped from the rewriting without impacting equivalence to the query) are practically not needed,
under set semantics filtering views can reduce significantly the query-evaluation costs. We show that under set semantics
the decision version of the view-selection problem remains in NP only if filtering views are not allowed in the rewritings.
Finally, we investigate whether the cgalg algorithm for view selection introduced in Chirkova and Genesereth (Linearly bounded reformulations of conjunctive databases,
pp. 987–1001, 2000) is suitable in our setting. We prove that this algorithm is sound for all cases we examine here, and that
it is complete under bag semantics for workloads of arbitrary conjunctive queries and under bag-set semantics for workloads
of conjunctive queries without self-joins.
Rada Chirkova’s work on this material has been supported by the National Science Foundation under Grant No. 0307072.
The project is co-funded by the European Social Fund (75%) and National Resources (25%)- Operational Program for Educational
and Vocational Training II (EPEAEK II) and particularly the program PYTHAGORAS.
A preliminary version of this paper appears in F. Afrati, R. Chirkova, M. Gergatsoulis, V. Pavlaki. Designing Views to Efficiently
Answer Real SQL Queries. In Proc. of SARA 2005, LNAI Vol. 3607, pages 332-346, Springer-Verlag, 2005. 相似文献
6.
Efficient k-Nearest-Neighbor Search Algorithms for Historical Moving Object Trajectories 总被引:1,自引:0,他引:1
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Yun-Jun Gao Chun Li Gen-Cai Chen Ling Chen Xian-Ta Jiang and Chun Chen 《计算机科学技术学报》2007,22(2):232-244
κ Nearest Neighbor (κNN) search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN (κ≥ 1) search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability. 相似文献
7.
A method for estimating a Lipschitz constant of the entropy operator of the Boltzmann type is suggested. Examples of the use of the obtained estimates in problems for restoring images by projections are given.__________Translated from Avtomatika i Telemekhanika, No. 7, 2005, pp. 54–65.Original Russian Text Copyright © 2005 by Popkov, Rublev.This work was supported by the Program “Branch of Information Technologies and Computer Systems” and the Russian Foundation for Basic Research, project no. 02-01-00198a. 相似文献
8.
This paper developed a fast and adaptive method for SAR complex image denoising based on l
k
norm regularization, as viewed from parameters estimation. We firstly establish the relationship between denoising model
and ill-posed inverse problem via convex half-quadratic regularization, and compare the difference between the estimator variance
obtained from the iterative formula and biased Cramer-Rao bound, which proves the theoretic flaw of the existent methods of
parameter selection. Then, the analytic expression of the model solution as the function with respect to the regularization
parameter is obtained. On this basis, we study the method for selecting the regularization parameter through minimizing mean-square
error of estimators and obtain the final analytic expression, which resulted in the direct calculation, high processing speed,
and adaptability. Finally, the effect of regularization parameter selection on the resolution of point targets is analyzed.
The experiment results of simulation and real complex-valued SAR images illustrate the validity of the proposed method.
Supported by the National Natural Science Foundation of China (Grant No. 60572136), the Fundamental Research Fund of NUDT
(Grant No. JC0702005) 相似文献
9.
10.
J. Jakubík 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2003,7(7):468-471
Torsion classes of MV-algebras are defined as radical classes which are closed with respect to homomorphisms; in this paper we investigate their
relations to radical classes of lattice ordered groups and to varieties of MV-algebras.
Supported by Grant VEGA 1/9056/02. 相似文献
11.
In this paper, we develop and analyze an energy efficient ARQ (automatic repeat request) initialized transmit diversity protocol
for cooperative communications. Medium access control (MAC) layer packet retransmission limit (similar to aShortRetryLimit
or aLongRetryLimit [802.11–1997]) has been used as an actuator for transmit cooperative diversity initialization. We take
the channel state information (CSI) as a function of retransmission tries and the number of retransmission tries is modeled
as a random variable. Relays close to the source node are chosen for the transmit cooperation. Closed form expressions are
obtained for symbol error rate (SER), outage capacity and outage probability for the proposed scheme in shadowed fading channels.
This cooperative scheme achieves lower signal-to-noise ratio (SNR), stumpy outage probability, higher bandwidth, and transmit
energy efficiencies for desired average symbol error rate (ASER) than the preceding ARQ based cooperative protocols. Finally,
the results of computer simulations are included to demonstrate the efficacy of the proposed scheme and to verify the accuracy
of the analytical expressions.
Supported by the National Natral Science Foundation of China (Grant No. 60602058), the National High Technology Research and
Development Program of China (Grant No. 2006AA01Z257) 相似文献
12.
We propose an optical scheme to prepare large-scale maximally entangled W states by fusing arbitrary-size polarization entangled W states via polarization-dependent beam splitter. Because most of the currently existing fusion schemes are suffering from the qubit loss problem, that is the number of the output entangled qubits is smaller than the sum of numbers of the input entangled qubits, which will inevitably decrease the fusion efficiency and increase the number of fusion steps as well as the requirement of quantum memories, in our scheme, we design a effect fusion mechanism to generate \(W_{m+n}\) state from a n-qubit W state and a m-qubit W state without any qubit loss. As the nature of this fusion mechanism clearly increases the final size of the obtained W state, it is more efficient and feasible. In addition, our scheme can also generate \(W_{m+n+t-1}\) state by fusing a \(W_m\), a \(W_n\) and a \(W_t\) states. This is a great progress compared with the current scheme which has to lose at least two particles in the fusion of three W states. Moreover, it also can be generalized to the case of fusing k different W states, and all the fusion schemes proposed here can start from Bell state as well. 相似文献
13.
P. Hájek 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2003,7(3):179-183
Three new (easy) results about the computational complexity of basic propositional fuzzy logic BL are presented. An important formula of predicate logic is shown 1-true in all interpretations over saturated BL-chains but is not a BL-1-tautology, i.e. is not 1-true in a safe interpretation over a non-saturated BL-algebra.
Partial support of the grant No. A1030004/00 of the Grant Agency of the Academy of Science of the Czech Republic is acknowledged. 相似文献
14.
In this paper we carry out both light-traffic and heavy-traffic analyses for the calculation of steady-state loss probabilities
in the general multi-server queuing loss system, the GI/G/n/0 queue. The analysis makes use of a heuristic approach called the GM Heuristic, for which a detailed analysis in normal
traffic has previously been published. Sufficient conditions are given for the GM Heuristic to be asymptotically exact in
light traffic. The heuristic is also shown to be asymptotically exact in heavy-traffic when the number of servers n tends
to infinity. These results are illustrated numerically using two-phase Coxian distributions for both the inter-arrival time
and service time. 相似文献
15.
L. Torkzadeh M. M. Zahedi M. Abbasi 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2007,11(10):985-990
In this note by considering the notion of (weak) dual hyper K-ideal, we obtain some related results. After that we determine the relationships between (weak) dual hyper K-ideals and (weak) hyper K-ideals. Finally, we give a characterization of hyper K-algebras of order 3 or 4 based on the (weak) dual hyper K-ideals. 相似文献
16.
B. Davvaz 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2007,11(9):829-837
The object of the present paper is the investigation and study of (fuzzy) hyperideals in H
v
- semigroups. Regular equivalence relations play in H
v
- semigroup theory a role analogous to congruences in semigroup theory, so we introduce fuzzy regular equivalence relations
on H
v
-semigroups and then we study fuzzy Rees regular relations on H
v
-semigroups. Using this ideas, we establish a relation between fuzzy hyperideal of an H
v
-semigroup H and fuzzy hyperideal of a quotient H
v
-semigroup of H. Some characterizations of them are then shown.
相似文献
17.
QoS supported MAC mechanism is a key issue for supporting QoS in wireless ad hoc networks. A new backoff algorithm, named RWBO+BEB, was proposed previ- ously to decrease the packet collision probability significantly. In this paper, it is explored how to make RWBO+BEB support service differentiation in wireless ad hoc networks, and a novel proportional service differentiation algorithm, named p-RWBO, is proposed to allocate the wireless bandwidth according to the band- width ratio of each station. In p-RWBO, station n's walking probability (Pw,n) is selected according to its allocated bandwidth ratio. An analytical model is proposed to analyze how to choose Pw, n according to the bandwidth ratios of station n. The simulation results indicate that p-RWBO can differentiate services in terms of both bandwidth and delay. 相似文献
18.
In this paper, the minimization of a weighted total variation regularization term (denoted TV
g
) with L
1 norm as the data fidelity term is addressed using the Uzawa block relaxation method. The unconstrained minimization problem
is transformed into a saddle-point problem by introducing a suitable auxiliary unknown. Applying a Uzawa block relaxation
method to the corresponding augmented Lagrangian functional, we obtain a new numerical algorithm in which the main unknown
is computed using Chambolle projection algorithm. The auxiliary unknown is computed explicitly. Numerical experiments show
the availability of our algorithm for salt and pepper noise removal or shape retrieval and also its robustness against the
choice of the penalty parameter. This last property is useful to attain the convergence in a reduced number of iterations
leading to efficient numerical schemes. The specific role of the function g in TV
g
is also investigated and we highlight the fact that an appropriate choice leads to a significant improvement of the denoising
results. Using this property, we propose a whole algorithm for salt and pepper noise removal (denoted UBR-EDGE) that is able
to handle high noise levels at a low computational cost. Shape retrieval and geometric filtering are also investigated by
taking into account the geometric properties of the model. 相似文献
19.
The current literature offers two extremes of nonblocking software synchronization support for concurrent data structure design:
intricate designs of specific structures based on single-location operations such as compare-and-swap (CAS), and general-purpose
multilocation transactional memory implementations. While the former are sometimes efficient, they are invariably hard to
extend and generalize. The latter are flexible and general, but costly. This paper aims at a middle ground: reasonably efficient
multilocation operations that are general enough to reduce the design difficulties of algorithms based on CAS alone.
We present an obstruction-free implementation of an atomic k
-location-compare single-location-swap (KCSS) operation. KCSS allows for simple nonblocking manipulation of linked data structures by overcoming the key algorithmic
difficulty in their design: making sure that while a pointer is being manipulated, neighboring parts of the data structure
remain unchanged. Our algorithm is efficient in the common uncontended case: A successful k-location KCSS operation requires only two CAS operations, two stores, and 2k noncached loads when there is no contention. We therefore believe our results lend themselves to efficient and flexible nonblocking
manipulation of list-based data structures in today’s architectures.
A preliminary version of this paper appeared in the Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms
and Architectures, pages 314–323, San Diego, California, USA, 2003. 相似文献
20.
One of the oldest art forms, mosaics are built by careful selection and placement of small pieces called tiles. Although 2D
mosaics have attracted attention in computer graphics research, 3D virtual mosaic sculptures are less common. In this work,
we present a method to simulate mosaic sculptures using tiles with irregular shapes, a method known by mosaicists as Opus Palladium, or simply “crazy paving,” due to the inherent freedom of mixing the tiles. In order to add expressiveness and emphasize
some features, artists distribute the tiles following a high-level design over the shape. We use Voronoi polygons to represent
the tiles computed from a distribution of points on the surface of the 3D object. We also address the simulation of mixed mosaics, where both irregular and squared-shape tiles are used on the same object. Previous works on such surface mosaics
have used only square-shaped tiles, with fixed or variable size. Special mosaic-like effects are obtained with the help from
texture maps, which control the high-level design of the tile distribution. 相似文献