36612071
SPY-TEC: An efficient indexing method for similarity search in high-dimensional data spaces
Most of all index structures based on the R-tree have failed to support eAcient indexing mechanisms for similarity search in high-dimensional data spaces. This is due to the fact that most of the index structures commonly use balanced split strategy in order to guarantee storage utilization and the shape of queries for similarity search is a hypersphere in high-dimensional spaces. In this paper, we propose the Spherical Pyramid-Technique (SPY-TEC), an eAcient indexing method for similarity search in high-dimensional data space. The SPY-TEC is based on a special partitioning strategy, which is to divide the d-dimensional data space first into 2d spherical pyramids, and then cut the single spherical pyramid into several spherical slices. This partition provides a transformation of d-dimensional space into one-dimensional space as the Pyramid-Technique [14] does. Thus, we are able to use a B a -tree to manage the transformed one-dimensional data. We also propose the algorithms to process hyperspherical range queries on the data space partitioned by this partitioning strategy. Finally, we show that the SPY-TEC clearly outperforms other related techniques including the Pyramid-Technique in processing hyperspherical range queries through various experiments using synthetic and real data. ” 2000 Elsevier Science B.V. All rights reserved.
6127186
An efficient nearest neighbor search in high-dimensional data spaces
Similarity search in multimedia databases requires an efficient support of nearest neighbor search on a large set of high-dimensional points. A technique applied for similarity search in multimedia databases is to transform important properties of the multimedia objects into points of a high-dimensional feature space. The feature space is usually indexed using a multidimensional index structure. Then, similarity search corresponds to a range search which returns all objects within a threshold level of similarity to the query objects, and a k-nearest neighbor search that returns the k most similar objects to the query object. Initially, traditional multidimensional data structures (e.g., R-tree [1], kd-tree [5]), which were designed for indexing low-dimensional spatial data, were used for indexing high-dimensional feature vectors. However, recent research activities [10,9,8] reported
15086952
Crosstalk- and performance-driven multilevel full-chip routing
In this paper, we propose a novel framework for fast multilevel routing considering crosstalk and performance optimization. To handle the crosstalk minimization problem, we incorporate an intermediate stage of layer/track assignment into the multilevel routing framework. For performance-driven routing, we propose a novel minimum-radius minimum-cost spanning tree heuristic for global routing. Compared with the state-of-the-art multilevel routing with the routability mode, the experimental results show that our router achieved a 6.7X runtime speedup, reduced the respective maximum and average crosstalk (coupling length) by about 30% and 24%, reduced the respective maximum and average delay by about 15% and 5%. Compared with the timing-driven mode, the experimental results show that our router still achieved a 5.9X runtime speedup, reduced the respective maximum and average crosstalk by about 35% and 23%, reduced the respective maximum and average delay by about 7% and 10% in comparable routability, and resulted in fewer failed nets.
19220261
Path protection and blocking probability minimization in optical networks
We study the problem of shared path protection in optical networks from the viewpoint of blocking probability minimization. Unlike the worst-case approach common in other studies, which typically deals with one failure at a time and requires recomputation of the protection paths after every failure, our framework assumes a fixed path protection strategy for every connection that does not change in response to failures in other connections, which is more realistic for networks with high failure rates. We study backup-path strategy configurations that minimize the blocking probability and derive various properties. We show that configurations which do not have partial overlaps among connections backup paths are optimal in a rather general sense. We discuss the minmax optimal configuration properties and present an efficient algorithm for finding it in a case of special interest, while showing it to be NP-hard in general. In addition, we discuss the properties of the game resulting if each connection chooses its backup path selfishly; we show it to belong to the class of potential games, well-studied in the game theory literature, and derive several further properties resulting from its specific structure.
16842793
Broadcast Encryption Using Efficient Key Distribution and Renewal for Ubiquitous Environments
The method of broadcast encryption has been applied to the transmission of digital information such as multimedia, software, and paid TV on the open network. In this broadcast encryption method, only previously authorized users can gain access to digital information. When broadcast message is transmitted, authorized users can first decode the session key using the previously given private key and get digital information using this session key. This way, users retrieve a message or a session key using the key transmitted by broadcasters. For their part, broadcasters need to generate and distribute keys. Broadcasters should also carry out efficient key renewal when users subscribe or unsubscribe. This paper introduces how to generate and distribute key efficiently and how key renewal works. The proposal uses two methods: (1) the server generates keys without the consent of users by anticipating users, and; (2) the server and users generate keys by mutual agreement. The advantage of the two proposed methods is that the receiver can decode broadcast message using a secret key. Even if the key is renewed later, the user can efficiently renew using only a single set of information.
7800252
Imprecise data computation for high performance asynchronous processors
Instruction level parallelism(ILP) is strictly limited by various dependencies. In particular , data dependency is the major performance bottleneck of data intensive applications. To accelerate the execution of sequential code serialized due to data dependencies, this paper proposes an imprecise computation as a fast data computing technique for a high-performance asynchronous processor. To show the performance benefits of the suggested computing model, simulation results are presented. The imprecise computation can be used effectively in data intensive processing with a microprocessor, a Digital Signal Processor or a multimedia processor.
6192203
Authentication for Single/Multi Domain in Ubiquitous Computing Using Attribute Certification
The Ubiquitous computer environment is thing which invisible computer that is not shown linked mutually through network so that user may use computer always is been pervasive. Intend computing environment that can use easily as user wants and it is the smart environment that user provides context awareness that is wanting computing environment. This Ubiquitous computing contains much specially weak side in security. Masquerade attack of that crawl that is quoted to user or server among device that is around user by that discrete various computing devices exist everywhere among them become possible. Hereupon, in this paper, proposed method that has following characteristic. Present authentication model through transfer or device. Suggest two method that realize authentication through device in case of moved to method (MD: Multi Domain) and user ownself space (SD: Single Domain) that realize authentication through device in case of moved user's direct path who device differs.