Abstract

In this paper we consider range-aggregate query problems wherein we wish to preprocess a set S of geometric objects such that given a query orthogonal range q, a certain aggregation function on the objects S0 = S \ q can be answered eciently. Range-aggregate version of point enclosure queries, 1-d segment intersection, 2-d orthogonal seg- ment intersection (with/without distance constraint) are revisited and we improve the existing results for these problems. We also provide semi- dynamic (insertions) solutions to some of these problems. This paper is the rst attempt to provide dynamic solutions to problems involving geometric aggregation operations.

Abstract

We consider the dominating point set reporting problem in two-dimension. We propose a data structure for finding the set of dominating points inside a given orthogonal query rectangle. Given a set of n points in the plane, it supports 4-sided queries in O (log n+ k), where k is size of the output, using O (n log n) space. This work can be of application when range queries are generated using mobile devices with limited display capacity.

Abstract

In this work we study the problem of finding axesparallel regions of maximum density for weighted point sets in IR2 and IR3. The 2-d variant is motivated by applications in thermal analysis of VLSI chips.

Abstract

Sensor networks consist of small motes attached with sensors to measure ambient parameters like temperature, humidity and light. As these motes are unreliable due to wireless link quality and also the data measuring sensors cannot be calibrated accurately for a given applications need. The unique data fusion needs are that parameter being measured is distributed across the network and needs to be computed reliably and with minimum overhead and redundancy due to data value being correlated. We show the asymptotic complexity of topology control when applied to power-aware routing is scalable and argue that the accuracy and reliability of the estimated sensor values can be accurately predicted for the physical value being sensed and aggregating. A prefix-based routing protocol is used for data-centric storage, which allows querying distributed parameters using a KEY, VALUE pairs without the need of the sensor node to know its exact geographic information. Intelligent sensor information processing, which is driven by these requirements, is discussed under the framework INSPIRE-DB.

Abstract

Tagging of images using descriptive keywords (tags), contributed by ordinary users, is a powerful way of organizing them. However, due to the richness of the image content, it is often difficult to choose tags that best describe the content of the image to the viewing audience and ensure access to the image. In this paper, we present a novel tagging framework based on the theory of emergent semantics to assist the user in the tag selection process. Our idea is to enrich the current" looking at" experience of tagging with the" looking for" experience of searching. We describe the design of our approach along with a preliminary user study conducted with a prototype Flickr application.

Abstract

Marking the image content with descriptive keywords (also known as tags) is an effective way of improving the accessibility of images. However, doing so practically is boring as well as laborious to most humans. In the recent times, there have been number of attempts to inspire humans to annotate images. Notable examples are social tagging like Flickr and online games like ESP. However, existing methods in their present form are inadequate to result in annotations of superior quality. Therefore, we present GoFish, an intelligent system for semantic annotation of images. GoFish is a web variant of standard Go Fish, a popular playing card game. GoFish utilizes the theory of Emergent Semantics to ensure that all images will have superior tags. We describe the complete design of the game and discuss its benefits. Results of a preliminary user study are encouraging.

Abstract

In the recent past composability has emerged as a key requirement for various distributed protocols. It is not enough for a protocol to be robust when it runs in isolation or in a “stand-alone” setting but it should be robust even in an environment where several copies of the same protocol or other protocol(s) are running simultaneously. In this work, we investigate the composability for protocols that tolerate a bounded adversary modeled as a probabilistic polynomial time Turing machine. We examine composability of protocols for two fundamental problems in distributed computing - reliable unicast and reliable broadcast. We show that any composable protocol – for reliable unicast tolerating an adversary, that corrupts up to any t nodes, requires 2t + 1 connectivity and for reliable broadcast tolerating an adversary, that corrupts up to any t nodes, requires n > 3t and 2t + 1 connectivity.

Abstract

Pease et al. introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among n players tolerating up to t faults is (efficiently) possible iff n > 3t. To overcome this severe limitation, Pease et al. introduced a variant of BGP, Authenticated Byzantine General (ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to n > t (which is a huge improvement over the n > 3t). Byzantine faults are the most generic form of faults. In a network not all faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in (t b ,t p )-mixed adversary model where the adversary can corrupt up to any t b players actively and control up to any other t p players passively. We prove that in such a setting, ABG over a completely connected synchronous network of n nodes tolerating a (t b ,t p )-adversary is possible iff n > 2t b +min(t b ,t p ) when t p  > 0. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

Abstract

This paper provides a solution to the issue:“How can we use Wikipedia based concepts in document clustering with lesser human involvement, accompanied by effective improvements in result?” In the devised system, we propose a method to exploit the importance of N-grams in a document and use Wikipedia based additional knowledge for GAAC based document clustering. The importance of N-grams in a document depends on a many features including, but not limited to: frequency, position of their occurrence in a sentence and the position of the sentence in which they occur, in the document. First, we introduce a new similarity measure, which takes the weighted N-gram importance into account, in the calculation of similarity measure while performing document clustering. As a result, the chances of topical similarity in clustering are improved. Second, we use Wikipedia as an additional knowledge base both, to remove noisy entries from the extracted N-grams and to reduce the information gap between N-grams that are conceptually-related, which do not have a match owing to differences in writing scheme or strategies. Our experimental results on the publicly available text dataset clearly show that our devised system has a significant improvement in performance over bag-of-words based state-of-the-art systems in this area.

Abstract

We study the interplay of network connectivity and the issues related to the 'possibility', 'feasibility' and 'optimality' for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.