We propose designing data structures called succinct geometric indexes of negligible space (more precisely, o ( n ) bits) that support geometric queries in optimal time, by taking advantage of the n points in the dataset permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O (lg n ) time. We also design three variants of this index. The first supports point location using lg n + 2√lg n + O (lg 1/4 n ) point-line comparisons. The second supports point location in o (lg n ) time when the coordinates are integers bounded by U . The last variant can answer point location queries in O ( H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O ( n ) words or O(n lg n ) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O (lg 2 n ) time.

There is undoubtedly an increase in the number of Web-connected devices, such as home appliances, handheld devices, and smartphones. Though Web applications are intended for information sharing among users, conventional Web technology does not sufficiently support synchronized sharing of information among various devices. We propose a method for synchronized sharing information among various Web-connected devices. We present an online bingo game system as an example of an information-sharing application. Members of the bingo game can shout “Bingo!” at the same time among all members from different environments.

The number of smartphone users and mobile applications are growing rapidly. Though smartphones are expected to have PC-like functionality, hardware resources such as CPUs, memory and batteries are still limited. To solve this resource problem, many researches have proposed architectures to use server resources in the cloud for mobile devices. We propose a conceptual architecture of Android as a Server Platform, which enables multiple user Android applications on cloud server via network. Though Android is mainly designed for physical smartphone, Android's two other features are useful to construct a server platform. Android is open-source product and runs on an ×86 CPU. We show three types of multi-tenant architecture for an Android server platform and discuss the direction to take to it reality.

The numbers of smart phone users and related applications are growing rapidly, and applications continue to become more data-intensive. In the cloud based service for smart phone, if user demand on virtual machines exceeds the hardware capacity of the server, the server incurs an overload and bottleneck, network delay, latency, and packet loss rate are increased in 3G and Wi-Fi connections. Therefore, it is important to predict user demand and to use this information for resource allocation methods such as network virtualization and load balancing. We present a novel user demand prediction method that uses analysis results of application usage patterns. By analysis of log data and using the proposed method, we can predict execution time and average volume of transmitted application data. The proposed method is mainly considered for adoption in our virtual smart phone system. We show results from an experiment performed in an implemented test-bed, including prediction results and performance of wireless media.

The number of smartphone users and mobile application offerings are growing rapidly. A smartphone is often expected to offer PC-like functionality. In this paper, we present Virtual Smartphone over IP system that allows users to create virtual smartphone images in the mobile cloud and to customize each image to meet different needs. Users can easily and freely tap into the power of the data center by installing the desired mobile applications remotely in one of these images. Because the mobile applications are controlled remotely, they are not constrained by the limit of processing power, memory and battery life of a physical smartphone.

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(n log n) expected time using only O(1) extra space; this improves the previous O(n log3 n) bound by Bronnimann, Chan, and Chen [SoCG'04]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(n log n+K) expected running time for output size K, improving the previous O(n log2 n + K) bound by Vahrenhold [WADS'05]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Molhave, and Zeh [ESA'08]. Our results are all obtained by standard random sampling techniques, with some interesting twists.

We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O(n) words or O(n lg n) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O(lg2 n) time.

The term Evil Twin refers to a type of rogue wireless access point that appears to be legitimate, but is set up for the purpose of intercepting traffic between mobile users and the Internet. This paper generalizes a known technique into a model we call ldquoend-to-middle security,rdquo which can be adopted by mobile users to protect against Evil Twin attacks. This model involves using a virtual gateway to securely relay traffic for mobile users. Our intention of formalizing this model is to gain wider awareness of its effectiveness, and to encourage more solution implementations that target on the less programmable mobile devices such as game consoles and VoIP phones. We also derive a minimal set of requirements to verify the correctness of implementation. Towards the end, this paper also provides suggestions to mitigate possible delay in traffic transmission as a result of adopting this model.

Summary form only given. Distributed denial of service (DDoS) attack is one of the most alarming threats on the Internet. DDoS attacks exhaust the critical resources of a target server in order to deny its services to the legitimate clients. In this paper, we propose a full set of techniques for defending against DDoS attacks. The complete countermeasure strategies are broken down to detection, segregation and mitigation techniques. Detection techniques are used to determine if any attack is taking place at any given moment. Segregation techniques aim to separate malicious traffic from legitimate traffic. Finally, the mitigation techniques are used to effectively minimizing the negative impact caused by DDoS attacks.

We initiate the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered.

For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

Researchers of active networks have been working on ways to make intermediate nodes (routers or switches) programmable, in order to accelerate the creation of new network services and to meet ever-changing user demands. However, one area has often been neglected: solution deployment on multi-provider networks. Because the Internet is composed of networks governed by different management entities with different policies, deploying new network solutions across different domains requires some form of contract to be already in place among the domains involved. We propose a framework we call FSP (federation of service providers), which will automatically allow management entities in different domains to formulate mutual agreements. Our framework is applicable, not only to active networks, but also to future solutions that could be deployed using existing devices.