27714693
Efficient Parallel Processing for K-Nearest-Neighbor Search in Spatial Databases
Even though the problem of k nearest neighbor (kNN) query is well-studied in serial environment, there is little prior work on parallel kNN search processing in parallel one. In this paper, we present the first Best-First based Parallel kNN (BFPkNN) query algorithm in a multi-disk setting, for efficient handling of kNN retrieval with arbitrary values of k by parallelization. The core of our method is to access more entries from multiple disks simultaneously and enable several effective pruning heuristics to discard non-qualifying entries. Extensive experiments with real and synthetic datasets confirm that BFPkNN significantly outperforms its competitors in both efficiency and scalability.
11794423
An adaptive consistency maintenance approach for replicated continuous applications
Consistency maintenance is a key problem to replicated continuous applications and dead reckoning (DR) algorithm is widely used in this area. In order to eliminate short-term inconsistency caused by DR algorithm, local-lag approach was proposed. For the purpose of simplicity, fixed lag value is used by local-lag approach and the performance of the approach is greatly deteriorated. In this paper, an adaptive consistency maintenance approach, which is based on local-lag approach, is proposed. The new approach can adjust lag value according to the estimated typical network latency. In order to ensure the criterion of consistency correctness, a lag value adjustment method is also proposed. Through two experiments, the performance of the new approach is evaluated and the results indicate that it is feasible and can greatly improve the performance of the application.
17619661
Your way your missions: from location-based to route-based pervasive gaming
In this paper, we describe the design and implementation of a route-based pervasive game named Your Way Your Missions (YWYM). Since the game obtains the planned routes of players and returns missions in the routes, players can play the game in a casual way, without changing their routes to respond to picked up missions. A self-reporting method is proposed to obtain the planned routes of players, and a corresponding route defining tool is developed upon Google Maps. Two approaches to realize route-based mission adaptation with spatial databases are presented.
14850996
Effects of network characteristics on task performance in a desktop CVE system
The influences of network characteristics on the task performance in a desktop collaborative virtual environment (CVE) system were studied. In the experiment, two participants worked together to accomplish a collaborative task and a network emulator was utilized to simulate real network characteristics. The task used in the experiment was designed to be highly interactive and had rigid requirements on network characteristics (e.g. latency and packet loss). The objective performance and subjective assessment were recorded and analyzed quantitatively as a function of network latency and packet loss rate. The experiment results show that network latency has no distinct effect on task performance when network latency is less than 200 ms and lightly affect task performance when network latency is between 200 and 600 ms; packet loss has no effect on task performance when there are 40 state update messages received per second and lightly affect task performance when there are between 15 and 40 state update messages received per second.
6229211
Resource allocation in a middleware for streaming data
Increasingly, a number of applications rely on, or can potentially benefit from, analysis and monitoring of <i>data streams.</i> To support processing of streaming data in a grid environment, we have been developing a middleware system called GATES (Grid-based AdapTive Execution on Streams). Our target applications are those involving high volume data streams and requiring distributed processing of data arising from a distributed set of sources.
 This paper addresses the problem of resource allocation in the GATES system. Though resource discovery and resource allocation have been active topics in grid community, the pipelined processing and real-time constraint required by distributed streaming applications pose new challenges. We present a resource allocation algorithm that is based on minimal spanning trees. We evaluate the algorithm experimentally and demonstrate that it results in configurations that are very close to optimal, and significantly better than most other possible configurations.
10161187
Accuracy of link capacity estimates using passive and active approaches with CapProbe
CapProbe is an inexpensive and accurate means to estimate capacity. CapProbe combines both dispersion and end-to-end delay to estimate the capacity of the narrowest link on a path. We evaluate in this paper the accuracy of CapProbe estimation, and its dependence on end systems speed, packet sizes, narrow link speeds, and other system parameters. We test kernel and user level implementations of CapProbe and find the kernel implementation to be much more accurate. We also evaluate through experiments the effect of probing packet size on the accuracy of CapProbe estimation. Finally, we explore the idea of a "passive CapProbe" within the context of a TCP flow. Passive here means that the dispersion and delay observed for the TCP flow data and ACK packets, without introducing any additional probing packets. We test active and passive versions of CapProbe with TCP. The active version is found to produce more accurate capacity estimates than the passive version.
25000873
Design, analysis, and implementation of an agent driven pull-based distributed video-on-demand system
The problem of employing multiple servers to serve a pool of clients on a network based multimedia service is addressed. We have designed and practically implemented a prototype system employing multiple servers to render a long duration movie to the customers. We have employed a multiple server retrieval strategy proposed in the literature [39] to realize this system. In the system, server coordination, client behavior and service facilities are completely controlled by an Agent based approach in which we have used the recent Jini technology. Several issues, ranging from data retrieval from individual server, behavior of the underlying network infrastructure, to client management and resource (client buffers) management, are considered in this implementation. We describe in detail our experiences in this complete design process of every module in the software architecture, its purpose, and working style. Further, the system is shown to be robust amidst unpredictable failures, i.e., in the event of server crashes. The load balancing capability is built-in as a safe guard measure to assure a continuous presentation. We present a comprehensive discussion on the software architecture to realize this working system and present our experiences. A system comprising a series of Pentium III PCs on a fast Ethernet network is built as a test-bed. Through this prototype, a wider scope of research challenges ahead are highlighted as possible extensions.
13758632
A new differential LSI space-based probabilistic document classifier
We have developed a new effective probabilistic classifier for document classification by introducing the con differential document vectors and DLSI (differential latent semantic indexing) spaces. A combined use of the projection the distances to the DLSI spaces introduced from the differential document vectors improves the adaptability of the LS semantic indexing) method by capturing unique characteristics of documents. Using the intraand extra-document both a simple posteriori calculation on a small example and an experiment on a large Reuters-21578 database demo advantage of the DLSI space-based probabilistic classifier over the LSI space-based classifier in classification perform  2003 Elsevier B.V. All rights reserved.
4781028
Merging R-Trees: Efficient Strategies for Local Bulk Insertion
A lot of recent work has focussed on bulk loading of data into multidimensional index structures in order to efficiently construct such structures for large datasets. In this paper, we address this problem with particular focus on R-trees—which are an important class of index structures used widely in commercial database systems. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk inserts entire new datasets into an active R-tree. This technique, called STLT (for small-tree-large-tree), considers the new dataset as an R-tree itself (small tree), identifies and prepares a suitable location in the original R-tree (large tree) for insertion, and lastly performs the insert of the small tree into the large tree. Besides an analytical cost model of STLT, extensive experimental studies both on synthetic and real GIS data sets are also reported. These experiments not only compare STLT against the conventional technique, but also evaluate the suitability and limitations of STLT under different conditions, such as varying buffer sizes, ratio between existing and new data sizes, and skewness of new data with respect to the whole spatial region. We find that STLT does much better (in average, about 65%) than the existing technique for skewed datasets as well for large sizes of both the large tree and the small tree in terms of insertion time, while keeping comparable query tree quality. STLT consistently outperforms the alternate technique in all other circumstances in terms of bulk insertion time, especially, even up to 2,000% for the cases when the area of new data sets covers up to 4% of the global region covered by the existing index tree; however, at the cost of a deteriorating resulting tree quality.