Sign In

Communications of the ACM

121 - 130 of 287 for bentley

Trees or grids?: indexing moving objects in main memory

New application areas, such as location-based services, rely on the efficient management of large collections of mobile objects. Maintaining accurate, up-to-date positions of these objects results in massive update loads that must be supported by spatial indexing structures and main-memory indexes are usually necessary to provide high update performance. Traditionally, the R-tree and its variants were used for indexing spatial data, but most of the recent research assumes that a simple, uniform grid is the best choice for managing moving objects in main memory.

We perform an extensive experimental study to compare the two approaches on modern hardware. As the result of numerous design-and-experiment iterations, we propose the update- and query-efficient variants of the R-tree and the grid. The experiments with these indexes reveal a number of interesting insights. First, the coupling of a spatial index, grid or R-tree, with a secondary index on object IDs boosts the update performance significantly. Next, the R-tree, when combined with such a secondary index, can provide update performance competitive with the grid. Finally, the grid can compete with the R-tree in terms of the query performance and it is surprisingly robust to varying parameters of the workloads. In summary, the study shows that, in most cases, the choice of the index boils down to the issues such as the ease of implementation or the support for spatially extended objects.


Designing phrase builder: a mobile real-time query expansion interface

As users enter web queries, real-time query expansion (RTQE) interfaces offer suggestions based on an index garnered from query logs. In selecting a suggestion, users can potentially reduce keystrokes, which can be very beneficial on mobile devices with deficient input means. Unfortunately, RTQE interfaces typically provide little assistance when only parts of an intended query appear among the suggestion choices. In this paper, we introduce Phrase Builder, an RTQE interface that reduces keystrokes by facilitating the selection of individual query words and by leveraging back-off query techniques to offer completions for out-of-index queries. We describe how we implemented a small memory footprint index and retrieval algorithm, and discuss lessons learned from three versions of the user interface, which was iteratively designed through user studies. Compared to standard auto-completion and typing, the last version of Phrase Builder reduced more keystrokes-per-character, was perceived to be faster, and was overall preferred by users.


Self organized multi-agent entangled hierarchies for network security

Cyber-security management is of central importance in financial, business, and military environments. Thus, we propose an effective and efficient self organized entangled hierarchial architecture of multiple agents that decentralizes network security control and communication. Considering the Cyberspace container model, the self organized multi-agent swarms are evolved based on partially observable Markov decision process formal models. Desired network security swarm behaviors are defined and formalized to interact with these models. The "optimal" policy (agent rules and parameters) for a given behavior is evolved using a multi-objective evolutionary algorithm. Swarm effectiveness is compared in various network security scenarios using statistical testing techniques and visualization.


An investigation into the structure of genomes within an evolution that uses embryogenesis

Evolutionary algorithms that use embryogenesis in the creation of individuals have several desirable qualities. Such algorithms are able to create complex, modular designs which can scale well to large problems. However, the inner workings of developmental algorithms have not been investigated as thoroughly as their direct-encoding counterparts. More precisely, it would be beneficial to look at how the rules used during embryogenesis evolve alongside the phenotypes they produced. This paper reports on such an investigation into the evolution of a rule set for the growth of an artificial neural network, and identifies several aspects that are desirable for the genomes of a developmental evolutionary algorithm.


Military network security using self organized multi-agent entangled hierarchies

Effective and efficient Cyber-security management is of central importance in military environments. Many contemporary military communication control structures are based on static, hierarchical designs, which generally lack scalability and flexibility due centralization. Thus, we propose a self organized entangled hierarchial architecture of multiple agents that decentralizes network security control and communication. In particular, we focus on the military CyberCraft container structure. The self organized multi-agent swarms are evolved based on partially observable Markov decision process formal models. Desired swarm behaviors are formalized to interact with these models. The "optimal" policy (agent rules and parameters) for a given behavior is evolved using a multi-objective evolutionary algorithm. Swarm effectiveness is compared in numerous military network security scenarios using statistical testing techniques and visualization.


Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection

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.


On the value of combining feature subset selection with genetic algorithms: faster learning of coverage models

The next challenge for the PROMISE community is scaling up and speeding up model generation to meet the size and time constraints of modern software development projects. There will always be a trade-off between completeness and runtime speed. Here we explore that trade-off in the context of using genetic algorithms to learn coverage models; i.e. biases in the control structures for randomized test generators. After applying feature subset selection to logs of the GA output, we find we can generate the coverage model and run the resulting test suite ten times faster while only losing 6% of the test case coverage.


A BSP-based algorithm for dimensionally nonhomogeneous planar implicit curves with topological guarantees

Mathematical systems (e.g., Mathematica, Maple, Matlab, and DPGraph) easily plot planar algebraic curves implicitly defined by polynomial functions. However, these systems, and most algorithms found in the literature, cannot draw many implicit curves correctly; in particular, those with singularities (self-intersections, cusps, and isolated points). They do not detect sign-invariant components either, because they use numerical methods based on the Bolzano corollary, that is, they assume that the curve-describing function f flips sign somewhere in a line segment AB that crosses the curve, or f(Af(B) < 0. To solve these problems, we have generalized the False Position (FP) method to determine two types of zeros: (i) crossing zeros and (ii) extremal zeros (local minima and maxima without function sign variation). We have called this method the Generalized False Position (GFP) method. It allows us to sample an implicit curve against the Binary Space Partitioning (BSP), say bisection lines, of a rectangular region of R2. Interestingly, the GFP method can also be used to determine isolated points of the curve. The result is a general algorithm for sampling and rendering planar implicit curves with topological guarantees.


Of social television comes home: a field study of communication choices and practices in tv-based text and voice chat

Social television applications have emerged as a potentially valuable convergence of media and communication, but questions remain about the utility and nature of the communication experiences they will provide. We present our study of STV3, an application that adds freeform text and voice chat capabilities to the conventional television-viewing experience. We conducted an in-depth field study of STV3 to understand how friends integrate communication through social television into their lives. Our results reveal users' choices of communication modality, their topics of conversation, and the sense of connectedness that was fostered through their use of STV3. Our findings indicate that participants overwhelmingly preferred text chat to voice chat, and that they often communicated about topics unrelated to the television content.


Efficient skyline retrieval with arbitrary similarity measures

A skyline query returns a set of objects that are not dominated by other objects. An object is said to dominate another if it is closer to the query than the latter on all factors under consideration. In this paper, we consider the case where the similarity measures may be arbitrary and do not necessarily come from a metric space. We first explore middleware algorithms, analyze how skyline retrieval for non-metric spaces can be done on the middleware backend, and lay down a necessary and sufficient stopping condition for middleware-based skyline algorithms. We develop the Balanced Access Algorithm, which is provably more IO-friendly than the state-of-the-art algorithm for skyline query processing on middleware and show that BAA outperforms the latter by orders of magnitude. We also show that without prior knowledge about data distributions, it is unlikely to have a middleware algorithm that is more IO-friendly than BAA. In fact, we empirically show that BAA is very close to the absolute lower bound of IO costs for middleware algorithms. Further, we explore the non-middleware setting and devise an online algorithm for skyline retrieval which uses a recently proposed value space index over non-metric spaces (AL-Tree [10]). The AL-Tree based algorithm is able to prune subspaces and efficiently maintain candidate sets leading to better performance. We compare our algorithms to existing ones which can work with arbitrary similarity measures and show that our approaches are better in terms of computational and disk access costs leading to significantly better response times.