5965790
On scalable and locality-aware web document sharing
We propose a scalable Web document sharing infrastructure model called Browsers-Aware Proxy Server. In this design, a proxy server connecting to a group of networked clients maintains an index file of data objects of all clients' browser caches. If a user request misses in its local browser cache and the proxy cache, the browsers-aware proxy server will search the index file attempting to find it in another client's browser cache before sending the request to an upper level proxy or the Web server. If such a request does hit in a remote client, this client will directly forward the data object to the requesting client; or the proxy server fetches the data object from this client and then forwards it to the requesting client. The contributions of this caching model are twofold. First, we show that the amount of sharable data in browser caches is significant and can be utilized for document sharing among clients to improve Web caching performance and scalability. Second, the browsers-aware model can effectively and further improve Web prefetching performance. The browsers-aware model and its supported prefetching technique build a strong locality-aware Internet environment to make Web accesses fast with low communication costs. Conducting trace-driven simulations, we show the effectiveness of the browsers-aware model, and its unique advantages to facilitate prefetching.
35965067
Dynamic Layer Management in Superpeer Architectures
Superpeer unstructured P2P systems have been found to be very effective by dividing the peers into two layers, superlayer and leaf-layer, in which message flooding is only conducted among superlayer and all leaf-peers are represented by corresponding superpeers. However, current superpeer systems do not employ any effective layer management schemes, so the transient and low-capacity peers are allowed to act as superpeers. Moreover, the lack of an appropriate size ratio maintenance mechanism on superlayer to leaf-layer makes the system's search performance far from being optimal. We present one workload model aimed at reducing the weighted overhead of a network. Using our proposed workload model, a network can determine an optimal layer size ratio between leaf-layer and superlayer. We then propose a dynamic layer management algorithm, DLM, which can maintain an optimal layer size ratio and adaptively elect and adjust peers between superlayer and leaf-layer. DLM is completely distributed in the sense that each peer decides to be a superpeer or a leaf-peer independently without global knowledge. DLM could effectively help a superpeer P2P system maintain the optimal layer size ratio and designate peers with relatively long lifetime and large capacities as superpeers, and the peers with short lifetime and low capacities as leaf-peers under highly dynamic network situations. We demonstrate that the quality of a superpeer system is significantly improved under the DLM scheme by comprehensive simulations.
848425
Location awareness in unstructured peer-to-peer systems
Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies.
12060317
DiCAS: An Efficient Distributed Caching Mechanism for P2P Systems
Peer-to-peer networks are widely criticized for their inefficient flooding search mechanism. Distributed hash table (DHT) algorithms have been proposed to improve the search efficiency by mapping the index of a file to a unique peer based on predefined hash functions. However, the tight coupling between indices and hosting peers incurs high maintenance cost in a highly dynamic network. To properly balance the tradeoff between the costs of indexing and searching, we propose the distributed caching and adaptive search (DiCAS) algorithm, where indices are passively cached in a group of peers based on a predefined hash function. Guided by the same function, adaptive search selectively forwards queries to "matched" peers with a high probability of caching the desired indices. The search cost is reduced due to shrunk searching space. Different from the DHT solutions, distributed caching loosely maps the index of a file to a group of peers in a passive fashion, which saves the cost of updating indices. Our simulation study shows that the DiCAS protocol can significantly reduce the network search traffic with the help of small cache space contributed by each individual peer
6911930
LANDMARC: Indoor Location Sensing Using Active RFID
Growing convergence among mobile computing devices and embedded technology sparks the development and deployment of “context-aware” applications, where location is the most essential context. In this paper we present LANDMARC, a location sensing prototype system that uses Radio Frequency Identification (RFID) technology for locating objects inside buildings. The major advantage of LANDMARC is that it improves the overall accuracy of locating objects by utilizing the concept of reference tags. Based on experimental analysis, we demonstrate that active RFID is a viable and cost-effective candidate for indoor location sensing. Although RFID is not designed for indoor location sensing, we point out three major features that should be added to make RFID technologies competitive in this new and growing market.
18230
Indexable PLA for Efficient Similarity Search
Similarity-based search over time-series databases has been a hot research topic for a long history, which is widely used in many applications, including multimedia retrieval, data mining, web search and retrieval, and so on. However, due to high dimensionality (i.e. length) of the time series, the similarity search over directly indexed time series usually encounters a serious problem, known as the "dimensionality curse". Thus, many dimensionality reduction techniques are proposed to break such curse by reducing the dimensionality of time series. Among all the proposed methods, only Piecewise Linear Approximation (PLA) does not have indexing mechanisms to support similarity queries, which prevents it from efficiently searching over very large time-series databases. Our initial studies on the effectiveness of different reduction methods, however, show that PLA performs no worse than others. Motivated by this, in this paper, we re-investigate PLA for approximating and indexing time series. Specifically, we propose a novel distance function in the reduced PLA-space, and prove that this function indeed results in a lower bound of the Euclidean distance between the original time series, which can lead to no false dismissals during the similarity search. As a second step, we develop an effective approach to index these lower bounds to improve the search efficiency. Our extensive experiments over a wide spectrum of real and synthetic data sets have demonstrated the efficiency and effectiveness of PLA together with the newly proposed lower bound distance, in terms of both pruning power and wall clock time, compared with two state-of-the-art reduction methods, Adaptive Piecewise Constant Approximation (APCA) and Chebyshev Polynomials (CP).
17779261
A Framework for Incorporating Class Priors into Discriminative Classification
Discriminative and generative methods provide two distinct approaches to machine learning classification. One advantage of generative approaches is that they naturally model the prior class distributions. In contrast, discriminative approaches directly model the conditional distribution of class given inputs, so the class priors are only implicitly obtained if the input density is known. In this paper, we propose a framework for incorporating class prior proportions into discriminative methods in order to improve their classification accuracy. The basic idea is to enforce that the distribution of class labels predicted on the test data by the discriminative model is consistent with the class priors. Therefore, the discriminative model has to not only fit the training data well but also predict class labels for the test data that are consistent with the class priors. Experiments on five different UCI datasets and one image database show that this framework is effective in improving the classification accuracy when the training data and the test data come from the same class proportions, even if the test data does not have exactly the same feature distribution as the training data.
34130479
Efficient and inefficient ant coverage methods
Ant robots are simple creatures with limited sensing and computational capabilities. They have the advantage that they are easy to program and cheap to build. This makes it feasible to deploy groups of ant robots and take advantage of the resulting fault tolerance and parallelism. We study, both theoretically and in simulation, the behavior of ant robots for one-time or repeated coverage of terrain, as required for lawn mowing, mine sweeping, and surveillance. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. To overcome these limitations, we study navigation methods that are based on real-time (heuristic) search and leave markings in the terrain, similar to what real ants do. These markings can be sensed by all ant robots and allow them to cover terrain even if they do not communicate with each other except via the markings, do not have any kind of memory, do not know the terrain, cannot maintain maps of the terrain, nor plan complete paths. The ant robots do not even need to be localized, which completely eliminates solving difficult and time-consuming localization problems. We study two simple real-time search methods that differ only in how the markings are updated. We show experimentally that both real-time search methods robustly cover terrain even if the ant robots are moved without realizing this (say, by people running into them), some ant robots fail, and some markings get destroyed. Both real-time search methods are algorithmically similar, and our experimental results indicate that their cover time is similar in some terrains. Our analysis is therefore surprising. We show that the cover time of ant robots that use one of the real-time search methods is guaranteed to be polynomial in the number of locations, whereas the cover time of ant robots that use the other real-time search method can be exponential in (the square root of) the number of locations even in simple terrains that correspond to (planar) undirected trees.
17413518
Enhancing the Effectiveness of Clustering with Spectra Analysis
For many clustering algorithms, such as K-Means, EM, and CLOPE, there is usually a requirement to set some parameters. Often, these parameters directly or indirectly control the number of clusters, that is, k, to return. In the presence of different data characteristics and analysis contexts, it is often difficult for the user to estimate the number of clusters in the data set. This is especially true in text collections such as Web documents, images, or biological data. In an effort to improve the effectiveness of clustering, we seek the answer to a fundamental question: How can we effectively estimate the number of clusters in a given data set? We propose an efficient method based on spectra analysis of eigenvalues (not eigenvectors) of the data set as the solution to the above. We first present the relationship between a data set and its underlying spectra with theoretical and experimental results. We then show how our method is capable of suggesting a range of k that is well suited to different analysis contexts. Finally, we conclude with further empirical results to show how the answer to this fundamental question enhances the clustering process for large text collections.
7923791
Discontinuity-Based Simplification of Free Form Surface From a Range Image
This paper improves an existing method for more accurate simplification of free form surface represented as dense points. The main improvement lies in two aspects: one is the introduction of a novel transformation of curvatures, the other is to propose sampling points using both curvature information and curvature variation information. The experimental results based on real images show that the original object surface has been better approximated and the majority of the surface discontinuities have been better preserved with considerably few sampled (5%) data points
10940084
Hamiltonian Graphs with Large Neighborhood Unions