5363634
Applying bulk insertion techniques for dynamic reverse nearest neighbor problems
Reverse nearest neighbors queries have emerged as an important class of queries for spatial and other types of databases. The Rdnn-tree is an R-tree based structure that has been shown to perform outstandingly for such kind of queries. However, one practical problem facing it (as well as other type of indexes) is how to effectively construct the index from stretch. In this case, the cost of constructing and maintaining a Rdnn-Tree is about twice the cost of an R-Tree. Normal insertion into a Rdnn-Tree is performed one point at a time, known as single point insertion. The question arises, can insertion be improved there by reducing the construction and maintenance cost. In this paper we propose a bulk-loading technique, which is capable of significantly, improve the performance of constructing the index from stretch, as well as insert a large amount of data. Experiments show that our method outperforms the single point insertion significantly.
11135944
Fuzzy Clustering of Web Logs for User Classification
17442336
Ordinal association rules for error identification in data sets
A new extension of the Boolean association rules, ordinal association rules, that incorporates ordinal relationships among data items, is introduced. One use for ordinal rules is to identify possible errors in data. A method that finds these rules and identifies potential errors in data is proposed.
18266651
A similarity-based soft clustering algorithm for documents
Document clustering is an important tool for applications such as Web search engines. Clustering documents enables the user to have a good overall view of the information contained in the documents that he has. However, existing algorithms suffer from various aspects, hard clustering algorithms (where each document belongs to exactly one cluster) cannot detect the multiple themes of a document, while soft clustering algorithms (where each document can belong to multiple clusters) are usually inefficient. We propose SISC (similarity-based soft clustering), an efficient soft clustering algorithm based on a given similarity measure. SISC requires only a similarity measure for clustering and uses randomization to help make the clustering efficient. Comparison with existing hard clustering algorithms like K-means and its variants shows that SISC is both effective and efficient.
46019766
A Study on Textual Entailment
In this paper we study a graph-based approach to the task of textual entailment between a text and hypothesis. The approach takes into account the full lexico-syntactic context of both the text and hypothesis and relies heavily on the concept of subsumption. It starts with mapping the text and hypothesis into graph structures where nodes represent concepts and edges represent lexico-syntactic relations among concepts. Based on a subsumption score between the text-graph and hypothesis-graph an entailment decision is then made. The impact of synonymy on entailment is quantified and discussed. An important advantage of our solution is the ability to customize it so that high-confidence results are obtained
15536346
An Index Structure for Data Mining and Clustering
Abstract. In this paper we present an index structure, called MetricMap, that takes a set of objects and a distance metric and then maps those objects to a k-dimensional space in such a way that the distances among objects are approximately preserved. The index structure is a useful tool for clustering and visualization in data-intensive applications, because it replaces expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. We compare the index structure with another data mining index structure, FastMap, recently proposed by Faloutsos and Lin, according to two criteria: relative error and clustering accuracy. For relative error, we show that (i) FastMap gives a lower relative error than MetricMap for Euclidean distances, (ii) MetricMap gives a lower relative error than FastMap for non-Euclidean distances (i.e., general distance metrics), and (iii) combining the two reduces the error yet further. A similar result is obtained when comparing the accuracy of clustering. These results hold for different data sizes. The main qualitative conclusion is that these two index structures capture complementary information about distance metrics and therefore can be used together to great benefit. The net effect is that multi-day computations can be done in minutes.
206624023
A Class of Rate-Based Real-Time Scheduling Algorithms
This paper investigates a class of rate-based real-time scheduling algorithms based on the idea of general processor sharing (GPS). We extend the GPS framework of Parekh and Gallager (1993) for periodic and sporadic process scheduling and show the optimality of GPS-based scheduling. In particular, we propose the earliest-completion-time GPS (EGPS) scheduling algorithm to simulate the GPS algorithm with much lower run-time overheads. The schedulability of each process is enforced by a guaranteed CPU service rate, independent of the demands of other processes. We provide a theoretical foundation to assign proper CPU service rates to processes to satisfy their individual stringent response time requirements. We also propose a GPS-based scheduling mechanism for jitter control. Finally, the performance of the proposed algorithms is studied using a generic avionics platform example and simulation experiments on jitter control and mixed soft and hard real-time process scheduling.
24712591
Integrating Priority with Share in the Priority-Based Weighted Fair Queuing Scheduler for Real-Time Networks
The Weighted Fair Queuing (WFQ) scheduler has been closely studied due to its desirable properties of bandwidth guarantee and bounded delay. However, the queuing delay bound of a communication session is tightly coupled with the session's allocated service share. To receive a low queuing delay, a session must reserve a high share. In this paper, we study a new fair queuing algorithm called Priority-based Weighted Fair Queuing (PWFQ). PWFQ combines a session's allocated share to achieve the bandwidth guarantee and the session's priority to adjust the delay bound inside a sliding window. The new algorithm decouples the delay from the service share so that a session with a low share but a high priority may still receive a small delay. We analyze the worst-case delay bound of PWFQ and propose a simple algorithm to assign session priorities.
32154890
BWE: a resource sharing protocol for multimedia systems with bandwidth reservation
In multimedia systems with soft real-time constraints, tasks must be guaranteed a certain system bandwidth so they can provide an acceptable performance to their users. In this paper a bandwidth exchange (BWE) protocol is proposed to manage resource sharing issues between tasks running on systems with CPU bandwidth reservation. The approach improves an earlier protocol, bandwidth inheritance (BWI), in that it provides bandwidth isolation not only between independent groups of tasks, but also between any two tasks within the same resource sharing group. BWE thus provides fairer resource allocation than BWI.
362708
Low-Cost RFID Identification Variation
Interests continue to grow in recent years for the adoption of Radio Frequency Identification (RFID) in many different areas including transportation and supply chain management. Those RFID-included objects can be targeted more efficiently by real-time tracking and instant management. However, because of the contact-less type of RFID remote retrieval, the transmission of data in the air is very vulnerable to eavesdropping or appropriation. A primary security concern surrounding RFID technology is the illicit tracking of consumer location and analyzing of their shopping habits or behavior. This paper proposes a more secure and lightweight RFID variation protection protocol which enhances the security of the transmission of information as well as the consumer privacy protection by using randomized control access and two-way identification. In addition, this protocol also improves the overall performance and lowers the cost of RFID tag without any complicated calculation.
14056151
Distributed pinwheel scheduling with end-to-end timing constraints
Algorithms for allocating resources and scheduling tasks are important to the success of many real-time systems with end-to-end performance requirements. In this paper, an end-to-end scheduling model based on the pinwheel scheduling algorithms is presented for distributed real-time systems. We discuss how tasks on different nodes may be transformed to have harmonic periods. We also present algorithms to adjust the phases between schedules on neighboring nodes so that the overall end-to-end delay is reduced. Using the pinwheel approach, schedules on different nodes are closely synchronized and more static. However, for many real-time systems, this practical approach may provide a more predictable performance and a shorter end-to-end delay.